[2025 1학기 알고리즘 스터디] 박현빈 #2주차

Dynamic Programming

동적 계획법, 다이나믹 프로그래밍(Dynamic Programming, DP) : 큰 문제를 작게 나누고, 같은 문제라면 한번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

최적의 해를 구하는 문제는 많은 연산 시간과 메모리가 필요해 컴퓨터로도 해결하기 어려운 문제이다. 이러한 문제들 중에서 특정 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 상승 시킬 수 있다. 기존의 알고리즘이 해결하지 못하는 문제들 중 다이나믹 프로그래밍 기법을 통해서 해결할 수 있는 문제가 있다. 대표적인 예시로 피보나치 수열이 있다.

---

DP 기법을 적용시키기 위한 조건

다이나믹 프로그래밍을 사용하기 위해서는 해당 하는 문제가 다음 2가지 조건을 만족해야 한다.

1. 최적 부분 구조(Optimal Substructure): 큰 문제의 최적해가 작은 문제의 최적해로 이루어진 구조이다. ⇒ 이를 통해 점화식의 형태로 표현 가능함을 확인할 수 있다.
2. 예를 들어, 피보나치 수열에서 F(n) = F(n-1) + F(n-2)와 같이 큰 문제를 작은 문제로 나눌 수 있고 이는 큰 문제에서도 동일하다.
3. 중복되는 부분 문제(Overlapping Subproblems) : 동일한 부분 문제가 반복되는 경우이다. ⇒ 다이나믹 프로그래밍의 메모제이션 혹은 DP 테이블을 통해서 작은 문제의 답을 저장 및 재사용을 통해서 문제 해결의 효율성을 높일 수 있다.
4. 예를 들어, 피보나치 수열을 재귀적으로 해결하는 과정에서 동일한 부분 문제가 반복적으로 호출되는 것을 예로 들 수 있다.

---

DP 문제 해결의 두가지 방식

• 탑다운(Top-Down) 접근 - 메모이제이션(Memoization):
  • 재귀적 접근 방식으로, 함수 호출 시 결과를 저장하여 중복 계산을 피합니다.
  • 재귀 함수를 사용하면 함수를 다시 호출 했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드(알고리즘 외에 연산을 위해 필요한 시간)가 발생 한다. 따라서, 재귀 함수 보다는 반복문을 사용하는 것이 성능이 좋다.
  • 이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해서 작은 문제를 호출 한다고 하여 Top_Down방식 이라고 한다.
• 바텀업(Bottom-Up) 접근 - 타뷸레이션(Tabulation):
  • 단순히 반복문을 잉요하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출 한다고 하여 Bottom-Up 방식이라고 한다.
  • 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이다. 바텀업 방식에서 사용되는 결과 저장용 리스트는 ‘DP 테이블’ 이라고 부르며, 메모이 제이션은 탑다운 방식에 국한되어 사용되는 표현이다.
  • 다이나믹 프로그래밍과 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념이다.

점화식

• 탑다운에서 메모제이션 기법은 반복되는 연산을 저장해두어 한 번 계산한 문제라면 다시 풀지 않고 정답을 호출해 효율적으로 문제를 해결하는 방법이다. 즉, 메모제이션을 사용하기 이전에는 점화식을 완성해야 하며 점화식에 값을 연산하는 과정에서 중복되는 연산을 찾았을때만 사용이 가능하다. Dynamic 프로그래밍 기법을 사용하기 위해서는 최적 부분 구조, 중복되는 부분 문제가 성립 되어야 하는데 이는 결국 점화식을 만들기전 확인해야 하는 조건과 같다.

---

<나동빈, "이것이 코딩 테스트다", 216쪽>

문제를 푸는 첫 번째 단계는 (당연하게 들리겠지만) 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이다. 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여불르 확인해보자.

일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 아이디어이다. 앞서 다루었던 피보나치 수열의 에제 처럼 재귀 함수를 작성한 뒤에 나중에 메모이제이션 기법을 적용해 소스코드를 수정하는 것도 좋은 방법이다.

또한 가능하다면 재귀 함수를 이용하는 탑다운 방식 보다는 바텀업 방식으로 구현하는 것을 권장한다. 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다. 실제로 앞에서 제시한 재귀 적인 피보나치 수열의 소스코드에서 오천 번째 이상의 큰 피보나치 수를 구하도록 하면 recursion depth와 관련된 오류가 발생한다.

 

1463번 문제 

import sys

"""변수설명
n : 1로 만들고자 하는 수 
min_count : 최소 연산 횟수 
count : 현재 연산 횟수 
"""

n = int(sys.stdin.readline().strip())
min_count = n - 1

def GotoOne(number, cnt):

    global min_count

    # number가 목표값 1에 도달한 경우에 최소 연산 초기화후 연산 종료
    if number == 1:
        if min_count > cnt:
            min_count = cnt
        return
    else:

        if cnt > min_count:
            return
        else:
            if number%3 == 0:
                GotoOne(number//3, cnt + 1)
            if number%2 == 0:
                GotoOne(number//2, cnt + 1)
            GotoOne(number - 1, cnt + 1)

GotoOne(n, 0)
print(min_count)

2579번 문제 

import sys

n = int(sys.stdin.readline().strip())
n_list = [0]
for i in range(n):
    n_list.append(int(sys.stdin.readline().strip()))
n_memo_list = [[0, 0] for _ in range(n + 1)]

# 인자 값으로는 현재 몇번째 계단에 인지와 현재 계단을 올라오며 모은 점수 그리고 연속해서 계단 하나를 올라온 횟수가 저장되어 있다.
def StepStairs(now_stair, score, cnt):

    global n_list
    global n_memo_list

    # 메모 제이션
    # 이전 값보다 작은 경우 연산을 종료 시킨다.
    if score < n_memo_list[now_stair][cnt - 1]:
        return
    # 이전 값보다 큰 경우 최댓값 업데이트
    else:
        n_memo_list[now_stair][cnt - 1] = score

    # 종료 조건
    if now_stair == n:
        return

    # 재귀 호출
    if cnt < 2:
        if now_stair + 1 <= n:

            StepStairs(now_stair + 1, score + n_list[now_stair + 1], cnt + 1)
    if now_stair + 2 <= n:
        StepStairs(now_stair + 2, score + n_list[now_stair + 2], 1)


StepStairs(0, 0, 0)
print(max(n_memo_list[n][0], n_memo_list[n][1]))

11053번 문제 

import sys

n = int(sys.stdin.readline().strip())
n_list = list(map(int, sys.stdin.readline().strip().split()))

# 오름 차순 정렬, 중복 제거
n_set = set(n_list)
n_sort_list = sorted(list(n_set))
n_sort_list = n_sort_list[::-1]

# 각 원소의 최장 증가 부분 수열을 저장하는 리스트 생성
subsequence_list = [0 for _ in range(n)]
for sort_element in n_sort_list:

    long_subsequence = 0

    for i in range(1, n + 1):

        if sort_element == n_list[n-i]: # 비교 대상이 자신인 경우
            subsequence_list[n-i] = long_subsequence + 1
        else:
            # 가져온 값이 자신 보다 크며 자신 보다 크며, 부분 수열의 길이가 지금까지 길이 보다 길다면
            if n_list[n-i] > sort_element and long_subsequence < subsequence_list[n-i]:
                long_subsequence = subsequence_list[n-i]

print(max(subsequence_list))