다이나믹 프로그래밍 기출문제

19 Oct 2020 in Algorithm on Intermediate

• 1. 간단 정리
  • 다이나믹 프로그래밍
  • 피보나치 수열
  • 탑다운과 보텀업
• 2. 금광
  • 내가 작성한 코드
  • 모범답안
• 3. 정수 삼각형
  • 내가 작성한 코드
  • 모범답안
• 4. 퇴사
  • 내가 작성한 코드
  • 모범답안
• 5. 병사 배치하기
  • 내가 작성한 코드
  • 모범답안
• 6. 못생긴 수
  • 내가 작성한 코드
  • 모범답안
• 7. 편집 거리
  • 편집거리 알고리즘
  • 내가 작성한 코드
• 다이나믹 프로그래밍 문제 유형 및 생각해야할 점

1. 간단 정리

---

다이나믹 프로그래밍

한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법이다. 다이나믹 프로그래밍은 점화식을 그대로 코드로 옮겨서 구현할 수 있는데, 점화식이란 인접한 항들 사이의 관계식을 의미한다.

피보나치 수열

피보나치 수열 문제는 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 문제이다. 한 번 계산한 i번째 피보나치 수는 모두 1차원 리스트에 저장해 놓았다가 나중에 해당 i번째 피보나치 수를 구해야 할 때, 이전 단계에서 계산된 값을 바로 반환한다.
다이나믹 프로그래밍은 그 자체로도 다양한 문제로 출제될 수 있는 유형이지만, 그래프 이론 등 다양한 알고리즘에서도 자주 사용된다. 예를 들어 플로이드 워셜 알고리즘 또한 대표적인 다이나믹 프로그래밍을 활용한 알고리즘이다.

탑다운과 보텀업

다이나믹 프로그래밍을 이용한 소스코드를 작성하는 방법은 2가지가 있다. 탑 다운 방식은 재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식이다. 반면에 보텀업 방식은 단순히 반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식이다.

2. 금광

---

n * m 크기의 금광이 있다. 금광은 1 * 1크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다. 이후에는 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하시오.
입력 조건

• 첫째 줄에 테스트 케이스 T가 입력된다 (1<= T <=1000)
• 매 테스트 케이스 철째 줄에 n과 m이 공백으로 구분되어 입력된다. (1<=n,m<=20) 둘째 줄에 n * m 개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력된다. (1<= 각 위치에 매장된 금의 개수 <= 100)

출력 조건

• 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력한다. 각 테스트 케이스는 줄바꿈을 이용해 구분한다.

입력 예시
2
3 4
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2

출력 예시
19
16

내가 작성한 코드

t = int(input())

for _ in range(t):
    n,m = map(int,input().split())
    ls = []

    # 금광 입력
    data = list(map(int,input().split()))
    idx=0
    for i in range(n):
        ls.append(data[idx:idx+m])
        idx+=m

    # dp 프로그래밍
    for y in range(1,m):
        ls[0][y] += max(ls[0][y-1],ls[1][y-1])
        ls[1][y] += max(ls[0][y-1],ls[1][y-1],ls[2][y-1])
        ls[2][y] += max(ls[1][y-1],ls[2][y-1])

    print(max(ls[0][y],ls[1][y],ls[2][y]))

모범답안

이 문제는 2차원 테이블을 이용한 다이나믹 프로그래밍으로 해결할 수 있다. 금광의 모든 위치에 대하여 왼쪽 위에서 오는 경우, 왼쪽 아래에서 오는 경우, 왼쪽에서 오는 경우의 3가지 경우만 존재한다. 따라서 3 가지 경우 중에서 가장 많은 금을 가지고 있는 경우를 테이블에 저장해주어 문제를 해결할 수 있다. 내가 작성한 코드는 다이나믹 프로그래밍이라기 보다는 완전 탐색에 가까웠다. 여기서는 다이나믹 프로그래밍으로 코딩한다. 모든 경우를 확인하며 그 결과값을 저장해두고 나중에 다시 사용한다. 여기서 핵심은 리스트의 범위에 따라 경우를 나눠야 한다는 점이다.
점화식은 dp[i][j] = arry[i][j] + max(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1]) 이다.

