플로이드-와샬 알고리즘이란? 다익스트라, 벨만포드 알고리즘과 더불어 대표적인 최단거리 찾기 알고리즘이다. 플로이드-와샬 알고리즘은 그 중에서도 모든 정점끼리의 최단거리를 한번에 계산할 때 사용한다. 즉, 다익스트라 알고리즘은 어떤 정점 A에서 다른 정점들까지의 최단거리를 계산한다면, 플로이드-와샬 알고리즘은 전체 정점에서 다른 정점들까지의 최단거리를 한번에 계산한다는 것이다. 다익스트라 알고리즘은 특정 정점을 중심으로 식을 계산시켜 나간다면, 플로이드-와샬 알고리즘은 계산을 위해 거쳐가는 정점을 중심으로 계산해나간다는 것이다. 또한, 플로이드-와샬 알고리즘의 중요한 특징 중 하나는 동적 계획법을 이용하여 최단 거리를 계산해나간다는 것이다. 동작 원리 위와 같은 초기 상황이 주어졌다고 가정하자. 일반적인 ..

1. 문제 2. 접근 방법 '알고리즘' 하면 빠질 수 없는 문제, '다이나믹 프로그래밍' 하면 빠질 수 없는 문제! 그 유명한 배낭 문제 (Knapsack Problem) 되시겠다. 나는 이 문제를 처음 접했을 때, 그러니까 대학교 3학년 시절에는 당연하게도 모든 경우의 수를 대입하는 무식한 방법을 택할 수 밖에 없었다. 그도 그럴 것이, 당시에는 DP의 개념도 몰랐었을 뿐더러 마땅한 해결책이 떠오르지 않았기 때문이다. 이렇게 문제를 풀었을 때는 각 물건 당 넣을지 안넣을지의 경우가 가능하므로, O(2^n) 이라는 어마어마한 시간 복잡도가 나오게 된다. 만약 물건이 100개라면 2의 100승이니까... 얼마나 무자비한 계산인지는 상상에 맡기겠다. 자! 그렇다면 본격적으로 다이나믹 프로그래밍의 개념을 적용..

1. 문제 2. 문제 풀이 다이나믹 프로그래밍 (DP) 문제이다. 현재의 상태를 저장시켜서 이를 지속적으로 활용하는 다이나믹 프로그래밍의 특성에 맞춰, 다음과 같은 문제 풀이 접근 방법을 활용하였다. '각각의 계단에 대해서, 이전 계단을 선택하는 경우와, 이전의 이전 계단을 선택하는 경우를 계산해나간다.' 즉, 각 계단에 대해서 다음의 알고리즘을 반복하는 것이다. (1) 이전 계단을 선택하는 경우, 이전 계단의 상태 중에서 '이전 계단을 선택하지 않았던 상태'를 선택할 수 있다. -> 이전 계단 중에서, '이전 계단을 선택했던 경우'를 선택하면 연속해서 세 계단을 오른 경우이므로 선택 불가 (2) 이전의 이전 계단을 선택하는 경우, 이전의 이전 상태 중 더 큰 값을 선택한다. -> 이전의 이전 계단의 경..

1. 문제 2. 문제 풀이 다이나믹 프로그래밍(DP)의 대표적인 유형 중 하나인 LIS 문제이다. 현재의 상태를 지속적으로 저장시켜서 문제를 푸는 DP의 특성을 이용하여 문제에 접근한다. 나의 경우에는 다음과 같은 방법을 고안했다. 각 값들에 대해서, 그 값까지 만들어지는 LIS를 지속적으로 저장시켜 나간다. 이 때, 현재의 LIS를 구하는 방법은 다음과 같다. '자신보다 작은 이전의 Value들에 대해서, 그때까지의 LIS가 가장 큰 값에 1을 더한다.' 즉, 각 LIS 값은 다음과 같은 조건으로 구한다. (1) 현재 LIS 값보다 이전의 값들에 대해서 (2) 현재 자신의 Value보다 작은 값들에 대해서 (3) LIS 값이 가장 큰 값을 구한 후, 그 값에 1을 더한 값으로 구한다. (4) 만약 조건..