[코딩테스트] 2주차: 동적 프로그래밍 (Dynamic Programming)

동적 프로그래밍 (Dynamic Programming)

학습 주제:

• 동적 프로그래밍의 기초 (Memoization, Tabulation)
• 대표적인 DP 문제 풀이 (피보나치 수열, 배낭 문제, 최대 부분합 문제)

학습 목표:

• 동적 프로그래밍의 개념과 기초적인 구현 방법을 이해하고 적용할 수 있다.
• 대표적인 동적 프로그래밍 문제를 해결하여 문제 해결 능력을 향상시킬 수 있다.

학습 자료:

• 동적 프로그래밍 개요와 원리
• 피보나치 수열 (Top-Down, Bottom-Up) 구현 방법
• 배낭 문제와 최대 부분합 문제 설명 및 구현

실습 문제:

1. 피보나치 수열 구현 (Top-Down, Bottom-Up)

• 주어진 정수 n에 대해 피보나치 수열의 n번째 값을 구하는 함수를 작성하세요.

# Top-Down Approach with Memoization
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_top_down(n):
    if n < 2:
        return n
    return fib_top_down(n - 1) + fib_top_down(n - 2)

# Bottom-Up Approach
def fib_bottom_up(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# Test
n = 10
print(f"Top-Down Fibonacci({n}): {fib_top_down(n)}")
print(f"Bottom-Up Fibonacci({n}): {fib_bottom_up(n)}")

 

2. 배낭 문제 (0/1 Knapsack)

• 주어진 아이템의 무게와 가치 리스트, 그리고 배낭의 최대 무게를 입력받아 최대 가치를 반환하는 함수를 작성하세요.

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
    
    return dp[n][W]

# Test
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
W = 7
print(knapsack(weights, values, W))  # 9

 

3. 최대 부분합 문제 (Kadane's Algorithm)

• 주어진 리스트에서 연속된 부분 리스트의 합 중 최대값을 찾는 함수를 작성하세요

def max_subarray_sum(arr):
    max_so_far = arr[0]
    max_ending_here = arr[0]
    
    for i in range(1, len(arr)):
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        max_so_far = max(max_so_far, max_ending_here)
    
    return max_so_far

# Test
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(arr))  # 6

 

추가 학습 자료:

• Dynamic Programming - GeeksforGeeks
• 0/1 Knapsack Problem - GeeksforGeeks
• Kadane's Algorithm - GeeksforGeeks

---

백준 (Baekjoon) 문제

1. 문제명: 1로 만들기
   • 설명: 정수 X에 사용할 수 있는 연산은 3가지입니다. 1을 뺀다, X가 3으로 나누어 떨어지면 3으로 나눈다, X가 2로 나누어 떨어지면 2로 나눈다. 이 세 연산을 사용하여 1을 만들 때, 최소 연산 횟수를 구하세요.
   • 문제 유형: 동적 프로그래밍
   • 난이도: 실버 III
   • 주소: 1로 만들기
2. 문제명: 동전 1
   • 설명: n가지 종류의 동전이 있을 때, 이 동전들을 사용하여 합이 k가 되는 경우의 수를 구하는 문제입니다.
   • 문제 유형: 동적 프로그래밍
   • 난이도: 실버 I
   • 주소: 동전 1
3. 문제명: 카드 구매하기
   • 설명: 카드의 가격이 주어질 때, n개의 카드를 구매하기 위해 지불해야 하는 최대 금액을 구하는 문제입니다.
   • 문제 유형: 동적 프로그래밍
   • 난이도: 실버 I
   • 주소: 카드 구매하기

프로그래머스 (Programmers) 문제

1. 문제명: 정수 삼각형
   • 설명: 정수로 이루어진 삼각형에서 맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 거쳐간 숫자의 합이 가장 큰 경우를 구하는 문제입니다.
   • 문제 유형: 동적 프로그래밍
   • 난이도: 중급
   • 주소: 정수 삼각형
2. 문제명: 등굣길
   • 설명: 학교에 가는 길에 물이 잠긴 지역이 있을 때, 가장 효율적인 등굣길의 경로의 수를 구하는 문제입니다.
   • 문제 유형: 동적 프로그래밍
   • 난이도: 중급
   • 주소: 등굣길
3. 문제명: 도둑질
   • 설명: 도둑이 털 수 있는 집들이 원형으로 배치되어 있을 때, 인접한 두 집을 동시에 털 수 없다는 제약 조건 아래에서 최대 금액을 훔칠 수 있는 방법을 구하는 문제입니다.
   • 문제 유형: 동적 프로그래밍
   • 난이도: 중급
   • 주소: 도둑질