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

BFS BFS의 목적은 임의의 정점에서 시작해서, 모든 정점을 한 번씩 방문하는 것이다. 모든 가중치가 1일 때, BFS는 최단거리를 구하는 알고리즘이 된다. BFS를 이용해서 최단거리를 구하기 위해서는, 다음과 같은 유형의 문제여야 한다. 최소 비용 문제여야 한다. 모든 간선의 가중치는 1이어야한다. 정점과 간선의 갯수에 제한이 있어야 한다. 다시 말하면, 문제에서 주어진 시간 및 메모리 제한을 만족시킬 수 있어야 한다. 간선을 이용했을 때 이동할 수 있는 가짓수가 다른 경우, 다른 정점이라고 봐야 한다. 이런 경우에는 그래프를 쪼개서 생각해봐야 한다는 점을 주의하자. 2178 미로 탐색, 백준 온라인 저지 (1, 1)에서 (N, M)으로 가는 가장 빠른 길을 구하는 문제이다. DFS 탐색으로는 문제를..

플러드 필(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}로 표현할 수 있다. 비트마스크를 사용하게되면 정수를 사용하는 것보다, 공간복잡도가 줄어들게 된다. 비트마스크의 연산 &를 사용하여 비트가 있는지 알 수 있다. |를 ..