알고리즘 문제 해결 전략을 읽고
(p.207 ~ p.225)
CH 08. 동적 계획법
8.1 도입
동적 계획법은 수학 이론에 근거하는데,
동적 계획법을 사용하는 알고리즘은 처음 주어진 문제르 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 낸다.
이는 분할정복과 비슷하다고 생각할 수 있지만 동적 계획법과 분할정복의 차이는 문제를 나누는 방식에 있다.
동적 계획법에서 어떤 부분의 문제가 두 개 이상의 다른 문제를 푸는데 사용될 수 있기 때문에 각 문제의 답을 메모리인 캐시에 저장해 둔다. 이렇게 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제라고 부른다.
동적 계획법의 가장 유명한 예는 이항 계수의 계산이다. 재귀 호출을 통해서 하나의 이항 계수를 계산할 때 값은 값을 두 번 이상 계산할 일이 빈번하다. 이렇게 모든 값을 계산하게 된다면 계산량을 낭비하는 일이다. 이를 방지하기 위해 동적 계획법이 쓰인다. 캐시 배열에 계산한 값을 저장해 두고, 그 값을 사용하여 계산한 새로운 값을 다시 캐시 배열에 저장한다. 이 방법을 사용하면 모든 부분 문제가 한 번씩만 계산된다고 보장할 수 있기 때문에 함수 호출 횟수가 매우 감소한다.
이와 같이 두 번 이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계 기법을 동적 계획법이라고 한다.
동적 계획법에서 쓰이는 최적화 기법 즉, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법을 메모이제이션이라고 부르는데, 이 메모이제이션은 입력이 같으면 항상 출력이 같은 참조적 투명 함수의 경우에만 적용할 수 있다.
메모이제이션 구현 패턴
- 기저 사례를 먼저 처리(ex.입력이 범위를 벗어난 경우)
- 캐시 배열을 -1로 초기화(반환 값이 음수가 아닐 경우)
- 참조 변수를 활용
- memset() 함수를 활용하여 배열 초기화
외발 뛰기 문제
정사각형의 게임판이 주어졌을 때 게임판의 끝에 도달할 수 있는지 확인하는 프로그램
- 문제를 재귀적으로 해결하는 완전 탐색 알고리즘 만들기
- 중복된 부분 문제를 한 번만 계산하도록 메모이제이션 적용하기
8.2 문제: 와일드카드
8.2 풀이: 와일드카드
와일드카드 패턴과 파일명의 집합이 주어질 때, 패턴에 대응되는 파일명들을 찾아내는 프로그램
- 문자 '*'에 따라서 탐색이 끝나는 경우를 나누기
- 각 경우에 대한 알고리즘을 만들고 완전 탐색 알고리즘에 메모이제이션 적용하기
