[Hello Coding 알고리즘] 9. 동적 프로그래밍 dynamic programming

Bibi·2021년 7월 6일
algorithmalgorithm이론
0

Hello Coding 알고리즘

목록 보기
9/11

Hello Coding 알고리즘

9. 동적 프로그래밍 dynamic programming

배낭 채우기 문제 knapsack prolem

도둑이 4파운드의 짐을 넣을 수 있는 배낭에 값나가는 물건을 최대한 많이 훔치려 한다.

훔칠 수 있는 물건은 3종류

  • 스피커 : 4파운드, 3000달러
  • 노트북 : 3파운드, 2000달러
  • 기타 : 1파운드, 1500달러

훔친 물건의 총 가치를 최대한으로 하려면 어떤 물건들을 훔쳐야 하는가?

단순한 방법

모든 물건들의 조합과 총 가치를 모두 구한 다음, 가장 가치 높은 경우를 선택

단점 : 너무 느리다. O(2의n제곱). 물건이 하나 추가될 때마다 경우의 수가 2배가 된다. 2, 4, 8, 16, 32...

8장에서는 이 문제의 근사해를 구해 보았다(탐욕 알고리즘으로).

그렇다면 최적해는 어떻게 구할까?

동적 프로그래밍 dynamic programming

: 어려운 문제를 여러 개의 하위 문제로 쪼개고, 하위 문제들을 먼저 해결하는 방법.

  • 동적 프로그래밍은 어떤 제한 조건이 주어졌을 때, 무언가를 최적화하는 경우에 유용하다.
    • 배낭 채우기 문제에서, 제한조건=배낭의 크기, 목표=훔칠 물건 가치 최대화
  • 동적 프로그래밍은 하위 문제가 서로 의존하지 않는 경우에만 쓸 수 있다.

위의 배낭 채우기 문제에서는 - 더 작은 배낭(1파운드 배낭, 2파운드 배낭..)에 대한 문제를 풀고 이를 이용해 원래의 문제를 푼다.

  • 모든 동적 프로그래밍 알고리즘은 격자 grid에서 시작한다.

  • 격자의 각 칸에는 최적화하고자 하는 값을 적는다.

  • 격자의 칸 = 원래 문제에 대한 하위 문제이다.

    • 따라서 원래의 문제를 어떻게 하위 문제로 나눌 수 있는지를 생각해야 한다
    • 하위 문제는 또 다른 문제를 하위 문제로 가질 수 있다.

  • 격자를 모두 채우면 문제에 대한 답이 나온다.

  • 동적 프로그래밍의 해답을 계산해 주는 쉬운 공식 같은 것은 없다.

동적 프로그래밍 체크리스트

  • 각 칸에 넣을 숫자는 무엇인가?
  • 이 문제를 어떻게 하위 문제로 나눌 수 있는가?
  • 격자의 축은 무엇인가?

배낭 채우기 문제 풀이 - 동적 프로그래밍

---1234
기타
스테레오
노트북
  • 열 (1,2,3,4) : 1파운드 ~ 4파운드의 배낭을 나타냄
  • 행 (기타, 스테레오, 노트북) : 선택할 물건을 나타냄

기타를 표시하는 행

이 행에서는 기타만 넣을 수 있다. 결정할 수 있는 것은 기타를 넣을지 넣지 않을지 뿐이다.

  • 왜 4파운드짜리 배낭 문제를 풀면서 1파운드, 2파운드 배낭을 고민하는가? -> 더 큰 문제를 풀기 위한 작은 문제들을 풀고 있는 것.
---1234
G(기타)1500(G)1500(G)1500(G)1500(G)
S(스테레오)
L(노트북)

스테레오를 표시하는 행

---1234
G(기타)1500(G)1500(G)1500(G)1500(G)
S(스테레오)1500(G)1500(G)1500(G)3000(S)
L(노트북)

노트북을 표시하는 행

---1234
G(기타)1500(G)1500(G)1500(G)1500(G)
S(스테레오)1500(G)1500(G)1500(G)3000(S)
L(노트북)1500(G)1500(G)2000(L)3500(L+G)