# 테스트 케이스(Test Case) 입력
for tc in range(int(input())):
    # 금광 정보 입력
    n, m = map(int, input().split())
    array = list(map(int, input().split()))

    # 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
    dp = []
    index = 0
    for i in range(n):
        dp.append(array[index:index + m])
        index += m

    # 다이나믹 프로그래밍 진행
    # 0열이 아니라 1열부터 진행
    for j in range(1, m):
        for i in range(n):
            # 왼쪽 위에서 오는 경우
            if i == 0:
                left_up = 0
            else:
                left_up = dp[i - 1][j - 1]
            # 왼쪽 아래에서 오는 경우
            if i == n - 1:
                left_down = 0
            else:
                left_down = dp[i + 1][j - 1]
            # 왼쪽에서 오는 경우
            left = dp[i][j - 1]
            dp[i][j] = dp[i][j] + max(left_up, left_down, left)

    result = 0
    for i in range(n):
        result = max(result, dp[i][m - 1])

    print(result)

3. 정수 삼각형

---

문제 클릭

내가 작성한 코드

n = int(input())
tower = [[] for _ in range(n)]
# 타워 정보 삽입
for i in range(n):
    tower[i] = list(map(int, input().split()))

# 보텀업 방식
for i in range(n - 2, 0 - 1, -1): # 마지막에서 한 줄 위부터 시작
    for j in range(i + 1):
        tower[i][j] += max(tower[i + 1][j], tower[i + 1][j + 1])

print(tower[0][0])

모범답안

특정한 위치로 도달하기 위해서는 왼쪽 위, 바로 위 2가지 위치에서만 내려올 수 있다. 따라서 모든 위치를 기준으로 이전 위치로 가능한 2가지 위치까지의 최적의 합 중에서 더 큰 합을 가지는 경우를 선택하면 된다. 이전 문제와 마찬가지로 범위에 따라 경우를 나눠야 한다.
점화식은 dp[i][j] = drray[i][j] + max(dp[i-1][j-1],dp[i-1][j]) 이다.

n = int(input())
dp = [] # 다이나믹 프로그래밍을 위한 DP 테이블 초기화

for _ in range(n):
    dp.append(list(map(int, input().split())))

# 다이나믹 프로그래밍으로 2번째 줄부터 내려가면서 확인
for i in range(1, n):
    for j in range(i + 1):
        # 왼쪽 위에서 내려오는 경우
        if j == 0:
            up_left = 0
        else:
            up_left = dp[i - 1][j - 1]
        # 바로 위에서 내려오는 경우
        if j == i:
            up = 0
        else:
            up = dp[i - 1][j]
        # 최대 합을 저장
        dp[i][j] = dp[i][j] + max(up_left, up)

print(max(dp[n - 1]))

cf) 2,3번에서 배운점
계산 결과를 누적해서 사용하는 다이나믹 프로그래밍, 보텀업 방식을 사용할 때는 생각의 시작을 시작점이 아니라 시작점 바로 하나 위에서 생각을 시작하는 것이 설계에 도움이 되는 것 같다.

4. 퇴사

---

문제 클릭

내가 작성한 코드

이런 누적문제를 보면 인덱스값마다 0~해당 인덱스까지의 최대값을 넣고 마지막 인덱스를 출력하면 되겠다는 생각이 들어야 한다. dp문제는 맨 처음보다 딱 하나 위에서 부터 점화식을 생각해보면 쉽게 해결할 수 있다. 복잡하게 점화식을 어떻게 해야하지부터 생각하지 말고, 해당 인덱스에는 최댓값이 들어있다고 무작정 가정하고 코딩을 하면 자연스럽게 해당 인덱스에 최댓값이 들어있도록 코딩할 수 있다. 일단 코딩을 하면서 어떻게든 해당 인덱스에 최댓값이 들어있다고 가정하고 코딩을 하는 것이 중요하다.
가정을 했다면 현재 인덱스에서의 최댓값을 구할때는 바로 전 인덱스에 최대값이 들어있으니 현재 인덱스에서의 최댓값은 앞에 인덱스를 사용하면 되겠구나 라는 생각이 떠오르게 되고 코딩이 더 쉬워진다.

n = int(input())
day = [0]
pay = [0]
ans = [0] * (n + 1)

# 입력
for i in range(1, n + 1):
    d, p = map(int, input().split())
    day.append(d)
    pay.append(p)

