다이나믹 프로그래밍 큰 문제를 작은 문제로 나눠서 푸는 알고리즘을 말한다. Devide and Conquere와 비슷하지만, 큰 문제를 작은 문제로 나눴을 때 작은 문제들 중 동일한 문제를 계산하지 않는다는 차이점이 있다. 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다. 겹치는 부분 문제가 나타난다. (Overlapping Subproblem) 최적 부분 구조가 나타난다. (Optimal Substructure) 즉, 문제의 정답을 작은 문제의 정답에서 구할 수 있다. 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. 따라서, 정답을 한 번 구했으면 정답을 어딘가에 저장해놓는다. 이런 방법을 Memoization이라고 한다. 다이나믹 프로그래밍을 해결하는 방법에는 Top-do..

플러드 필(Flood fill) 어떤 위치와 연결된 모든 위치를 찾는 알고리즘이다. 2667 단자번호 붙이기, 백준 온라인 저지 N*N 사이즈의 정사각형 모양 지도가 있다. 이 지도에 나온 집들 중, 연결된 집들의 모임인 단지를 정의찾아 번호를 붙이려고 한다. 이때 상하좌우에 집이 인접해있을 때 연결되어있다고 말한다. (지도에서 0은 집이 없는 곳, 1은 집이 있는 곳을 나타낸다.) DFS나 BFS 알고리즘을 이용해서 이어져있는 집을 찾을 수 있다. 4963 섬의 갯수, 백준 온라인 저지

그래프의 탐색 목적: 시작점 X로 시작하여 모든 정점을 1번씩 방문하고자 한다. 깊이 우선 탐색(DFS) 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고, 더 이상 갈 수 없으면 이전 정점으로 돌아간다. 스택을 이용하는 가장 쉬운 방법은 재귀 호출을 이용하는 방법이다. 인접 행렬을 이용한 구현은 다음과 같다. 정점의 갯수를 V라고 할 때, 시간 복잡도는 O(v^2)가 된다. void dfs(int x) { check[x] = true; printf("%d ", x); for(int i=0; i

그래프 정점(Node, Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 이때 간선은 정점간의 관계를 나타낸다. G = (V, E)로 나타낸다. 자세한 내용은 생략한다. 그래프의 표현 인접 행렬(Adjacency-matrix) 정점의 개수를 V라고 했을 때 VxV크기의 이차원 배열을 이용한다. a[i][j]는 i에서 j로 가는 간선의 존재 유무를 나타낸다.(0: 有, 1:無) 가중치를 표현하고 싶다면 0일때 간선이 없음, 1이상의 수일때 가중치로 표현할 수 있다. 인접 리스트(Adjacency-list) 리스트를 이용해서 구현한다. A[i]=i와 연결된 정점을 리스트로 표현한다. 리스트는 크기를 동적으로 변경할 수 있어야 하기 때문에, 일반적인 배열은 사용할 수 없다. 가중치를 표현할때는 리스트..

비트마스크 비트마스크를 이용해서 부분집합을 구할 수 있다는 점을 기억하고 가자. not 연산의 경우 자료형에 따라 결과가 달라진다. 또한, unsigned, signed에 따라서 보여지는 값이 달라진다. signed의 경우 가장 앞 자리 비트를 이용하여 음수/양수를 구별하기 때문이다. 정수의 집합을 나타낼 때 사용할 수 있다. 집합에는 같은수가 없기 때문이다. 570을 이진수로 나타내면 1000111010이 되는데, 이는 2^9+2^5+2^4+2^3+2^1로 나타낼 수 있다. 이를 통해서 주어진 수 570를 집합 {1, 3, 4, 5, 9}로 표현할 수 있다. 비트마스크를 사용하게되면 정수를 사용하는 것보다, 공간복잡도가 줄어들게 된다. 비트마스크의 연산 &를 사용하여 비트가 있는지 알 수 있다. |를 ..

재귀 함수 함수 내에서 자기 자신을 다시 호출하는 함수이다. 이 함수를 잘 사용하면 N번의 반복문을 보다 보기 쉽게 작성할 수 있다. 단, 다중 루프문을 사용한 것보다 복잡도가 줄어들지는 않을 수 있다. 재귀 함수는 잘 짜는게 중요한데, 항상 다음의 경우를 고려해야 한다. 조건에 맞지 않는 경우(불가능한 경우) 정답을 찾은 경우 재귀 호출을 하는 경우(다음의 경우를 실행하는 경우) 9095 1, 2, 3 더하기, 백준 온라인 저지 정수 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제. 주어진 N이 3일 경우, 1, 2, 3의 합으로 나타내는 방법은 아래의 표와 같다. N=4 1+1+1+1 1+1+2 1+2+1 1+1+2 2+1+1 2+2 1+3 3+1 이 때, Ngoal, 즉 합산 결과가 ..