CS/Algorithms
-
[알고리즘] 동적 계획법(Dynamic Programming) - 기본CS/Algorithms 2020. 12. 9. 21:24
동적 계획법(Dynamic Programming) 짧게 줄여서 DP 라고 부르는 이 알고리즘은 분할정복(Divide and Conquer) 알고리즘과 마찬가지로 복잡한 문제를 여러 개의 부분 문제들(Sub-problem) 으로 나누어 푼 후, 그 결과를 이용하여 복잡한 문제를 푸는 알고리즘이다. 다만 분할정복 알고리즘과의 차이는 DP 에서는 각 부분 문제들간에 겹치는 부분이 존재한다는 것인데, DP 는 이러한 겹치는 부분들을 메모이제이션(Memoization) 이라는 기법을 사용하여 단 한 번만 계산하도록 함으로써 알고리즘의 작동 시간을 줄이는 게 핵심입니다. 그렇다면 메모이제이션이라는 것은 무엇인지 알아봅시다. 피보나치 수열을 예로 들면, 아래와 같이 Fib(0) ~ Fib(3) 은 동일한 값을 구하는..
-
[알고리즘] 재귀(Recursion) - 하노이탑CS/Algorithms 2020. 8. 4. 17:02
하노이의 탑은 3개의 기둥과 서로 크기가 다른 여러개의 원판들이 있을 때 이 원판들을 한 기둥으로부터 다른 기둥으로 옮기는 일종의 게임입니다. 게임을 시작하기 전 초기 상태는 3개의 기둥 중 하나의 기둥에 모든 원판들이 아래에서부터 크기가 큰 순으로 놓여져 있으며, 최종 목표는 이 원판들을 하나씩 옮겨서 순서 그대로 다른 기둥에 쌓는 것입니다. 이 때 2가지 규칙이 있습니다. 원판은 한 번에 한 개씩만, 기둥에서 기둥으로만 움직일 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 하노이탑은 재귀함수를 사용하여 해결할 수 있는 대표적인 문제입니다. 1, 2, 3번 기둥이 있고, n 개의 서로 다른 크기의 원판들이 있다고 할 때 1번 기둥에 쌓여져 있는 n 개의 원판들을 모두 3번 기..