중복되는 하위 문제(Overlapping Subproblems)

1
2
3
4

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def fibonacci_memo(n, memo={}):
    # 이미 계산된 결과가 있으면 바로 반환
    if n in memo:
        return memo[n]
    
    # 기본 사례
    if n <= 1:
        return n
    
    # 결과 계산 및 저장
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def fibonacci_tab(n):
    # DP 테이블 초기화
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    
    # 작은 문제부터 큰 문제까지 해결
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# 계단 오르기 문제: 한 번에 1단 또는 2단씩 오를 수 있을 때, n개의 계단을 오르는 방법의 수
def climb_stairs(n):
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]  # 선형 의존성
    
    return dp[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

# 행렬 곱셈 연쇄 문제
def matrix_chain_multiplication(dims):
    n = len(dims) - 1
    
    # dp[i][j] = i부터 j까지의 행렬을 곱하는 최소 연산 횟수
    dp = [[0 for _ in range(n)] for _ in range(n)]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            # 구간 내 모든 분할점 k에 대해 최소값 찾기 (구간 의존성)
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1])
    
    return dp[0][n-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# 동전 교환 문제: 주어진 금액을 만들기 위한 최소 동전 개수
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for coin in coins:
        for i in range(coin, amount + 1):
            # 현재 금액에서 동전 값을 뺀 상태에서 전이 (상태 전이 의존성)
            dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 편집 거리 문제
def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    
    # dp[i][j] = word1[:i]와 word2[:j] 간의 편집 거리
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    
    # 기본 케이스: 빈 문자열로 변환
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # 문자가 같으면 대각선 값 사용
            else:
                # 삽입, 삭제, 대체 중 최소값 (다차원 의존성)
                dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
    
    return dp[m][n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

# 하위 문제 중복 횟수 분석
def count_fibonacci_calls(n):
    count = [0] * (n + 1)
    
    def fibonacci(n):
        count[n] += 1
        if n <= 1:
            return n
        return fibonacci(n-1) + fibonacci(n-2)
    
    fibonacci(n)
    return count

# n=5일 때 호출 횟수: F(0):3번, F(1):5번, F(2):3번, F(3):2번, F(4):1번, F(5):1번

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def longest_increasing_subsequence(nums):
    if not nums:
        return 0
    
    n = len(nums)
    dp = [1] * n  # dp[i] = 인덱스 i까지의 LIS 길이
    
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def analyze_subproblem_calls(dp_function, n):
    # 하위 문제 호출 추적을 위한 래퍼 함수
    call_count = {}
    
    def wrapper(*args):
        # 튜플로 변환하여 해시 가능하게 만듦
        args_tuple = tuple(args)
        
        if args_tuple in call_count:
            call_count[args_tuple] += 1
        else:
            call_count[args_tuple] = 1
            
        return dp_function(*args)
    
    # 함수 실행
    wrapper(n)
    
    # 분석 결과
    total_calls = sum(call_count.values())
    unique_subproblems = len(call_count)
    max_repetition = max(call_count.values())
    
    return {
        "total_calls": total_calls,
        "unique_subproblems": unique_subproblems,
        "max_repetition": max_repetition,
        "detailed_counts": call_count
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def build_dependency_graph(problem_size):
    # 예: 피보나치 수열의 의존성 그래프
    graph = {}
    
    for i in range(problem_size + 1):
        if i <= 1:
            graph[i] = []  # 기본 사례는 의존성 없음
        else:
            graph[i] = [i-1, i-2]  # F(i)는 F(i-1)과 F(i-2)에 의존
    
    return graph

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])  # 독립적인 하위 문제
    right = merge_sort(arr[mid:])  # 독립적인 하위 문제
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        
        # 이미 처리된 노드는 건너뛰기
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def quick_sort(arr):
    if len(arr) <= 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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def memoization_optimization(func):
    """함수에 메모이제이션을 적용하는 데코레이터"""
    memo = {}
    
    def wrapper(*args):
        # 인수를 해시 가능한 형태로 변환
        args_key = tuple(map(lambda x: tuple(x) if isinstance(x, list) else x, args))
        
        if args_key not in memo:
            memo[args_key] = func(*args)
        return memo[args_key]
    
    return wrapper

@memoization_optimization
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def tabulation_optimization(fibonacci, n):
    """상향식 테이블링으로 피보나치 수열 최적화"""
    # 기본 사례
    if n <= 1:
        return n
    
    # 2개의 변수만 사용하여 공간 복잡도 최적화
    a, b = 0, 1
    
    for i in range(2, n + 1):
        a, b = b, a + b
    
    return b

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 원래 배낭 문제 구현 (2차원 배열)
def knapsack_original(weights, values, capacity):
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(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]

# 상태 공간 축소 버전 (1차원 배열)
def knapsack_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0 for _ in range(capacity + 1)]
    
    for i in range(n):
        # 역순으로 순회하여 이전 상태에 영향을 주지 않도록 함
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])
    
    return dp[capacity]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

