💻 [코테10] 15장 동적 계획법

15장. 동적 계획법

15-1. 동적 계획법(Dynamic Programming) 개념

• 전체 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들을 해결하고 이것들을 활용하여 전체 문제를 해결하는 방법
• 동적 계획법을 효율적으로 활용하기 위해 충족 되어야 하는 조건
  • 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제 반복 등장
  • 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성

• 최적 부분 구조(opimal substructure)
  : 작은 문제의 해결책의 합으로 큰 문제를 해결할 수 있는 구조
• 중복 부분 문제(overlapping subproblems)
  : 큰 문제를 나누었을 때 작은 문제가 여러 개 반복되는 문제

1) 점화식 세우기와 동적 계획법

• 절차1) 문제를 해결하는 해가 이미 있다고 가정한다
• 절차2) 종료 조건을 설정한다
• 절차3) 절차 1, 2를 활용해 점화식을 세운다
  - 점화식 구현 : 재귀 활용
  • 재귀 호출 문제 해결 방법 : 반복문 또는 메모이제이션 활용

2) 재귀 호출의 횟수를 줄여주는 메모이제이션

• 메모이제이션 : 이미 계산한 값을 저장해두었다가 이 후 쓸 일이 있을 때 활용
• 피보나치 수 구하기 문제 : 최적 부분 구조이면서 중복 부분 문제에 해당
  - 점화식 구현 : 재귀 + 메모이제이션 활용
  

3) 최장 증가 부분 수열

• 부분 수열 : 주어진 숭려 중 일부를 뽑아 새로 만든 수열(단, 각각의 운소는 저후 관계 유지 필수)
• 최장 증가 부분 수열(Longest Increasing Subsequence;LIS) : 부분 수열의 원소가 오름차순을 유지하면서도 길이가 가장 긴 수열
• LIS의 길이 동적 계획법으로 구하기

4) 최장 공통 부분 수열

• Longest Common Subsequence(LCS)
• 두 수열이 어떤 기준에 따라 양쪽에서 공통으로 발견할 수 있는 가장 긴 부분 수열
• LCS의 길이 동적 계획법으로 구하기

15-2. 몸풀기 문제

• 문제70_LCS 길이 계산하기

'''
<최장 공통 부분 수열 구하기>
1. dp 2차원 배열 준비
2. dp(0, 0) = 0
3. str1[i] == str2[j] >> dp(i, j) = dp(i-1, j-1) + 1
4. str1[i] != str2[j] >> max(dp(i-1, j), dp(i, j-1))

'''


def solution(str1, str2):
    n = len(str1)
    m = len(str2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    
    for i in range(0, n):
        for j in range(0, m):
            if str1[i] == str2[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    
    return max(max(dp))

# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
print(solution("ABCBDAB","BDCAB")) # 반환값 : 4
print(solution("AGGTAB","GXTXAYB")) # 반환값 : 4

• 문제71_LIS 길이 계산하기

'''
<최장 증가 부분 수열 길이 구하기>
>> 해당 숫자로 끝나는 LIS 길이 넣기

0. n 길이의 result 초기화(0으로)
1. result[0] = 1
2. 수열을 순서대로 순회
    1) 현재 값 이전 값 순회
        ㄱ) 현재 값보다 작은 값들 중 LIS 길이 최대치 + 1
'''

def solution(nums):
    n = len(nums)
    lengths = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                lengths[i] = max(lengths[i], lengths[j] + 1)
    return max(lengths)

# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
print(solution([1, 4, 2, 3, 1, 5, 7, 3])) # 반환값 : 5
print(solution([3, 2, 1])) # 반환값 : 1

• 문제72_조약돌 문제

def solution(arr):
    m = len(arr[0])
    dp = [[0] * m for _ in range(4)]
    
    dp[0][0] = arr[0][0]
    dp[1][0] = arr[1][0]
    dp[2][0] = arr[2][0]
    dp[3][0] = arr[0][0] + arr[2][0]
    
    for i in range(1, m):
        dp[0][i] = arr[0][i] + max(dp[1][i-1], dp[2][i-1])
        dp[1][i] = arr[1][i] + max(dp[0][i-1], dp[2][i-1], dp[3][i-1])
        dp[2][i] = arr[2][i] + max(dp[0][i-1], dp[1][i-1])
        dp[3][i] = arr[0][i] + arr[2][i] + dp[1][i-1]
    return max(dp[0][-1], dp[1][-1], dp[2][-1], dp[3][-1])



# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
print(solution([[1, 3, 3, 2], [2, 1, 4, 1], [1, 5, 2, 3]])) # 반환값 : 19
print(solution([[1, 7, 13, 2, 6], [2, -4, 2, 5, 4], [5, 3, 5, -3, 1]])) # 반환값 : 32

15-3. 합격자가 되는 모의 테스트

• 문제73_피보나치 수
• 문제74_2 X n 타일링
• 문제75_정수 삼각형
• 문제76_땅따먹기
• 문제77_도둑질
• 문제78_가장 큰 정사각형 찾기
• 문제79_단어 퍼즐