JUNGLE 240404 (W03)

in Study #Jungle

KRAFTON JUNGLE Week 03

1. Keywords

동적 계획법 (Dynamic Programming)

  • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 재활용해서 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
  • 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용하여 상위 문제를 풀어가는 방식
  • Memoization 기법을 사용함
    • Memoization: 프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술

분할 정복 (Divide and Conquer)

  • 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
  • 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식 (주로 재귀함수로 구현)
  • 문제를 쪼갤 때, 부분 문제는 서로 중복되지 않음

동적 계획법 vs 분할 정복

내용 참고: Click!!

  • 공통점: 문제를 잘개 쪼개서 가장 작은 단위로 분할
  • 차이점:
    • 동적 계획법은 부분 문제가 중복되어 상위 문제 해결 시 재활용되지만, 분할 정복은 중복되지 않음
    • 동적 계획법은 Memoization 기법을 사용하지만, 분할 정복은 사용하지 않음

Example

동적 계획법

피보나치 수열, 최장 증가 부분 수열, 최단 경로 문제, 배낭 문제, 그래프 알고리즘에서의 최적화 문제 등이 있음

def climb_stairs(n):
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1  # 1계단을 오르는 경우의 수
    dp[2] = 2  # 2계단을 오르는 경우의 수
    
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # 이전 계단에서 1계단 또는 2계단을 오르는 경우의 수 합산
    
    return dp[n]

# 예시 사용법
n = 5
ways_to_climb = climb_stairs(n)
print(ways_to_climb)  # 출력: 8 (1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 2+2+1, 1+2+2, 2+1+2)
분할 정복

합병 정렬, 퀵 정렬, 이진 탐색, 최대 부분 배열 문제, 행렬 거듭제곱 등이 있음

def quick_sort(arr):
    if len(arr) <= 1:  # 배열이 비어 있거나 원소가 1개 이하인 경우, 정렬할 필요가 없으므로 종료
        return arr
    
    pivot = arr[len(arr) // 2]  # 피벗은 중간 값으로 선택
    left = [x for x in arr if x < pivot]  # 피벗보다 작은 원소들로 이루어진 부분 배열
    middle = [x for x in arr if x == pivot]  # 피벗과 같은 원소들로 이루어진 부분 배열
    right = [x for x in arr if x > pivot]  # 피벗보다 큰 원소들로 이루어진 부분 배열
    
    # 재귀적으로 부분 배열을 정렬하여 합치기
    return quick_sort(left) + middle + quick_sort(right)

# 예시 사용법
arr = [3, 7, 2, 5, 1, 4, 6]
sorted_arr = quick_sort(arr)
print(sorted_arr)  # 출력: [1, 2, 3, 4, 5, 6, 7]

그리디 알고리즘 (Greedy)

  • 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘
  • 하지만 그리디 알고리즘은 100% 최적해를 보장해주지 않는다.
  • 예시로는 다익스트라 알고리즘, 거스름돈 문제 등이 있다.

배낭 문제 (Knapsack Problem)

By Greedy Algorithm
def knapsack_greedy(weights, values, capacity):
    n = len(weights)
    items = list(zip(values, weights))  # 각 물건의 (가치, 무게) 튜플 리스트 생성
    items.sort(key=lambda x: x[0] / x[1], reverse=True)  # 물건을 가치 비율에 따라 내림차순으로 정렬
    
    total_value = 0  # 배낭에 넣은 물건의 총 가치
    total_weight = 0  # 배낭에 넣은 물건의 총 무게
    for value, weight in items:
        if total_weight + weight <= capacity:  # 배낭에 물건을 넣을 수 있는 경우
            total_value += value
            total_weight += weight
        else:  # 배낭에 물건을 넣을 수 없는 경우
            remaining_capacity = capacity - total_weight  # 남은 용량 계산
            total_value += value * (remaining_capacity / weight)  # 남은 용량만큼만 넣기
            break
    
    return total_value
  • 각 물건의 가치 대비 무게 비율이 높은 순서부터 물건을 선택하여 배낭에 담는다.
  • 각 단계에서 가장 좋은 선택을 하여 전체적으로 최적해를 찾는다.
  • but, 그리디 알고리즘은 항상 최적해를 보장하지 않는다.
By Dynamic Programming
def knapsack_dp(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]  # 동적 계획법을 위한 DP 테이블 초기화

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:  # 현재 물건을 배낭에 넣을 수 있는 경우
                # 현재 물건을 넣었을 때와 넣지 않았을 때의 최대 가치 비교
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])  
            else:  # 현재 물건을 배낭에 넣을 수 없는 경우
                dp[i][w] = dp[i - 1][w]  # 현재 물건을 넣지 않았을 때의 최대 가치 사용

    return dp[n][capacity]  # 마지막 행의 마지막 열 값이 배낭의 용량이 capacity일 때의 최대 가치
  • 모든 가능한 상태를 저장하고 이를 재활용하여 최적해를 찾는다.
  • 주어진 용량의 배낭을 채우기 위해 각 물건을 선택하거나 선택하지 않는 모든 경우를 고려하며, 이를 통해 모든 가능한 부분 문제의 해를 구한다.
  • 그리고 이를 이용하여 최종적으로 배낭의 용량이 주어졌을 때 최대 가치를 계산한다.
  • 동적 계획법은 모든 가능한 경우를 고려하기 때문에 항상 최적해를 찾을 수 있다.
  • but, 시간과 공간 복잡도가 높아질 수 있다.