다이나믹 프로그래밍
한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘
컴퓨터는 연산 속도에 한계가 존재하고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이다.
우리는 컴퓨터의 제약된 연산 속도와 메모리 공간을 최대한 활용할 수 있는 알고리즘을 만들 수 있어야 한다.
다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.
프로그래밍에서의 다이나믹은 '프로그램이 실행되는 도중에' 라는 의미이다.
자료 구조에서 동적 할당은 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법이지만,
다이나믹 프로그래밍의 '다이나믹'은 이러한 의미는 아니다.
다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시는 피보나치 수열이다.
피보나치 수열은 점화식을 사용해서 표현이 가능한데, 점화식이란 인접한 항들 사이의 관계식을 의미한다.
피보나치 수열의 점화식
점화식을 이용해 현재의 항을 이전의 항에 대한 식으로 표현하였다.
피보나치 코드(재귀 함수로 표현)
피보나치를 그림으로 표현
만약 재귀 함수를 통해 피보나치 수열을 계산한다고 가정하고, 그림을 보면 f(n)의 n값이 커질 수록 반복해서 호출되는 수가 많아져서 연산량이 기하급수적으로 늘어난다.
이는 빅오 표기법으로 O(2^N)의 지수 시간이 소요되기 때문에 매우 비효율적이다.
이러한 문제는 다이나믹 프로그래밍을 통해 해결할 수 있다.
하지만 다이나믹 프로그래밍을 사용하기 위해서는 2가지 조건이 충족되어야 한다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 수열은 이러한 조건을 만족한다.
이 문제를 해결하기 위해서 메모이제이션 기법을 사용할 수 있다.
메모이제이션 기법이란?
다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과만 그대로 가져오는 기법이다.
메모이제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다.
단순히 한 번 구한 정보를 리스트에 저장한다.
다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때, 이미 구한 정답을 그대로 리스트에서 가져온다.
피보나치 수열 코드(재귀적, 메모이제이션 기법 사용, 탑다운)
99번째 피보나치 수를 구했음에도 짧은 시간을 소요하였다.
정리하면, 다이나믹 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘이다.
큰 문제를 작은 문제로 나누는 방식은 퀵 정렬에서도 사용되었다.
퀵 정렬은 정렬하고자 하는 리스트를 분할해면서 전체적으로 정렬되도록 한다. 이는 분할 정복 알고리즘으로 분류된다.
다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.
퀵 정렬은 기준이 되는 pivot이 자리를 변경 후, 자리를 잡게 되면, 기준 원소의 위치는 바뀌지 않고, pivot값을 변경하는 문제가 없다.
반면 다이나믹 프로그래밍은 한 번 해결했던 문제를 다시 해결한다는 점이 특징이다.
그렇기 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결됐기 때문에, 다시 해결할 필요 없이 결과만 반환하는 것이다.
왼쪽 사진에서는 피보나치 수를 구하기 위해, 이전에 수행됐던 연산들을 반복해서 수행하지만
오른쪽 사진은 이전에 수행됐던 연산들은 생략되고, 피보나치 수를 구한 값들을 저장해두어, 필요한 값들만 저장된 리스트에서 가져오는 것만으로 연산을 수행한다.
하지만, 재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하기 때문에 오버헤드가 발생할 수 있다.
그래서 재귀 함수 대신에 반복문을 사용하면 오버헤드를 줄일 수 있다.
일반적으로 반복문을 이용한 다이나믹 프로그래미잉 더 성능이 좋기 때문이다.
다이나믹 프로그래밍을 적용한 피보나치 수열 알고리즘의 시간복잡도는 O(N)이다.
위의 오른쪽 사진의 과정을 보면, 해당 피보나치 수를 구할 때, 바로 이전에 구한 결과를 사용하고 그 이후로는 구해지지 않기 때문이다.
f(1)을 구한 다음 그 값이 f(2)에 사용되고, f(2)에 값이 f(3)을 구하는데 사용되는 방식으로 이어진다.
위와 같이 재귀 함수를 이용하여 다이나믹 프로그래밍을 사용하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(top-down) 방식이라고 한다.
반면 단순히 반복문을 이용하여 작은 문제부터 차근차근 답을 도출하는 방식을 보텀업(bottom-up) 방식이라고 한다.
피보나치 수열 코드(반복적, 보텀업)
탑다운(메모이제이션) 방식은 "하향식" 이라고도 하며, 보텀업 방식은 "상향식"이라고도 한다.
다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.
보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.
다이나믹 프로그래밍과 메모이제이션의 개념을 혼용해서 사용하는 경우가 있다.
엄밀히 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념이므로, 다이나믹 프로그래밍과 별도의 개념이다.
메모이제이션이 다이나믹 프로그래밍이 아닌 다른 곳에서 활용될 수 있다.
다이나믹 프로그래밍 문제에 접근하는 방법
- 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토
- 다른 알고리즘으로 풀이 방법이 떠오르지 않거나 다른 알고리즘으로 풀이를 했더라도, 시간이 매우 오래걸리면 다이나믹 프로그래밍 방식을 고려. 해결하고자 하는 부분 문제들의 중복 여부 확인
- 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 물체에서 구한 답이 그대로 사용될 수 있으면, 코드를 개선하는 방법(메모이제이션 기법)을 사용
- 또한 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식을 구현하는 것을 권장
시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문
1로 만들기
문제 : 교재 217p 참고
피보나치 수열 문제처럼 점화식으로 표현할 수 있고, 점화식을 토대로, 보텀업 다이나믹 프로그래밍을 사용하여 접근이 가능하다.
나의 코드 (오답)
오답이다.
26을 입력했을 때, 3이 출력되어야 한다.
일단 보텀업 다이나믹 프로그래밍 방식으로 접근해야 한다고 생각했다.
그리고 2, 3, 5와 나누어 떨어지는 경우가 1씩 변화하는 것보다 연산 횟수를 더 줄여줄 것이라고 생각해서 일단 나눠지는 연산을 우선적으로 생각했고, 나누어 떨어지는 경우가 없을 때만, 1씩 변화한다고 가정하고 문제를 풀었다.
하지만 예상했던 결과가 나오지 않았고, 책의 예시를 보니 26에서 -1 연산을 먼저하고 진행하니, 연산수가 더 적은 결과가 있었다.
그래서 보텀업 방식에서 언제 적절히 +1을 먼저 계산해야하는가에 대해 고민하다가 결국 해결하지 못했다.....
해설을 참고한 코드
허무할 정도로 간단히 해결되는 문제였다.
우선적으로 +1 연산을 해서 해당 d[i]값을 이전의 d[i - 1]에서 연산 횟수 1을 증가시키고, 그 다음에 이전에 2, 3, 5와 나누어 떨어지는 경우의 d[i // ?]에 +1 한 값과 비교해서 더 적은 값을 선별하면 해결되는 문제였다.
개미 전사
문제 : 교재 220p 참고
왼쪽부터 차례대로 식량창고를 턴다고 가정하고, 몇몇개를 계산하다보면, 점화식을 세울 수 있다.
나의 코드 with 오답
위의 주석으로 처리된 코드가 이전의 나의 오답 코드이다.
주어진 예시 입력값과 출력값을 토대로 실행을 했을 때, 정상적으로 보였으나, 해설과 비교해보려고 했을 때, 뭔가 이상해서 예시 입력 뒤에 1을 추가로 넣었더니, 오답이 나와서 수정하였다. 좀 성급하게 푼 것 같다.
오답인 코드를 보면 위의 1로 만들기 문제와 비슷한 실수를 하였다.
1로 만들기 문제에서는 나누어 떨어지는 값은 나눗셈을 우선적으로 일단 연산하고 본다고 가정해서 푼 것처럼
식량창고의 마지막 창고를 무조건 턴다는 가정하에 계산을 하였기 때문이다.
무조건 현재 창고를 턴다고 가정하면, 바로 직전에 털었던 값들이 더 많더라도 현재 창고를 기준으로 갱신되기 때문이다.
왼쪽에서부터 전진하면서 해당 창고를 터는것이 이전에 털었던 양과 비교해서 이득인지 검사 후 선택하는 식으로 천천히 풀어나갔으면, 실수하지 않았을 텐데 아쉽다.
바닥 공사
문제 : 교재 223p 참고
왼쪽에서부터 차례로 그려가면서 풀다보면 점화식을 만들 수 있다.
나의 코드
해설과 큰 차이가 없어서 해설코드는 생략한다.
앞서 풀었던 문제들이 좀 도움이 됐다.
직접 그림을 그려서 앞의 개수를 세보니, 기존의 타일에서 1칸 늘어났을 때와 2칸 늘어났을 때가 반복되는 것이 보였다.
1칸 늘어났을 때는 2x1 타일 하나가 추가되는 경우만 존재하기 때문에, 늘어나는 경우의 수는 없고, 타일 2칸이 늘어났을 때는 2x1 타일1개, 1x2 타일 2개, 2x2 타일 1개 총 3가지의 경우의 수가 있으나, 2x1은 1칸 늘어났을 때의 경우의 수와 겹치기 때문에 생략한다. (이 부분 때문에 오답이 계속 출력됐었다.)
추가되는 타일의 개수에 따라 경우의 수가 각각 존재하기 때문에, 이에 맞게 점화식을 만들어주면 된다.
효율적인 화폐 구성
문제 : 교재 226p 참고
그리디에서 다루었던 거스름돈 문제와 유사하지만, 화폐 단위가 큰 단위가 작은 단위의 배수가 아니기 때문에 가장 큰 단위 화폐부터 나눠서 처리하는 방법으로는 해결할 수 없다.
나의 코드(오답)
나의 코드를 설명하자면, 일단 입력받은 화폐는 각 자기자신을 1개 사용한 값이기 때문에, 1로 초기화 하였다.
그리고 입력받은 화폐 리스트를 내림차순으로 정렬하였다.
보텁업 방식으로 1원부터 찾고자하는 m원까지 화폐 개수를 정의해 나가는데 만약, 해당 화폐가 내가 갖고 있는(입력받은) 화폐로 만들 수 있는 값인지 for문으로 리스트 내의 큰 값부터 비교하고, 만약 가능하다면, 연산횟수 1을 증가시켜주고 모든 화폐로도 만들 수 없는 값이라면 -1값을 넣어 구분해준다.
하지만 위 코드는 오답이다
2개의 입력값, 출력값 예시처럼 결과값이 나와서 정답인줄 알았는데, 해설코드와 비교해보고, 다른 값들을 입력해보니, 해설 코드와 다른 값이 출력되었다.
계속 똑같은 패턴으로 실수를 한다.....
오답인 이유는, money(입력값 리스트)에서 한번 계산되면 break하고 나가버리는 것이 문제이다.
이전에 더 낮은 횟수가 존재 할 수 있는데, 그 경우를 무시하고, 그냥 진행해서 생기는 문제이다.
해설을 참고한 코드
해설 코드는 본인의 코드와 다르게 입력된 모든 화폐로 계산하고 min()함수를 통해 더 작은 값을 추출해서 선정한다.
느낀점
난이도가 이전 것들과는 다르게 좀 어려웠고, 시간도 많이 걸린데다가 오답률이 너무 높았다.
해설 코드를 본 후, 어떤 부분에서 실수를 했지를 인지하고 다음 문제로 넘어가지만, 다른 문제에서도 풀지 못하고 해설을 참고하면 또 비슷한 개념을 실수한 경우가 자주 나왔다.
진짜 반성해야 할 부분이다. 무조건 다시 풀거다. 이 문제들에 대해 잊혀질 때쯤 또 풀어볼 것이다.
