동적 프로그래밍

동적 프로그래밍

• 동적 프로그래밍은 부분 문제로 분해할 수 있는 최적화, 탐색, 계산 문제를 해결하기 위한 일반적인 방법을 말한다.
• 동적 프로그래밍을 효율적으로 작성하려면 반복해서 발생하는 하위 문제의 결괏값을 캐싱(cashing) 해두어야 한다.
• 동적 프로그래밍을 효율적으로 푸는 핵심은 하나의 문제를 부분 문제로 나누는 방법을 찾는 것이다.
  • 부분 문제의 해법을 찾으면 원래 문제도 비교적 쉽게 해결할 수 있다.
  • 부분 문제의 해법을 캐시에 저장할 수 있다.

예시

• 정수 배열이 주어졌을 때 합이 가장 큰 부분배열을 동적 프로그래밍으로 구해보자.
  1. 배열 A의 인덱스 i 이하의 모든 원소의 합계 최대 배열을 B라고 하자.
  2. 그러면 i를 포함해서 끝나는 최대 하위배열에 대한 두 가지 가능성만 존재한다.
     • 원소 A[i]이거나,
     • 이전 항목이 포함되는 경우 B[i-1] + A[i]다.
  3. 따라서 B[i] = max(A[i], B[i-1] + A[i])다.
• A : [1, 3, -7, 5]
• B : [1, 4, -3, 5]

알고 있어야 할 내용

• 문제가 부분 문제와 관련이 있는 경우는 더더욱 동적 프로그래밍을 고려하자.
• 개수를 세는 문제, 의사 결정 문제를 푸는 데도 쓸 수 있다.
• 캐시는 효율성을 위해 상향식, 즉 반복적으로 구축되는 경우가 많다.

핵심 이론

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다
2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다
3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다.
   • 이를 메모이제이션(memoization) 기법이라 한다
4. 동적 계획법은 top-down, bottom-up 방식이 있다.

풀이 방법

1. 먼저 동적 계획법으로 풀 수 있는지 확인한다.
2. 점화식을 세운다. 이 때 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는 훈련을 해두어야 한다.
3. 작은 문제들의 답을 메모이제이션 해서 다음에 다시 계산하지 않고 DP 테이블의 값을 이용하게 해주면 된다. 시간 복잡도 측면에서 많은 이점이 생긴다.
4. 톱-다운 구현 방식은 말 그대로 위에서부터 문제를 파악해 내려오는 방식으로, 주로 재귀 함수 형태로 구현한다. 코드의 가독성이 좋고, 이해하기가 편하다.
5. 바텀-업 구현 방식은 가장 작은 부분 문제부터 문제를 해결하며 점점 큰 문제로 확장해 나가는 방식이다. 주로 반복문의 형태로 구현한다. 톱-다운 방식은 재귀의 깊이가 깊어질 경우 런타임 에러가 발생할 수 있어 바텀-업 방식이 좀더 안전하다. 하지만 실제 코테에서 여까지 고려해야 하는 문제는 잘 나오지 않는다. 편한대로 쓰자.

---

문제 16.1 가능한 점수가 몇 개인지 구하기

미식축구는 각 게임당 2점(세이프티), 3점(필드골), 7점(터치다운, 추가점수)을 낼 수 있다. 최종 점수와 각 게임에서 낼 수 있는 점수가 주어졌을 때, 주어진 최종 점수를 만들 수 있는 조합의 개수를 반환하라.

해법

• 2차원 배열 A[i][j]에 W[0], W[1], … , W[i-1]의 조합으로 점수 j를 만들 수 있는 개수를 저장해 보자.

응용