for idx in range(1, n + 1):
    if day[idx] == 1:
        ans[idx] = max(ans[idx - 1] + pay[idx], ans[idx])
    else:
        ans[idx] = max(ans[idx - 1], ans[idx])
        next = idx + day[idx] - 1
        if next <= n:
            ans[next] = max(ans[idx - 1] + pay[idx], ans[next])

print(ans[n])

위와 같이 풀이할 수도 있지만, 방법이 한가지 더 있다.
다이나믹 프로그래밍의 사고의 시작은 맨 앞에서 조금 뒤, 맨 뒤에서 조금 앞에서 점화식을 세우고 시작점에서 다른 점화식과 다른경우 시작점을 따로 처리해주는 방식으로 사고하면 쉽게 풀린다.
일반적은 DP 문제의 경우, 일반적인 누적의 경우 처음부터 끝으로 가면서 누적해서 마지막 인덱스의 값으로 최대값을 저장하면 쉽게 풀린다.
반면에 이 문제는 끝점이 명확하게 정해져 있지 않다.
그렇다면 역으로 생각해서 끝점이 명확하게 지어져 있는 1을 끝점이라고 생각하고 역으로 올라갈 수 있다.
정리하자면, 일반적인 경우 처음부터 끝까지 누적해나가면 되지만, 끝이 입력된 값에 범위를 초과하는지 검증이 필요한 경우라면 마지막 입력을 연산의 시작점으로 두고 첫 입력값을 누적의 끝으로 생각하면 된다.
일반적인 경우에 첫번째 식 처리를 위해 맨 앞에 더미 값을 주는 것처럼 마지막을 시작점으로 두게 되면 끝점이 시작점이 되므로 끝에 더미값을 추가해주어야 한다.

n = int(input())
day = [0]
pay = [0]
ans = [0] * (n + 2)

# 입력
for i in range(1, n + 1):
    d, p = map(int, input().split())
    day.append(d)
    pay.append(p)

for idx in range(n, 0, -1):
    next = day[idx] + idx - 1

    if next <= n:
        ans[idx] = max(ans[next + 1] + pay[idx], ans[idx + 1])
    else:
        ans[idx] = ans[idx + 1]

print(ans[1])

모범답안

