플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드-워셜 알고리즘은 그래프에서 모든 정점 간의 최단 거리를 구하는 알고리즘입니다. 데이크스트라 알고리즘이 하나의 정점(시작 정점)으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이었다면, 플로이드-워셜 알고리즘은 모든 정점에서 모든 정점으로부터 모든 정점까지의 최단 경로를 구하는 알고리즘이며 음의 경로가 존재하는 그래프에서도 사용할 수 있습니다. 또한 플로이드-워셜 알고리즘은 다이나믹 프로그래밍 기법이 적용될 수 있습니다. 알고리즘 원리 플로이드-워셜 알고리즘은 정점 A에서 정점 C에 대한 최단경로를 구하기 위해 `정점 A에서 정점 C에 대한 경로`와 `정점 A에서 정점 B를 거쳐 정점 B에서 정점 C로 가는 경로`를 ..

데이크스트라 알고리즘 (Dijkstra Algorithm) 데이크스트라 알고리즘은 그래프에서 정점 간의 최단 경로를 찾는 탐색 알고리즘입니다. 예를 들어 여러 개의 도시가 있을 때 도시 사이를 연결하는 도로의 길이를 최소 비용으로 계산하여 건설하고자 할 때와 같이 현실 세계의 다양한 상황에서 사용될 수 있는 알고리즘입니다. 또한 그래프 내에서 하나의 최단 경로는 다른 여러 최단 경로로 만들어질 수 있으므로 기존에 저장되었던 최단 경로의 결괏값이 그대로 사용될 수 있다는 점에서 다이나믹 프로그래밍을 적용하여 사용할 수 있습니다. 알고리즘 원리 위 그림에서 정점 1로부터 정점 2, 3, 4로의 최단 경로가 각각 5, 9, 13으로 설정되어 있습니다. 정점 1은 방문이 완료되었으므로 다음으로 가장 가까운 정점..

에라토스테네스의 체 (Sieve of Eratosthenes) 소수는 1보다 큰 자연수 중 1과 자기자신만을 약수로 가지는 수입니다. 특정한 자연수가 소수인지 아닌지는 다음과 같은 간단한 알고리즘을 통해 판별할 수 있습니다. // 소수 판별 O(N^(1/2)) #include using namespace std; bool isPrime(int x) { int rt = (int)sqrt(x); for (int i = 2; i > x; cout

[백준] 알고리즘 14852. 타일채우기 3 문제 2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. 예제 입력 1 1 예제 출력 1 2 예제 입력 2 2 예제 출력 2 7 예제 입력 3 3 예제 출력 3 22 다이나믹 프로그래밍의 2차원 배열 적용 문제. 타일 채우기 1 문항과 같은 알고리즘을 적용한다면 제한 시간 초과하여 비효율적인 문제가 발생. 타일의 N칸이 3칸 추가되는 경우부터는 두 경우의 나눌 수 없는 고유의 모양 배치가 계속해서 나타나므로 2차원적 다이나믹 프로그래밍 적용이 가능. 초기 값 arr[0][0], ..

[백준] 알고리즘 2133. 타일 채우기 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 2 예제 출력 1 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다. #include int arr[31]; int dp(int x) { if (x == 0) return 1; if (x == 1) return 0; if (x == 2) return 3; if (arr[x] != 0) return arr[x]; int result = 3 * dp(x - 2); for (int i = 3; i 1, (n - 2x) >= 0

[백준] 알고리즘 11727. 2xn 타일링2 문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력 1 2 예제 출력 1 3 예제 입력 2 8 예제 출력 2 171 예제 입력 3 12 예제 출력 3 2731 #include int i[1001]; int dp(int x) { if (x == 1) return 1; if (x == 2) return 3; if (i[x] != 0) return i[x]; return i[x] = (dp..

[백준] 알고리즘 11726. 2xn 타일링 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력 1 2 예제 출력 1 2 예제 입력 2 9 예제 출력 2 55 #include int i[1001]; int dp(int x) { if (x == 1) return 1; if (x == 2) return 2; if (i[x] != 0) return i[x]; return i[x] = (dp(x - 1) + dp(x - 2)..