def longest_palindromic_substring(s):
    n = len(s)
    # dp[i][j] = s[i:j+1]이 회문인지 여부
    dp = [[False for _ in range(n)] for _ in range(n)]
    
    # 모든 길이 1인 부분 문자열은 회문
    for i in range(n):
        dp[i][i] = True
    
    start = 0
    max_length = 1
    
    # 길이 2인 부분 문자열 확인
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_length = 2
    
    # 길이 3 이상인 부분 문자열 확인
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            # s[i+1:j]가 회문이고 s[i]와 s[j]가 같은지 확인 (중복되는 하위 문제 활용)
            if dp[i + 1][j - 1] and s[i] == s[j]:
                dp[i][j] = True
                
                if length > max_length:
                    start = i
                    max_length = length
    
    return s[start:start + max_length]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def floyd_warshall(graph):
    n = len(graph)
    dist = [row[:] for row in graph]  # 그래프 복사
    
    # k = 중간 정점
    for k in range(n):
        # i = 시작 정점
        for i in range(n):
            # j = 종료 정점
            for j in range(n):
                # i→k→j 경로가 i→j 직접 경로보다 짧은지 확인 (중복되는 하위 문제 활용)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

def min_completion_time(jobs, k):
    """
    k개의 프로세서에 작업을 할당하여 마지막 작업이 완료되는 시간을 최소화
    """
    n = len(jobs)
    
    # dp[mask][i] = 비트마스크 mask로 표현된 작업들을 i개의 프로세서에 할당했을 때의 최소 완료 시간
    dp = {}
    
    def solve(mask, processors):
        # 모든 작업이 할당됨
        if mask == (1 << n) - 1:
            return 0
        
        # 이미 계산된 상태
        if (mask, processors) in dp:
            return dp[(mask, processors)]
        
        # 가능한 모든 미할당 작업 조합 시도
        result = float('inf')
        
        # 새 프로세서 시작
        if processors > 0:
            for i in range(n):
                if not (mask & (1 << i)):  # 작업 i가 아직 할당되지 않음
                    new_mask = mask | (1 << i)
                    # 작업 i를 새 프로세서에 할당 (중복되는 하위 문제 활용)
                    result = min(result, max(jobs[i], solve(new_mask, processors - 1)))
        
        # 기존 프로세서에 추가
        for i in range(n):
            if not (mask & (1 << i)):  # 작업 i가 아직 할당되지 않음
                new_mask = mask | (1 << i)
                # 작업 i를 기존 프로세서에 추가 (중복되는 하위 문제 활용)
                result = min(result, jobs[i] + solve(new_mask, processors))
        
        dp[(mask, processors)] = result
        return result
    
    return solve(0, k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def problem_solver_memoization(input_data):
    # 메모이제이션 캐시 초기화
    memo = {}
    
    def solve_recursive(state):
        # 상태가 이미 계산되었는지 확인
        if state in memo:
            return memo[state]
        
        # 기본 사례 체크
        if is_base_case(state):
            return base_case_value(state)
        
        # 가능한 모든 선택지에 대해 최적값 계산
        result = initial_value  # 문제에 따라 초기값 설정 (최소값/최대값)
        for choice in possible_choices(state):
            next_state = apply_choice(state, choice)
            subproblem_result = solve_recursive(next_state)
            result = combine_results(result, subproblem_result, choice)
        
        # 결과 저장 및 반환
        memo[state] = result
        return result
    
    # 초기 상태에서 시작
    return solve_recursive(initial_state(input_data))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def problem_solver_tabulation(input_data):
    # 문제 크기 및 필요한 매개변수 추출
    n = extract_problem_size(input_data)
    
    # DP 테이블 초기화
    dp = initialize_dp_table(n)
    
    # 기본 사례 설정
    set_base_cases(dp)
    
    # 상향식으로 테이블 채우기
    for i in range(smallest_non_base_case, n + 1):
        for j in range(additional_dimension_if_needed):
            dp[i][j] = calculate_value(dp, i, j, input_data)
    
    # 최종 결과 반환
    return extract_result(dp, n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def memory_optimized_dp(input_data):
    n = extract_problem_size(input_data)
    
    # 1. 차원 축소: 2차원 → 1차원
    # 예: 배낭 문제에서 행(물건)을 기준으로 반복하면서 한 행만 유지
    dp = initialize_reduced_dp_table()
    
    for i in range(1, n + 1):
        # 2. 순회 방향 최적화: 역순 순회로 이전 값 보존
        for j in range(max_value, min_value - 1, -1):
            dp[j] = calculate_with_previous_values(dp, j, input_data[i-1])
    
    # 3. 슬라이딩 윈도우: 필요한 이전 상태만 유지
    # 예: 피보나치 수열에서 마지막 두 값만 유지
    a, b = initial_values
    
    for i in range(2, n + 1):
        a, b = b, combine(a, b)
    
    return b

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def choose_appropriate_data_structure(problem_type, input_size):
    if problem_type == "linear_dependency":
        # 배열이나 리스트로 충분
        return [0] * (input_size + 1)
    
    elif problem_type == "two_dimensional":
        # 2D 배열 또는 딕셔너리
        if input_size <= 1000:
            return [[0 for _ in range(input_size + 1)] for _ in range(input_size + 1)]
        else:
            # 희소 행렬의 경우 딕셔너리가 더 효율적
            return {}
    
    elif problem_type == "state_based":
        # 복잡한 상태는 해시 맵이 적합
        return {}
    
    elif problem_type == "bit_manipulation":
        # 비트마스크 사용
        return [0] * (1 << input_size)