- 같은 문제를 O(s)의 공간을 사용해 풀어 본다 - 최종 점수와 각 게임에서 낼 수 있는 점수가 주어졌을 때, 최종 점수를 만들 수 있는 수열의 개수를 반환하라. 예로 12점을 낼 수 있는 수열은 <2, 2, 2, 3, 3>, <2, 3, 2, 2, 3>, <2, 3, 7>, <7, 3, 2>를 포함해 총 열여덟가지 이다. - 최종 점수가 (s, s’)의 꼴로 주어진다고 가정하자. 1번 팀은 최종적으로 s점을 내고 2번 팀은 최종적으로 s’점을 낸다는 뜻이다. 이와 같은 결과를 만들 수 있는 서로 다른 점수 수열의 개수는 어떻게 구할 수 있을까? 예로 최종 점수 (6, 3)을 만들 수 있는 한 가지 방법은 1번 팀이 3점을 내고, 그 다음 2번 팀이 3점을 내고, 1번 팀이 다시 3점을 내는 것이다. - 최종 점수가 (s, s’)의 꼴로 주어졌을 때, 경기 중간에 역전되는 상황이 최대 몇 번이나 일어날 수 있는지 계산하라. 예를 들어 s = 10이고 s’=6일 때, 역전은 네 번 발생할 수 있다. 1번 팀이 2점 낸 뒤 2번 팀이 3점으로 역전, 1번 팀이 2점을 내서 다시 역전, 2번 팀이 3점을 내서 다시 역전, 1번팀이 3점을 내서 다시 역전, 마지막으로 1번 팀이 3점을 내면 10대 6으로 게임이 끝난다.

---

문제 16.2 레벤슈타인 거리 구하기

문자열 두 개가 입력으로 주어졌을 때, 첫 번째 문자열에서 두 번째 문자열로 변환하는 데 필요한 최소 편집 횟수를 구하라. - 편집에는 삽입, 삭제, 치환이 있다.

해법

• 먼저 두 문자열을 각각 행, 열로 하는 2차원 배열을 만든다.
• 마지막 바로 전의 최적해를 안다고 가정했을 때, 마지막 문자가 서로 같으면 + 0 하고 리턴
• 만약 다르다면,
  1. 두 문자 각 마지막 문자 바로 전까지 편집하고 난 후 치환
     • G[i][j] = G[i-1][j-1] + 1
  2. 첫 문자열 다 완성시키고 나서 나머지 한 문자열의 마지막 문자를 삭제
     • G[i][j] = G[i][j-1] + 1
  3. 첫 문자열의 마지막 문자를 빼고, 나머지 문자열을 모두 완성시키고 난 후 마지막 문자 삽입
     • G[i][j] = G[i-1][j] + 1

문제 3. 2차원 배열을 순회할 수 있는 방법의 개수 구하기

• 2차원 배열의 왼쪽 위에서 오른쪽 아래까지 순회할 수 있는 방법의 개수를 구하라.
• 오른쪽이나 아래로만 움직일 수 있다.

4. 이항계수 구하기

• 최종 결과를 정수형으로 표현할 수 있을 때 nCk를 계산하는 효율적인 알고리즘을 설계하라.

풀이 방법

• n개에서 k 크기의 부분집합을 고르는 것은..
  • n-1 개에서 k 크기의 부분집합 개수 +
  • n-1 개에서 k-1 크기의 부분집합 개수 (n을 포함시켜 k 크기로 만든다)
• 중간 결과를 캐시에 저장해 시간 복잡도를 줄이면 좋다.

5. 2차원 배열에서 수열 찾기

16.6 배낭 문제

• 가치와 무게가 정해진 여러 시계가 있다. 배낭의 무게 한도가 정해져 있을 때 가치가 최대가 되는 시계 집합을 구하라.

풀이

• 그리디로 풀 수 없다.
• 무게와 시계를 행과 열로 하는 2차원 배열을 먼저 만든다.
• 배열의 데이터는 해당 무게에서 해당 열까지의 시계를 조합한 최대 가치이다.
• V[i][w] = max( V[i][w] , V[i-1][w-wi]+vi ) 이다.

9. 합이 최대가 되도록 동전 선택하기

• 한 줄에 짝수 개의 동전이 있을 때,
• 두 플레이어가 번갈아 가며 동전을 하나씩 고른다.
• 더이상 고를 동전이 없을 때 겡미이 끝나며 이때 각자 고른 동전의 합이 더 높은 플레이어가 이긴다.
• 처음 시작하는 플레이어가 고른 동전의 합이 최대가 되도록 알고리즘을 설계하라

풀이 방법

• 양 끝의 동전 중 큰 가치를 고르는 선택같은 그리디는 해법이 아니다.
  • 선택의 결과가 다른 플레이어의 선택에 미치는 영향을 고려하지 않기 때문
• 점화식1
  • 양 끝 동전 중 하나를 골랐을 때, (그 동전의 가치) + (나머지 동전의 합) - (나머지 동전에서 얻을 수 있는 동전의 최대 가치)