마지막 칸의 값 구하기 - 아래 둘을 비교한다.

  • 현재까지의 최대 가치인 3000(S)
  • 추가된 행의 가치인 2000(L) + 1파운드의 무언가
    • 1파운드일 때 최대 가치는 무엇일까? - 이미 구함. 1500(G)
  • 따라서 새로운 최대 가치인 2000+1500 vs 기존 최대 가치인 3000 을 비교했을 떄 전자가 더 높다.

정리 - 왜 하위 문제로 나누어 푸는가?

: 작은 배낭(1,2 파운드)에 대한 최대 가치를 계산하면, 더 큰 배낭에 공간이 남게 되었을 때 작은 배낭에 대한 답을 사용하여 빈 공간의 가치가 최대가 되는 값을 찾을 수 있기 때문이다.

각 칸의 최대 가치를 구하는 공식 (배낭 채우기 문제)

칸[i][j]의 최대값 (i = 행, j = 열)

  • 지금까지 구한 칸[i-1][j]의 값 중에서 가장 최대값 (=세로줄 상의 최대값)

  • 또는 현재 물건의 가치 + 남은 공간의 가치

    • 이 때 남은 공간의 가치 = 칸[i-1][j-물건의 무게]

배낭 채우기 문제에서 자주 하는 질문

만약 물건이 추가되면 어떻게 하나?

  • 동적 프로그래밍은 점진적으로 답을 수정해 나가는 방법.
  • 따라서 물건이 추가되어도 처음부터 다시 풀 필요가 없다.
  • 예를 들어 훔칠 물건에 아이폰(1파운드, 2000달러)이 추가되면 - 아이폰을 나타내는 행을 추가해 각 칸의 최대 가치를 계산하면 된다.
1234
G(기타)1500(G)1500(G)1500(G)1500(G)
S(스테레오)1500(G)1500(G)1500(G)3000(S)
L(노트북)1500(G)1500(G)2000(L)3500(L+G)
I(아이폰)2000(I)3500(I+G)3500(I+G)4000(I+L)
  • 마지막 칸 구하기 - 아래 둘을 비교
    • 기존 최대 가치인 3500(L+G)
    • 추가된 행의 가치인 2000(1파운드) + 3파운드의 무언가
      • 기존 3파운드의 최댓값은 2000(L)이므로 이것을 더한다 = 4000.
    • 3500보다 4000이 크므로 새로운 최대 가치가 된다.

만약 행의 순서가 바뀌면 어떻게 되나?

행의 순서가 바뀌어도 답은 바뀌지 않는다.

격자를 행 방향이 아니라 열 방향으로 채워도 되는가?

배낭 채우기의 경우는 아무런 차이가 없지만, 다른 문제에서는 영향이 있을 수 있다.

만약 더 작은 물건을 추가하면 어떻게 되나?

만약 무게가 0.5파운드인 목걸이가 훔칠 수 있는 목록에 추가된다면?

  • 배낭의 종류를 1파운드 단위에서 0.5파운드 단위로 세분화해야 한다.

  • ---0.511.522.533.54

물건의 일부만 훔칠 수도 있는가?

전체를 훔치는 것이 아니라 일부만 훔칠 수는 없는가?

  • 동적 프로그래밍에서는 불가능하다. 물건 하나를 통으로 훔치거나 / 아예 훔치지 않거나 뿐이다.
  • 일부를 훔치는 경우, 동적 프로그래밍 대신 탐욕 알고리즘으로 쉽게 풀 수 있다.

여행 일정 최적화 문제

런던으로 휴가를 떠나는데, 이틀 동안 머물면서 가능한 많은 관광지를 돌고 싶다.

각 관광지마다 걸리는 시간과 보고 싶은 정도를 정하고 어떻게 코스를 짤지 정하는 문제.

= 배낭 채우기 문제와 같다.

  • 배낭이라는 공간 대신 시간이 한정됨
  • 훔칠 물건 대신 방문할 관광지가 있음