다이나믹 프로그래밍 (Dynamic Programming) 직역하면 동적 프로그래밍으로 불리는 이 프로그래밍 방법은 큰 문제를 작은 부분으로 나누어 작은 부분들을 이용해 큰 문제를 해결하는 기법입니다. 이와 대조되는 분할 정복 알고리즘 역시 큰 문제를 한번에 처리하기에 연산 수가 크고 복잡하여 큰 문제를 작은 부분으로 나누는 기법입니다. 방법은 유사하지만 동적 프로그래밍은 작은 부분들을 다시 반복하여 연산하지 않는다는 차이점이 존재합니다. 즉, 큰 문제들을 작은 문제들로 나누는 과정은 동일하지만 분할 정복은 작은 문제들을 다시 연산하고 다이나믹 프로그래밍은 미리 연산된 결괏값을 재사용합니다. 다이나믹 프로그래밍에서 모든 작은 문제들은 반드시 한번만 사용하게 됩니다. 따라서 연산이 끝난 문제들은 어딘가에 ..

크루스칼 알고리즘 (Kruskal Algorithm) 크루스칼 알고리즘은 최소 비용 신장 트리(MST)를 만드는 데 사용되는 알고리즘입니다. 최소 비용 신장 트리란 가장 적은 최소한의 가중치(비용)로 모든 노드를 연결한 트리입니다. 즉, 여러 장소를 최소한의 비용으로 연결하고자 할 때 적용되는 알고리즘입니다. 우선 정점(노드) vertex과 간선 edge의 개념에 대해 알고 가야합니다. 그래프 자료구조에서 자세히 다루었으니 참고하시기 바랍니다. 알고리즘 원리 크루스칼 알고리즘의 동작 원리는 다음과 같습니다. 1. 최소 비용을 기준으로 간선을 오름차순 정렬 2. 사이클 확인 후 집합 생성 (사이클이면 사이클되는 간선을 배제함) 최소 비용 신장 트리의 경우 사이클이 생성되어서는 안됩니다. 사이클 여부는 유니..

합집합 찾기 알고리즘 (Union-Find) 서로소 집합(Disjoint-Set)이라고도 불리는 유니온 파인드는 서로 아무런 연결성도 없는 두 원소를 선택하여 그것들이 서로 같은 집합 내에 연결되어 있는 지 연결성을 확인하는 알고리즘입니다. 알고리즘 원리 위와 같이 6개의 아무런 연결성 없는 원소들이 존재할 때 각각의 원소들은 자기 자신의 집합에 속해있습니다. 원소 1은 집합 1에 속해있으며 원소 4는 집합 4에 속해있는 것입니다. 원소 1과 2를 연결하게 되면 이 둘을 Union 한 것이며 일반적으로 값이 더 작은 쪽으로 집합을 합치게 됩니다. 즉 원소 1과 2는 모두 집합 1에 속하게 되는 것입니다. 위 원리대로 볼 때 원소 2와 3을 연결하게 되면 원소 3은 집합 2에 속해야 할 것입니다. 하지만 ..

DFS 알고리즘 (Depth First Search) 깊이 우선 탐색(DFS)은 BFS와 달리 스택 자료구조를 사용하여 깊이를 우선적으로 탐색하는 알고리즘입니다. 또한 재귀적 함수로도 구현이 가능합니다. 위와 같은 이진 트리에 대하여 깊이 우선 탐색을 해보겠습니다. 깊이 우선 탐색은 기본적으로 노드를 스택에 넣고 인접한 노드 중 방문하지 않은 노드를 스택에 넣고 방문이 완료되었으면 다시 방문하지 않은 노드를 찾아서 스택에 넣는 방식입니다. 가장 먼저 방문하는 노드 1을 스택에 넣고 방문 완료(visited)합니다. 스택은 큐와 달리 나중에 들어온 것이 먼저 나가는 후입선출 방식입니다. 인접해있던 노드 2를 스택에 넣고 방문 완료합니다. 위 과정을 통해 노드 7까지 스택에 삽입되었다면 노드 7, 6, 3은..

BFS 알고리즘 (Breath First Search) 너비 우선 탐색 (BFS)은 큐 자료구조를 사용하여 너비를 우선적으로 탐색하는 탐색 알고리즘입니다. 흔히 최단 경로를 파악하여 최단 길이를 찾아낼 때 활용합니다. 순회의 순서로만 보면 이진 트리의 레벨 순회와 유사한 방식입니다. 위와 같은 이진 트리에 대하여 너비 우선 탐색을 해보겠습니다. 너비 우선 탐색은 기본적으로 '노드를 큐에넣고 -> 꺼내서 출력하고 -> 인접한 노드를 큐에넣고' 를 반복하는 알고리즘입니다. 가장 먼저 방문하는 노드1을 큐에 넣고 방문 완료(visited)합니다. 큐에 들어있던 1을 꺼내서 출력하고 인접해있던 노드 2와 3을 큐에 넣고 방문 완료합니다. 큐에서 먼저들어온 2를 꺼내서 출력하고 인접해있던 노드 4와 5를 큐에 넣..