• 점화식2
  • [a,b]구간이 주어졌을 때, a를 골랐다면, [a+1, b-1] 과 [a+2, b] 중 최소가 되는 값을 다른 플레이어가 선택할 것이고,
  • b를 골랐다면, 비슷하게 [a+1, b-1] 과 [a, b-2] 중 최소가 되는 값을 다른 플레이어가 선택할 것이다.
  • a 골랐을 때의 가치와 b를 골랐을 때의 가치 중 큰 가치를 선택하면 된다.

10. 계단 올라가는 방법 개수 구하기

• 한 번에 1~k개의 계단을 오를 수 있을 때 n번째 계단에 올라가는 방법의 개수를 구하라

11. 텍스트 예쁘게 배치하기

16.12 감소하지 않는 가장 긴 부분 수열 찾기

• 숫자 배열이 입력으로 주어졌을 때, 감소하지 않는 가장 긴 부분 수열의 길이를 반환하는 프로그램을 작성하라.

풀이

• 숫자 배열(A)의 길이만큼 최적해 배열(B)을 먼저 만든다.
• B[i]는 $j<i$ 를 만족하는 모든 j에 대해 $A[j]<B[i]$ 인 경우 B[i] = B[j]+1 이다.
  • 모든 j에 대해 $A[j]>B[i]$ 면 0.

---

이친수 구하기

이진수 중 0으로 시작하지 않고, 1이 두번 연속으로 나타나지 않는 이진수를 이친수(pinary number)라고 한다. N(1≤N≤90)이 주어졌을 때 N자리 이친수의 개수를 구하는 프로그램을 작성하라

풀이 방법

점화식은 다양할 수 있다. 여기선 2차원 배열 점화식 (D[N][2]) 을 선언하고 풀어 본다. D[i][0]은 i 길이에서 끝이 0으로 끝나는 이친수의 개수, D[i][1]은 i 길이에서 끝이 1로 끝나는 이친수의 개수이다.

연속된 정수의 합 구하기

• n개의 정수로 이뤄진 수열이 주어질 때, 연속된 몇 개의 수를 선택해 구할 수 있는 합 중 가장 큰 합을 구하라.
• 수는 1개 이상 선택해야 하며, 수열에서 수를 1개 제거할 수 있다.(제거하지 않아도 됨)

풀이 방법

• 가장 하기 쉬운 실수 중 하나가 점화식 정의를 잘못 하는 것이다. 이 문제에서 점화식의 정의를 ‘D[N] = 0에서 N까지 길이에서 연속으로 수를 선택하여 구할 수 있는 최대 합’이라 정의하면 안된다.
• ‘D[N] = 0에서 N까지의 길이에서 N을 포함했을 때 연속으로 수를 선택해 구할 수 있는 최대 합’이라고 정의해야 명확하다.
• 그리고 수 제거를 구현하기 위해 두 최대 연속합 배열을 이용한다.
  • 한 배열은 시작부분에서 시작해서 끝까지 최대합을 저장하고,
  • 다른 배열은 끝에서 시작해 시작부분까지 진행해 나가며 최대합을 저장해 나간다.
  • 그러면 i 인덱스의 수를 제거 했을 때 최대 합은 A[i-1] + B[i+1] 이겠죠

최장 공통부분 수열 찾기

LCS(longest common subsequence: 최장 공통부분 수열) 문제는 두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제다. 예로 acaykp와 capcak의 LCS는 acak가 된다.

문자열은 최대 1,000글자로 주어진다.

풀이 방법

먼저 이 문제를 풀기 위해 각 문자열을 축으로 하는 2차원 배열을 생성한다. 이 배열이 바로 점화식 테이블이 된다. 테이블에 저장되는 값은 각 위치 인덱스를 마지막 문자로 하는 두 문자열의 최장 공통 수열의 길이이다.

점화식은 특정 자리가 가리키는 행과 열의 문자열값을 비교해 값이 같으면 테이블의 대각선 왼쪽 위의 값에 1을 더한 값을 저장한다. 비교한 값이 다르다면 테이블의 왼쪽과 위쪽 값 중 큰 값을 선택해 저장한다.

최종적으로 정답을 출력하는데, 먼저 마지막부터 탐색을 수행하고, 해당 자리에 있는 인덱스 문자열값을 비교해 값이 같으면 최장 증가 수열에 해당하는 문자로 기록하고, 왼쪽 대각선으로 이동한다. 비교한 값이 다르다면 테이블의 왼쪽과 위쪽 값 중 큰 값으로 이동한다.

가장 큰 정사각형 찾기

