플로이드-워셜 알고리즘 (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..