서로 의존적인 물건을 다룰 수 있나?

위의 여행 일정 최적화 문제에서, 관광지로 파리 여행도 추가하려 한다.

런던-파리는 반나절이 걸린다. 런던-파리를 오가는 경우 걸리는 시간에 1/2일을 더해야 한다.

  • 이 문제는 동적 프로그래밍으로 풀 수 없다.
  • 동적 프로그래밍은 각 하위 문제들이 서로 관계가 없을 때 (서로 의존하지 않는 경우)에만 사용할 수 있다.]

하위 문제가 두 개 이상인 경우도 있을 수 있나?

두 개 이상의 물건을 훔친다면 하위 배낭이 두 개 이상일 수도 있다. (하위 배낭이 그 안에 다시 하위 배낭을 갖는 식으로)

배낭을 완전히 채우지 못하는 경우도 있나?

배낭을 완전히 채우지 않더라도 그 경우가 최대 가치라면 그럴 수 있다.

최장 공통 부분 문자열 LCS, Longest Common Substring

사용자가 검색어를 실수로 잘못 입력했을 때, 대신 비슷한 단어들을 찾아 줌

실수로 입력한 검색어와 가장 유사한 단어를 후보로 보여주어야 한다. - 최장 공통 부분 문자열 또는 최장 공통 부분열을 구한다.

  • 최장 공통 부분 문자열 = 두 단어에서 공통적으로 가지는 가장 긴 부분 문자열.
    • 예를 들어 fish와 hish의 경우 ish라는 최장 공통 부분 문자열을 갖는다.
---hish
f0000
i0100
s0020
h1003
  1. 만약 두 글자가 다르면 값은 0이다.
  2. 만약 두 글자가 같으면 값은 '좌측 상단 칸의 값 + 1'이다.

최장 공통 부분 문자열 구하기 - 파이썬 코드

if wordA[i] == wordB[j]:
    cell[i][j] = cell[i-1][j-1] + 1
else:
    cell[i][j] = 0

❗ 이 문제의 경우 마지막 칸이 최종 답이 아니다. 답은 격자 전체에서 가장 큰 숫자이다. ( = 3, 즉 세 글자가 공통이다.)

최장 공통 부분열 Longest Common Subsequence

fosh라고 실수로 입력했을 때, fish를 검색하려던 것일까? fort를 검색하려던 것일까?

  • 공통으로 들어간 글자의 갯수가 더 많은 쪽일 것이다.
  • 최장 공통 부분열 = 순서가 바뀌지 않고 공통으로 들어간 글자의 개수.
    • fosh와 fish의 경우 f, s, h가 겹친다.
---fosh
f1111
i1111
s1122
h1123
  1. ([0][0]의 경우) 만약 두 글자가 같으면 1이고, 다르면 0이다.
  2. (나머지 칸의 경우) 위쪽 칸과 왼쪽 칸 중에서, 글자가 같지 않으면 둘 중 더 큰 값을 선택한다.
  3. (나머지 칸의 경우) 위쪽 칸과 왼쪽 칸 중에서, 글자가 같으면 '좌측 상단 칸의 값 + 1'이다.

최장 공통 부분열 구하기 - 파이썬 코드

if wordA[i] == wordB[j]:
    cell[i][j] == cell[i-1][j-1] + 1
else:
    cell[i][j] = max(cell[i-1][j], cell[i][j-1])

동적 프로그래밍의 활용

  • 생물학자 - DNA가닥의 유사성을 찾는 데 사용
  • git diff 명령에서 두 파일의 차이점을 찾는 데 사용
  • 두 문자열의 유사성을 측정할 때 사용 (레벤슈타인의 거리) - 표절 검사기, 맞춤법 검사기 ..
  • 워드 프로그램에서 줄 맞추기 기능에 사용됨
profile
Bibi
이전 포스트

[Hello Coding 알고리즘] 8. 탐욕 알고리즘 greedy algorithm

다음 포스트

[Hello Coding 알고리즘] 10. KNN 알고리즘 k-nearest neighbors algorithm

0개의 댓글