• 이차원 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하라

풀이 방법

• D[i][j]를 사각형의 맨 오른쪽아래라고 생각해 보자.
  • 여기서 그릴 수 있는 사각형 중 가장 큰 사각형은 어떨까.
• 원래의 값이 1일 경우 왼쪽, 위, 왼쪽 대각선 위의 값 중 가장 작은 값에 +1 하는 방법이 있겠죠.

빌딩 순서 구하기

• 빌딩 N개가 1줄로 세워져 있다. 가장 왼쪽에서 봤을 때 보이는 빌딩의 수를 L, 오른쪽에서 봤을 때 보이는 빌딩의 수를 R 이라고 할 때, 가능한 빌딩 순서의 경우의 수를 구하는 프로그램을 작성하라.
• 예로 N=5, L=3, R=2 이면 가능한 배치 중 하나는 1 3 5 2 4 이다.

풀이 방법 (풀어보기)

• 우선 점화식은 D[N][L][R]
  • N개의 빌딩, L, R 에서 가능한 경우의 수

DDR 해보기

• 두 발을 이용해 누른다.
  • 중앙에서 발이 이동할 때는 힘이 2,
  • 중앙이 아닌 다른 지점에서 인접한 지점으로 이동할 때는 힘이 3,
  • 중앙이 아닌 다른 지점에서 인접하지 않은 지점으로 이동할 때는 힘이 4가 필요하다
• 눌러야 하는 방향 수열이 주어질 때 필요한 힘의 최솟값을 구하라.

풀이 방법

• 발이 두개다.
• 여기서는 mp[5][5] 를 정의해 한발을 이용해 드는 힘을 미리 정의해 둔다.
• 점화식은 D[N][L][R] -> N개의 수열을 진행했을 때 l, r에 발 위치가 있을 때 최소 힘

행렬 곱 연산 횟수의 최솟값 구하기

크기가 NM 인 행렬 A와 MK인 B를 곱할 때 필요한 곱셈 연산 횟수는 총 NMK번이다. 여러 행렬을 곱하는 데 필요한 곱셈 연산 횟수는 행렬을 곱하는 순서에 따라 달라진다. 행렬 N개의 크기가 주어졌을 때 모든 행렬을 곱하는 데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하라.

첫 줄에 행렬의 개수 N(1≤N≤500), 2번째 줄부터 N 개의 줄에는 행렬의 크기 r과 c가 주어진다. (1≤r, c≤500).

풀이 방법

먼저 문제가 어렵고, 점화식 구하기가 막막할 때는 동적 계획법의 특징인 부분 문제를 구해 큰 문제를 해결하는 방식을 떠올려야 한다. 1~N-1개의 행렬 까지의 필요한 최소 연산 횟수를 알고 있다고 가정하자. 그럼 1~N 구역의 최소 연산 횟수는 어떻게 될까.. 이를 점화식으로 나타내면 D[i][j] . i~j 구간의 행렬을 곱 연산하는데 드는 최소 연산 횟수이다.

D[1][N] = D[1][N-1] + D[N][N] + a 이다. a는 두 행렬을 합치는 데 드는 값이다. row * row*cloumn 이다.

행렬 구간에 행렬이 1개면 0을 반환하겠죠. 두개면 a. 3개 이상이면 시작 행렬부터 종료 행렬까지 반복하여 result = min(result, D[s][i] + D[i+1][e] + a) 계산을 하면 된다.

외판원의 순회 경로 짜기

N개의 도시가 있고 도시들 사이에는 길이 있을수도 없을 수도 있다. 모든 도시를 거치고 다시 원래의 도시로 돌아오되, 한번 갔던 도시로는 다시 갈 수 없다고 할때 가장 적은 비용을 들이는 여행 계획을 세워라. 비용은 행렬 W[i][j] 형태로 주어지며 대칭적이지 않다. W[i][i] 혹은 길이 없는 도시 사이는 W[i][j] = 0 이다.

첫 줄에 도시의 수 N이 주어진다 (2≤N≤16). N개의 줄에 비용 행렬이 주어진다. 각 값은 1,000,000 이하의 양의 정수이며 갈 수 없을 때는 0이 주어진다.

풀이 방법