이 문제는 뒤쪽 날짜부터 거꾸로 확인하는 방식으로 접근하여 해결하는 다이나믹 프로그래밍의 아이디어를 떠올릴 수 있다. 거꾸로 계산하는 방식을 떠올릴 수 있는 이유는 끝이 확실히 정해지지 않았기 때문이다. 따라서 입력받은 것을 토대로 끝을 확인한 다음 끝에서부터 시작하는 것이다.
예시를 기준으로 생각해보자. 1일 차에 상담을 진행한다고 해보자. 이 경우 3일에 걸쳐 상담을 진행해야 한다. 결과적으로 4일부터 다시 상담을 진행할 수 있다. 그러므로 1일 차에 상담을 진행하는 경우, 최대 이익은 1일차 부터의 상담 금액 + 4일부터의 최대 상담 금액이 된다. 따라서 이러한 원리를 이용하여 뒤쪽 날짜부터 거꾸로 계산하며 문제를 해결할 수 있다. 즉, 뒤쪽부터 매 상담에 대하여 현재 상담 일자의 이윤(p[i]) + 현재 상담을 마친 일자부터의 최대 이윤 (dp[t[i] + i])를 계산하면 된다. 이후에 계산된 각각의 값 중에서 최댓값을 출력하면 된다.
dp[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대 이익이라고 하면 점화식은 dp[i] = max(p[i] + dp[t[i]+i],max_value)가 된다. 이때 max_value는 뒤에서부터 계산할 때, 현재까지의 최대 상담 금액에 해당하는 변수이다.

n = int(input())
days = [0] # 인덱스 맞추기위해 0넣고 시작
pays = [0] # 인덱스 맞추기위해 0넣고 시작

# 현재 인덱스부터 끝까지의 최댓값을 구하는 저장소
# 설계를 생각해보면 인덱스 맞추기 위해 +1 해줘야 되고, 
# 설계한 알고리즘에 따라 맨 뒤에도 한 칸 늘리기 위해 +1 해줘야 한다.
# 설계한 알고리즘을 맨 뒤에서 조금 앞에서 생각해 보면
# 해당 위치에서의 최대값은 소요하는 날짜 + 끝난 날짜 이후의 최댓값
# 이렇게 설계하고 맨 뒤쪽을 확인해보면 맨 뒤가 1일 소요의 경우 끝난 날짜 이후 최댓값은 
# out of index이므로 맨 뒤에 0을 추가로 넣어준다.
ans = [0] * (n + 2) 
max_value=0 # 최댓값
for _ in range(n):
    day, pay = map(int, input().split())
    days.append(day)
    pays.append(pay)


for i in range(n,1-1,-1):
    idx = i+days[i]-1 # 일이 끝난 위치
    # 일이 끝난 위치가 범위 내이면
    if idx<=n:
        ans[i] = max(pays[i]+ans[idx+1],max_value)
        max_value = ans[i] # 최대값 수정
    # 일이 끝난 위치가 범위 밖이면
    else:
        ans[i]=max_value

print(ans[1])

배운점
누적 계산 문제는 다이나믹프로그래밍처럼 탑다운방식이나 보텀업 방식의 점화식으로 풀이가 가능하다. 내 풀이는 보텀업 방식으로 풀었고 답안은 탑다운 방식으로 풀었다. 누적 계산 문제는 어떤 문제는 보텀업 방식이, 어떤 문제는 탑다운 방식이 좋을 때가 있다. 보통 보텀업 방식이 흐름상 가장 먼저 생각해 낼 수 있다. 두 가지 방식을 생각하면서 더 쉬운 풀이가 어느쪽 일까 고민해서 선택하면 될 것 같다. 이 문제와 같이 경우마다 끝나는 위치가 다른 경우는 탑다운 방식으로 먼저 거꾸로 생각해 보는게 좋은 것 같다. 또한, 누적 문제는 항상 해당 인덱스 내부값을 최대, 최소로 고려하고 생각해보자. 항상 보텀업, 탑다운 방식을 생각할 때는 맨 앞, 맨 뒤를 생각하는게 아니라 맨 앞에서 조금 뒤쪽, 맨 뒤에서 조금 앞쪽을 우선적으로 생각해서 점화식을 잡고 나중에 맨 앞, 맨 뒤를 고려하여 수정하는 작업을 해야 한다.

5. 병사 배치하기

---

문제 클릭

내가 작성한 코드

앞서 말했듯이 다이나믹 프로그래밍, 누적문제는 점화식에 해당 가정 을 가지고 시작하는게 좋다고 했다. 누적문제이므로 당연히 누적을 저장할 리스트를 만드는 생각을 했고, 이 리스트의 값에 어떤 것을 넣을지 생각해야 한다.
누적문제에서는 누적 리스트에 어떤 누적 값을 넣을지 고민해야 한다.
무작정 해당 인덱스에서의 누적 최대, 최소값을 넣는게 아니라 문제에서 주어진 병사의 전투력을 최소로 하는 길이의 누적 최대값을 넣어야 한다.

n = int(input())
soldier = list(map(int, input().split()))
ans = [1] * n

# 끝이 정해져있는 일반적인 문제
# 감소수열의 최대 길이
# 각 위치를 최소값으로 갖는 감소수열 최대 길이값으로 지정 
for i in range(1, n):
    for j in range(1, i):
        if soldier[i] < soldier[j]:
            ans[i] = max(ans[i], ans[j] + 1)

print(n - max(ans))

모범답안

이 문제의 기본 아이디어는 가장 긴 증가하는 부분 수열로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어 와 같다. 가장 긴 증가하는 부분 수열 문제란 하나의 수열이 주어졌을 때 값들이 증가하는 형태의 가장 긴 부분 수열을 찾는 문제이다. 감소하는 수열의 최대 길이는 감소하는 수열을 뒤집어서 증가하는 수열의 최대 길이를 구하는 것과 같다.
예를 들어 하나의 수열 array = [10,20,10,30,20,50]이 있다고 하자. 이때 가장 긴 증가하는 부분 수열은 {10,20,30,50}이 될 것이다. dp[i]는 array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이라고 정의하면, 가장 긴 증가하는 부분 수열을 계산하는 점화식은 다음과 같다. 이때 초기의 dp 테이블의 값은 자기 자신을 수열의 개수로 카운트 한다는 의미로 모두 1로 초기화한다. 모든 0 <= j < i 에 대하여, d[i] = max(d[i],d[j]+1) if array[j] < array[i], 풀어서 말하면, 현재 위치 i보다 작은 0부터 i-1까지의 리스트값을 비교하여 i리스트값이 더 큰 경우 dp를 max를 통해 갱신한다는 것이다. 결과적으로 테이블에 남아있는 값 중에서 가장 큰 값이 가장 긴 증가하는 부분 수열의 길이가 된다.
좀 더 생각해보자. 보텀업 방식으로 앞에서부터 시작해보자. dp[i]에는 인덱스값이 i보다 작은 것들 중에서 최대값을 리스트i의 값으로 하는 수열의 최대 길이가 들어있다. 이유는 for문을 0부터 돌려려서 최대값이 수정되면서 해당 길이가 계속 갱신되기 때문이다. 그럼 dp[i+1]는 어떤가? 인덱스 값이 i+1보다 작은 것들 중에서 실제 값이 작다면 dp[i+1] = max(dp[i+1],dp[i+1보다작 값]+1)를 하게 되면 dp[i+1보다작은값]안에는 이미 해당 값보다 작은 값들로 구성된 수열의 최대 길이가 들어있고 거기다가 i+1의 실제값은 그것보다 크니 +1 해주고 max비교를 하면 결국 dp[i+1]은 해당값을 최대로하는 수열의 최대 길이를 알 수 있게 된다.
이러한 방식을 문제에 적용해보자. 현재 문제는 병사를 배치할 때 전투력이 높은 병사가 앞쪽에 오도록 내림차순 배치를 하고자 한다. 따라서 이 문제를 가장 긴 감소하는 부분 수열의 길이를 계산하는 문제로 간주하고, 입력으로 주어진 원소의 순서를 뒤집은 뒤 가장 긴 증가하는 부분 수열 문제를 풀 때의 점화식을 그대로 적용하면 풀 수 있다.
정리하자면, 문제는 감소하는 수열의 최대 길이를 구하는 것이므로 받은 입력을 뒤집어서 증가하는 수열의 최대 길이를 구하는 것과 같은 문제이다.

n = int(input())
soldier = list(map(int, input().split()))[::-1]
dp = [1] * n

# dp[i]에는 soldier[i]를 최대값으로 하는 수열의 최대 길이가 들어있다는 가정
# 인덱스 0부터 차례로 dp값을 수정해나가므로 soldier[j]<soldier[i] 값만 비교해도
# 증가하는 수열이다.
# 이 가정대로 코드를 작성했기 때문에 확인해보면 dp에는 수열의 최대 길이가 들어가있다.
for i in range(n):
    for j in range(i):
        if soldier[j] < soldier[i]:
            dp[i] = max(dp[j] + 1, dp[i])

print(n - max(dp))

6. 못생긴 수

---

못생긴 수란 오직 2, 3, 5만을 소인수로 가지는 수를 의미한다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 말한다. 1은 못생긴 수라고 가정한다. 따라서 못생긴 수들은 {1,2,3,4,5,6,8,9,10,12,15..}순으로 이어지게 된다. 이때, n번째 못생긴 수를 찾는 프로그램을 작성하시오.
입력 조건

• 첫째 줄에 n이 입력된다. (1<=n<=1000)

출력 조건

• n번째 못생긴 수를 출력한다.

입력 예시
10
출력예시
12
입력예시
4
출력예시
4

내가 작성한 코드

n = int(input())
ugly=[1]
cnt=1

idx2=0
idx3=0
idx5=0

while cnt != n:
    a = ugly[idx2] * 2
    b = ugly[idx3] * 3
    c = ugly[idx5] * 5
    value = min(a,b,c)

    if value == a:
        idx2+=1
    elif value == b:
        idx3+=1
    else:
        idx5+=1

    if value not in set(ugly):
        ugly.append(value)
        cnt+=1

print(ugly.pop())

모범답안

이 문제는 못생긴 수를 앞에서부터 하나씩 찾는 방법으로 해결할 수 있다. 못생긴 수들은 끊임없이 존재하는데 이때 못생긴 수에 2,3,5를 곱한 수도 또한 못생긴 수에 해당한다는 점이 포인트이다.
답안을 보고 생각을 정리해보았다. ugly수는 2,3,5를 기반으로 하는 수이다. 2,3,5 이후의 ugly수는 당연히 ugly수들의 곱으로 이루어진다. 그렇다면 ugly수마다 ugly수를 일일이 전부 곱해야 할 필요가 있는가? -> 아니다. 어쩌피 2,3,5 이후의 어글리 수들은 2,3,5로 만들어진 수. 어글리수에 2,3,5 이후에 수를 곱한다는 것은 결국 의미가 없다. 만약 어글리수가 15까지 만들어졌다고 하면 2에다가 15를 곱해서 어글리수를 만들 필요가 없다. 15는 3과 5로 만들어진 어글리수이다. 2에 3을 곱해서 만든 어글리수에 5를 곱한것과 같다. 따라서 모든 어글리수에는 2,3,5만 곱해서 최소값을 어글리 리스트에 넣어주면 되는 것이다.

n = int(input())

ugly = [0] * n # 못생긴 수를 담기 위한 테이블 (1차원 DP 테이블)
ugly[0] = 1 # 첫 번째 못생긴 수는 1

# 2배, 3배, 5배한 인덱스의 위치
i2 = i3 = i5 = 0
# 2,3,5를 곱한 결과값
next2, next3, next5 = 2, 3, 5

# 1부터 n까지의 못생긴 수들을 찾기
for l in range(1, n):
    # 가능한 곱셈 결과 중에서 가장 작은 수를 선택
    ugly[l] = min(next2, next3, next5)
    # 인덱스에 따라서 곱셈 결과를 증가
    # 여기서 이해가 조금 어려웠는데 처음부터 예시를 들어보면
    # ugly[1]=2가 될 것이고 첫번째 if문이 실행되어 i2=1이 되고 next2값이 변경된다.
    # 즉, ugly의 1번 인덱스는 2배처리를 완료했다는 것이고, 다음에는 인덱스2의 값을 2배처리.. ~~ 하는 것이다.
    # 그럼 1번 인덱스는 이제 3,5배처리를 해야할텐데 그 동작은 제일 작은 것으로 선택될때 수행된다.    
    if ugly[l] == next2:
        i2 += 1
        next2 = ugly[i2] * 2
    if ugly[l] == next3:
        i3 += 1
        next3 = ugly[i3] * 3
    if ugly[l] == next5:
        i5 += 1
        next5 = ugly[i5] * 5
    # next끼리 같은 경우가 있을 수 있으므로
    # 한 번만 넣기 위해 elif를 쓰지 않고 if를 써야함

# n번째 못생긴 수를 출력
print(ugly[n - 1])

7. 편집 거리

---

두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 한다. 문자열 A를 편집할 때는 다음 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있다.

• 삽입 : 특정한 위치에 하나의 문자를 삽입한다.
• 삭제 : 특정한 위치에 있는 하나의 문자를 삭제한다.
• 교체 : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체한다.

이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미한다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요. 예를 들어 sunday와 saturday의 최소 편집 거리는 3이다.
입력 조건

• 두 문자열 A와 B가 한 줄에 하나씩 주어진다.
• 각 문자열은 영문 알파벳으로만 구성되어 있으며, 각 문자열의 길이는 1보다 크거나 같고, 5,000보다 작거나 같다.

출력 조건

• 최소 편집 거리 출력

입력 예시
cat
cut

출력예시
1

입력예시
sunday
saturday

출력예시
3

편집거리 알고리즘

자세한 알고리즘 참조

이 문제는 최소 편집 거리를 담을 2차원 테이블을 초기화한 뒤에, 최소 편집 거리를 계산해 테이블에 저장하는 과정으로 문제를 해결할 수 있다. 점화식은 다음과 같다.

• 두 문자가 같은 경우 : dp[i][j] = dp[i-1][j-1]
  • 행과 열에 해당하는 문자가 서로 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
  • 두 문자가 같기 때문에 작업이 필요 없으므로 바로 전의 열과 행에서 비교한 값을 그대로 가져오면 된다.
• 두 문자가 다른 경우 : dp[i][j] = 1 + min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
  • 삽입 : 왼쪽 값 + 1
  • 삭제 : 위쪽 값 + 1
  • 교체 : 왼쪽 대각선 값 + 1

예를 들어 sunday를 saturday로 변경한다고 해보자. 이때 초기 2차원 테이블은 다음과 같이 구성된다. 왼쪽(열)에 있는 sunday라는 문자열을 위쪽(행)에 있는 saturday로 변경하는 비용을 계산할 수 있도록 이와 같이 테이블을 구성한 것이다. 또한 여기서 0은 빈 문자열을 의미한다. 빈 문자열을 saturday로 만들기 위해서는 8개의 문자를 삽입해야 하기 때문에 테이블의 dp[0][8]의 값은 8이다.

비고	0	s	a	t	u	r	d	a	y
0	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	4	3

처음 접하게 된다면 점화식을 이해하기가 힘들다. 하나씩 생각해보자.
su 와 saturday를 비교해보자.

1. su를 s로 만들기 위해서는 u를 지워야 하므로 s를 s로 만들기 위해 사용한 편집거리에서 u를 지우기 위한 동작 +1 이다.
   • 즉, 위에 값 +1이다.
2. su를 sa로 만들기 위해서는 u를 교체해야하므로 s를 s로 만들기 위해 사용한 편집거리에서 u를 교체하기 위한 동작 +1 이다.
   • 즉, 왼쪽 대각선 값 + 1이다.
3. su를 sat로 만들기 위해서는 su를 sa로 고치는 과정값 + t를 추가하는 과정이다.
   • 즉, 왼쪽 값 + 1 이다.
4. su를 satu로 만들기 위해서는 마지막 u가 일치하므로 s를 sat로 만드는 편집거리를 그대로 가져오면 된다.

이러한 과정이 반복되면 다음과 같은 규칙을 찾을 수 있다.

• 비교하는 문자가 일치할 경우, 왼쪽 대각선의 값을 그대로 가져온다.
• 비교하는 문자가 불일치하면, 왼쪽, 왼쪽 대각선, 위에 값중 최소값 +1 처리한다.

내가 작성한 코드

a = input()
b = input()
n = len(a)
m = len(b)

dp = [[0] * (m + 1) for _ in range(n + 1)]
# 빈문자열로 a 만들기
for i in range(n + 1):
    dp[i][0] = i

# 빈문자열로 b만들기
for j in range(m + 1):
    dp[0][j] = j

for i in range(1, n + 1):
    for j in range(1, m + 1):
        # 일치한다면 전에 비교했던것 그대로 가져오기
        if a[i - 1] == b[j - 1]:
            dp[i][j] = dp[i - 1][j - 1]
        else:
            # 일치하지 않는다면 전에 비교했던 것에서 삽입 삭제 교체 중 최소값으로 선택
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

print(dp[n][m])

다이나믹 프로그래밍 문제 유형 및 생각해야할 점

• 접근 방식(점화식 세우는 법)
  • 사고의 시작은 맨 앞에서 조금 뒤 또는 맨 뒤에서 조금 앞에서 점화식을 세우고 시작점에서도 점화식이 성립하도록 앞 또는 뒤쪽에 더미를 하나 추가한다. 만약 시작점이 예외적으로 다른 점화식과 다른경우 시작점을 따로 처리해주는 방식으로 사고하면 쉽게 풀린다.
  • 사고가 어렵다면 무작정 앞의 인덱스 안에 값이 최대,최소 값이라고 가정하고 이를 이용해 현재 인덱스에 최대,최소값을 어떻게 구성하면 될지를 고민한다.
• 문제 유형
  • 새로운 리스트에 처음부터 끝까지 누적한 값을 담아두고 마지막 인덱스가 최종 답안
  • 입력값에 따라 끝점이 범위를 초과하는지에 대한 검증이 필요한 경우라면 역으로 끝점을 시작점으로 두고 시작점을 끝점으로 두어 풀이를 진행한다.
    • 일반적인 dp의 경우 첫번째 식이 점화식에 성립하도록 맨 앞에 더미를 추가하는데, 역이므로 맨 뒤에 더미를 추가한다.
    • 4번 유형
  • 새로운 리스트에 누적값을 담지만 누적하는 값이 문제에 조건에 따라 다르다.(첫 혹은 마지막 인덱스 값이 정답이 아님)
    • 새로운 리스트에서 최대, 최솟 값을 찾는 추가적인 로직이 필요하다.
    • 5번 유형
  • 편집 거리 알고리즘
    • 이건 알고리즘을 알아야 풀 수 있다.