C++: 동적 프로그래밍(Dynamic Programming)

동적 프로그래밍(Dynamic Programming)

• 이전의 계산 결과를 저장해 이후의 계산결과에서 다시 쓰는 기법
• 대략 다음과 같은 과정을 통해 최종 결과에 도달한다. 어찌 보면 재귀를 이용하는 브루털 포스와 유사하다고도 볼 수 있지만, 한 번 계산한 적이 있는 값을 다시 계산하는게 아니라 저장해놨다가 다시 사용한다는 점에서 차이가 있다.
  1. 문제가 무엇을 의미하는지 한 문장 수준으로 정의한다.
  2. 점화식, 큰 문제를 작은 문제들로 구성하도록 만든다.
  3. 가장 작은 문제에서의 결과를 나타낼 초기값을 설정한다.
  4. 답을 계산할지 아니면 기존에 계산했던 결과에서 꺼내올지 결정하며 최종 결과를 계산한다.

대표적인 문제

• 배낭문제

  • 특정 상황에선 그리디 알고리즘으로도 풀리겠지만, 대부분의 경우 DP가 더 효과
    1. 특정 가치와 무게를 가지는 물건이 여러개 있을 때, 배낭에 특정 무게만큼 넣을 수 있다면, 배낭에 넣을 수 있는 최대 가치는?
    • 가치, 무게, 2차원 추적 2. dp[i, w] = max(dp[i-1, w], dp[i-1, w - 무게] + 가치)
    • i번째에 물건을 넣을 때와 안넣을 때 어느 쪽이 더 가치있는지 확인 3. dp[0][w] = 0, dp[i][0] = 0
    • 아무물건도 안넣었을 때 가치 0, 용량이 0이면 가치 0 4. 확실한 내용부터 표 채워넣기, 모든경우의 수 계산보다 빠름!
    • ex 배낭 용량 7kg, 사과 2kg 5$, 복숭아 4kg 4$, 오렌지 3kg 6$, 수박 7kg 18$

  종류	0Kg	1Kg	2Kg	3Kg	4Kg	5Kg	6Kg	7Kg
  없을때	0	0	0	0	0	0	0	0 (dp[0][w])
  사과	0	0	5	5	5	5	5	5
  복숭아	0	0	5	5	5	5	9	9
  오렌지	0	0	5	6	6	11	11	11
  수박	0 (dp[i][0])	0	5	6	6	11	11	18

  • 수박만 넣어 오는게 제일 이득!

1. 최장 공통 부분수열(Longest Common Substring, LCS)

   • 순서를 지켜 뽑되, 떨어져있어도 되는 수열중 가장 긴 부분수열 찾기
     • Ex) “ABCDE” , “ABEDC” -> “ABD”
   • 배낭 문제처럼 표 채우기로 간단히 풀이 가능
     • 처음 모두 0에서 시작
     • 글자가 같으면 대각선 값 + 1
     • 글자가 다르면 왼쪽이나 위에서 큰 값으로
     • 끝까지 표 채우면 제일 오른쪽 최하단이 LCS 길이!

   	시작	A	B	C	D	E
   시작	0	0	0	0	0	0
   A	0	1	1	1	1	1
   B	0	1	2	2	2	2
   E	0	1	2	2	2	3
   D	0	1	2	2	3	3
   C	0	1	2	3	3	3

2. 편집거리 계산

   • 특정 문자열을 다른 문자열로 변환하기위해 필요한 삽입/삭제/교체 횟수의 총 합은?
     • ex)sunday -> saturday, 대체 2회, 삽입 1회
   • LCS와 비슷하게 해결가능!
     • 같으면 대각선 그대로 - 편집없음
     • 다르면 1+ min(위, 왼쪽, 대각선) -1회 편집
     • 선택지 총 3

   	시작	s	a	t	u	r	d	a	y
   시작	0	1	2	3	4	5	6	7	8
   s	1	0	1	2	3	4	5	6	7
   u	2	1	1	2	2	3	4	5	6
   n	3	2	2	2	3	3	4	5	6
   d	4	3	3	3	3	4	3	4	5
   a	5	4	3	4	4	4	4	3	4
   y	6	5	4	4	5	5	5	5	3

   • 총 편집거리 3!

3. LIS(Longest Increasing Subsequence)

   • 배열중에 증가하는 구간의 총 길이는? (LCS처럼 서로 떨어져있어도 괜찮음)
   • 이전 문제들보다 간단하게 해결 가능
     • dp[0] = 0
     • dp[i] = (앞구간에서 본인보다 작은값중 dp 최대값) + 1

   시작	10	30	4	31	56	78	54	100	32
   DP	1	2	2 (더작음)	3	4	5	5 (더작음)	7	7 (더작음, 최종)

활용

• 범용적으로 활용 가능하며 성능도 준수한 편으로 많은 용도로 사용되곤 한다.
• git diff - 파일간의 차이에서 공통적인 줄/문자열을 파악하고, 나머지를 +/-로 구분해 차이를 확인한다.
• 자원배분 문제 - 예산 배정, 생산라인 설계등 한정된 자원을 배분하는 대부분의 문제는 배낭 문제의 변형으로 표현 가능하다.
  • 클라우드 서버 장비 성능 결정
  • 투자 포트폴리오 분배
  • 광고, 팀 예산 분배 등등
• 게임
  • 인벤토리 배열 조합
  • 스킬 트리 포인트 분배
  • 대사 유사도 검출
  • 스피드런 행동 순서
• 웹/서버
  • 추천 시스템 유사도(LCS)
  • 광고 예산 배분
  • 방문 패턴 비교분석
• CS
  • 코딩 테스트에 자주 나오는 개념
  • DNA 서열 정렬(BLAST)
  • 음성 인식(비터비)
  • 맞춤법 및 자동완성 (LCS)
• 배낭문제, LCS, LIS, 편집거리 문제로 단순화 될 수 있는 많은 경우에 적용 가능하다.