외판원 순회 문제는 TSP(traveling salesman problem)라고 불리고, 가장 중요하게 취급되는 문제 중 하나이다. 여기서 N의 크기가 작으므로 완전 탐색 해보겠다. 점화식은 D[c][v]: 현재 도시가 c, 현재까지 방문한 모든 도시 리스트가 v일 때 앞으로 남은 모든 도시를 경유하는데 필요한 최소 비용 D[i][j]에서 j가 나타내는 것이 현재까지 방문한 모든 도시 리스트이다. 여기서 리스트 데이터 j를 변수 1개의 저장하는 방법으로 bit, 즉 이진수를 사용할 수 있다. 방문 도시를 이진수의 각 자릿수로 표현하고, 방문 시 1, 미방문 시 0의 값으로 저장한다. 먼저 점화식은 c번 도시에서 v 리스트 도시를 방문한 후 남은 모든 도시를 순회하기 위한 최소 비용이다. 현재 방문하지 않은 모든 도시에 대해 반복하고, 방문하지 않은 도시를 i라고 했을 때, W[c][v] = min(D[c][v], D[i][v | (1 << i)] + W[c][i]) 이다. 모든 도시 순회 판단 연산식은 if(v == (1 << N) - 1) 이며. N=4(도시의 개수가 4개)인 경우 (1 << 4) - 1 = 16 -2 = 15 이며, 15는 이진수로 1111이고, 모든 도시를 방문한 상태다. 방문 도시 확인 연산식은 if((v & (1 << i)) == 0) 이며, i=3(4번째 도시 확인 여부 확인) 인 경우 1 << 3 = 8 이며, 8은 이진수로 1000이고, v & 1000 연산 시 결괏값이 0이면 4번째 도시는 방문하지 않은 상태이다. 즉, v의 이진수 표현 시 4번째 자리가 1인 경우가 아니면 0을 반환하며 4번째 도시를 방문하지 않았다고 판단한다. 방문 도시 저장 연산식은 v | (1 << i) 이며, i=2(3번째 도시 저장) 인 경우 1 << 2 = 4 이며, 이진수로 100 이다. v | 100 연산을 수행하면 v의 이진수 표현 시 3번째 자리를 1로 저장하게 되어 3번째 도시를 방문하였다는 사실을 저장하게 된다. W 배열을 저장한 후, 점화식으로 정답을 구하고(도시를 순회하는 것이므로 어떤 도시에서 출발해도 상관없다), 최솟값을 정답으로 출력한다.

가장 길게 증가하는 부분 수열 찾기

수열 a가 주어졌을 때 가장 길게 증가하는 부분 수열을 구하는 프로그램을 작성하라. 예로 A={10, 20, 10, 30, 20, 50}일 때, 가장 길게 증가하는 부분 수열은 {10, 20, 30, 50} 이고 길이는 4다.

수열 a의 크기 N(1~1000000)

풀이 방법

점화식을 먼저 구해보자면 A[i]를 i번째 수열의 값이라고 정의하면 D[k]는 A[i] > A[j]를 만족하는 최대 수열의 길이이다. 즉, A[i]보다 작은 값을 지닌 수열의 최장 증가 수열의 길이 중 최댓값을 찾아 해당 값에 +1을 한 값을 D[i]에 저장하면 된다. D[i] = max({D[k]}) + 1 ( k = 1 ~ i - 1).

점화식을 이용해 D 배열의 값을 저장하며, 이 때 자신보다 작은 값을 지닌 최장 증가 수열 길이를 찾기 위해 B 배열을 만들어 현재 가장 유리한 수열을 실시간으로 저장한다.

D 배열을 이용해 정답을 출력하는데, 먼저 뒤에서부터 탐색해 최댓값과 동일한 값을 가지는 최초 index의 A[]값을 출력한다. 그리고 그 값을 1만큼 감소시키고 index가 1일 될 때까지 반복한다.

• D에는 해당 인덱스에서 최장 길이를 저장하고.
  • 이 최장 길이를 구하기 위해서는 B를 이용한다.
  • i의 숫자가 5라고 하고, B가 [1, 6, 10] 이면,
  • B의 6을 5로 바꾸고 D[i] = 2가 되는 것이다!
  • B에서 탐색하는 부분을 이진탐색으로 구현함으로써 효율성 극대화.

‘266가지 문제로 정복하는 코딩 인터뷰 - 아다드 아지즈, 쭝시엔 리, 아트 프라카시 지음 - 이창현, 김현욱 옮김’,
‘알고리즘 코딩테스트-c++편, 김종관 지음’ 책을 참고하여 작성한 포스트입니다.