11.21 (TIL)

동적 프로그래밍 ( Dynamic Programming )

1) 동적 프로그래밍 이란?

동적 프로그래밍은 큰 문제를 작은 하위 문제로 분할하여 푸는 접근 방식

 

작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 이용하여 큰 문제의 해결 방법을 도출

이러한 저장 과정을 "메모이제이션(Memoization)"이라고 함

 

동적 프로그래밍은 중복되는 하위 문제들을 효율적으로 해결하기 위해 사용

 

일반적으로 재귀적인 구조를 가지며, 하향식(Top-down)과 상향식(Bottom-up) 두 가지 방법으로 구현

 

동적 프로그래밍은 최적 부분 구조와 중복 부분 문제의 특징을 가진 문제들을 효과적으로 해결

 

간단 예제

def fibonacci(n):
    # 계산된 부분 문제의 결과를 저장하기 위한 배열
    # 초기값은 -1로 설정하여 계산이 안 된 상태를 나타냄
    memo = [-1] * (n + 1)

    # 피보나치 수열을 계산하는 함수
    def fib(n):
        # 기저 사례: 0 또는 1일 때는 그대로 반환
        if n == 0 or n == 1:
            return n

        # 이미 계산된 값이 있으면 그 값을 반환
        if memo[n] != -1:
            return memo[n]

        # 계산이 안 된 경우, 재귀적으로 부분 문제를 해결하고 결과를 저장
        memo[n] = fib(n - 1) + fib(n - 2)
        return memo[n]

    # 최종 결과 반환
    return fib(n)

# 피보나치 수열의 10번째 항 출력
result = fibonacci(10)
print(result)

 

// fibonacci 함수:

피보나치 수열의 n번째 항을 반환하는 함수

memo 배열은 이미 계산된 부분 문제의 결과를 저장하기 위한 배열

 

// fib 함수:

재귀적으로 피보나치 수열을 계산하는 함수

기저 사례로 n이 0 또는 1일 때는 n을 반환

이미 계산된 값이 있다면 해당 값을 반환

그렇지 않으면 재귀적으로 부분 문제를 해결하고 결과를 memo 배열에 저장

 

// 메모이제이션(Memoization):

이미 계산된 값을 저장해두고 필요할 때 불러와서 중복 계산을 피하는 기법

memo 배열을 사용하여 한 번 계산한 부분 문제의 결과를 저장하고 이를 활용

 

// 최종 결과 반환:

fibonacci(10)을 호출하여 피보나치 수열의 10번째 항을 계산하고 결과를 출력

 

// 시간 복잡도는 O(n), n은 피보나치 수열의 인덱스로, 계산해야 하는 부분 문제의 수

 

// 동적 프로그래밍은 이처럼 중복 계산을 피하고 이미 계산한 결과를 활용하여 효율적으로 문제를 해결하는 기법을 의미

 

 

그리디 알고리즘 ( Greedy Algorithm )

1) 그리디 알고리즘 이란?

그리디 알고리즘은 각 단계에서 가장 최적인 선택을 하는 알고리즘

각 단계에서 가장 이익이 큰 선택을 하여 결과적으로 최적해에 도달하려는 전략

그리디 알고리즘은 지역적인 최적해를 찾는데 초점을 맞추기 때문에 항상 전역적인 최적해를 보장하지는 않는다.

그리디 알고리즘은 간단하고 직관적인 설계가 가능하며, 실행 시간이 매우 빠른 편입

 

간단 예시

동전 거스름돈 문제

def greedy_coin_change(coins, amount):
    coins.sort(reverse=True)  # 동전을 큰 순서대로 정렬

    change = []  # 거스름돈 동전의 개수를 저장할 리스트

    for coin in coins:
        num_coins = amount // coin  # 해당 동전으로 거슬러 줄 수 있는 최대 개수 계산
        change.append((coin, num_coins))
        amount -= num_coins * coin  # 해당 동전으로 거슬러 준 후 남은 금액 업데이트

    return change

# 예시: 동전 종류와 거스름돈 금액
coin_types = [500, 100, 50, 10]
amount_to_change = 1230

result = greedy_coin_change(coin_types, amount_to_change)
print(result)

 

// greedy_coin_change 함수:

coins: 동전의 종류를 나타내는 리스트

amount: 거스름돈으로 거슬러 줄 금액

동전을 큰 순서대로 정렬하고, 각 동전으로 거슬러 줄 수 있는 최대 개수를 계산

 

// 동전을 큰 순서대로 정렬:

가장 큰 동전부터 거스름돈을 계산하는 것이 그리디 알고리즘의 특징

 

// 동전으로 거슬러 줄 수 있는 최대 개수 계산:

현재 동전으로 거슬러 줄 수 있는 최대 개수를 계산하여 결과 리스트에 추가

 

// 거스름돈을 주고 남은 금액 업데이트:

현재 동전으로 거슬러 준 후 남은 금액을 계산하여 업데이트

 

// 결과 반환:

각 동전의 종류와 해당 동전으로 거슬러 준 개수를 담은 리스트를 반환

 

// 실행 및 결과 출력:

coin_types에는 [500, 100, 50, 10]이라는 동전 종류가 있고, amount_to_change에는 1230이라는 거스름돈이 나옴

결과는 [(500, 2), (100, 2), (50, 0), (10, 3)]으로, 500원 동전 2개, 100원 동전 2개, 10원 동전 3개를 사용하여 1230원을 거슬러줄 수 있음

 

// 시간 복잡도는 동전의 종류 수에 선형적으로 비례합니다. 따라서 동전의 종류를 n개라고 할 때, 시간 복잡도는 O(n)

 

 

분할 정복 ( Divide and Conquer )

1) 분할 정복 이란?

큰 문제를 작은 부분 문제로 분할하므로 문제의 크기에 따른 성능 향상이 가능

재귀적인 구조를 가지므로 문제 해결 방법의 설계가 단순하고 직관적

분할된 부분 문제들은 독립적으로 해결되므로 병렬 처리에 유리

하지만 문제를 분할할 때 발생하는 부분 문제들 간의 중복 계산이 발생할 수 있다.

이런 경우에는 중복 계산을 피하기 위한 메모이제이션 등의 기법을 활용하여 성능을 향상시킬 수 있다.

 

간단 예제

병합 정렬(Merge Sort)

 

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 배열을 중간으로 나눔
        left_half = arr[:mid]
        right_half = arr[mid:]

        # 분할 정복: 왼쪽과 오른쪽 부분 배열을 각각 정렬
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        # 정렬된 부분 배열을 합병
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # 남은 요소들을 합병
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# 예시: 정렬되지 않은 배열
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print("Sorted array:", arr)

 

// merge_sort 함수:

주어진 배열을 분할하고 정렬하는 함수

 

// 배열을 중간으로 나눔:

배열을 중간 지점에서 두 부분 배열로 나눔

 

// 분할 정복:

왼쪽과 오른쪽 부분 배열에 대해 재귀적으로 merge_sort 함수를 호출하여 각 부분 배열을 정렬

 

// 합병 (Merge):

정렬된 왼쪽과 오른쪽 부분 배열을 합병하여 전체 배열을 정렬

 

// 남은 요소들을 합병:

왼쪽이나 오른쪽 부분 배열 중 남은 요소들을 합병

 

// 예시 실행 및 결과 출력:

주어진 배열 [38, 27, 43, 3, 9, 82, 10]이 merge_sort 함수에 전달되고, 정렬된 결과가 출력

 

// 병합 정렬의 시간 복잡도는 O(n log n), 배열을 반으로 나누고 각 부분 배열을 정렬하는 단계에서 log n, 각 부분 배열을 합병하는 단계에서 n의 시간 복잡도를 갖기 때문

 

 

 

 

01. 문제 해결 전략

1. 문제 이해: 문제를 정확히 이해하고 요구사항을 파악하는 것이 중요합니다. 문제 설명을 꼼꼼히 읽고, 입력과 출력의 형식을 이해하고 분석해야 합니다.
2. 예제와 테스트 케이스: 문제의 예제와 추가적인 테스트 케이스를 활용하여 문제를 이해하고 해결 방법을 검증해야 합니다. 예제와 테스트 케이스는 문제의 조건과 제약을 이해하는 데 도움을 줄 수 있습니다.
3. 알고리즘 설계: 문제를 해결하기 위한 알고리즘을 설계해야 합니다. 문제의 특성에 맞는 알고리즘을 선택하고, 알고리즘의 구현 방법과 시간 복잡도를 고려해야 합니다.
4. 코드 작성: 알고리즘을 기반으로 코드를 작성해야 합니다. 코드는 가독성이 좋고, 문제의 요구사항을 정확히 반영해야 합니다. 변수명을 명확하게 지어 가독성을 높이고, 주석을 추가하여 코드를 설명하는 것도 좋은 습관입니다.
5. 효율성: 문제의 제약 조건과 입력 크기에 따라 알고리즘의 효율성을 고려해야 합니다. 최적화 기법을 사용하고, 시간 복잡도와 공간 복잡도를 최대한 줄이는 방향으로 코드를 작성해야 합니다.
6. 디버깅과 테스트: 코드를 작성한 후에는 디버깅을 통해 오류를 찾고 수정해야 합니다. 테스트 케이스를 활용하여 코드의 정확성을 검증하고, 예외 상황을 고려하여 코드를 완성해야 합니다.
7. 시간 관리: 코딩 테스트는 제한된 시간 안에 문제를 해결해야 하는 것이 특징입니다. 따라서 시간을 효과적으로 관리하고, 문제에 맞는 효율적인 접근 방법을 선택하는 능력이 필요합니다.
8. 연습과 경험: 코딩 테스트는 많은 연습과 경험이 필요한 분야입니다. 다양한 유형의 문제에 노출되고, 해결 방법을 익히며 자신의 실력을 향상시켜야 합니다. 코딩 테스트 관련 문제를 많이 풀고 다른 사람들의 풀이를 학습하는 것도 좋은 방법입니다.

02. 실전 연습 문제

1. 백준 온라인 저지 (**https://www.acmicpc.net/**): 다양한 난이도의 알고리즘 문제를 제공하며, 많은 사용자들과 소통할 수 있는 커뮤니티도 제공합니다.
2. 프로그래머스 (**https://programmers.co.kr/**): 코딩 테스트 연습을 위한 문제들을 다양한 난이도로 제공하고 있습니다. 실제 취업 시험에서도 출제되는 문제들을 포함하고 있습니다.
3. 바킹독 (https://blog.encrypted.gg/): 알고리즘 강의 다수 제공하고 있습니다.
4. LeetCode (**https://leetcode.com/**): 알고리즘 문제와 코딩 테스트 문제를 다양한 난이도로 제공하고 있으며, 실제 기업 코딩 인터뷰에서 출제되는 문제들을 포함하고 있습니다.

03. 코딩 테스트나 알고리즘 문제의 종류

1. 탐색과 정렬: 배열, 리스트, 문자열 등의 데이터에서 특정 값을 찾거나 정렬하는 문제입니다. 선형 탐색, 이진 탐색, 퀵 정렬, 병합 정렬 등의 알고리즘이 주로 활용됩니다.
2. 그래프: 그래프 구조를 활용하여 문제를 해결하는 문제입니다. 최단 경로, 신장 트리, 네트워크 연결 등의 문제가 있을 수 있으며, 대표적인 알고리즘으로는 DFS(Depth-First Search), BFS(Breadth-First Search), Dijkstra, 크루스칼, 프림 등이 있습니다.
3. 동적 프로그래밍: 큰 문제를 작은 하위 문제로 분할하여 해결하는 동적 프로그래밍 알고리즘을 활용하는 문제입니다. 피보나치 수열, 최장 공통 부분 수열, 0-1 배낭 문제 등이 있습니다.
4. 그리디 알고리즘: 각 단계에서 가장 최적인 선택을 하는 알고리즘으로, 지역적 최적해를 찾는 문제입니다. 거스름돈 문제, 회의실 배정, 작업 스케줄링 등이 있습니다.
5. 분할 정복: 문제를 작은 부분으로 분할하여 해결하는 분할 정복 알고리즘을 사용하는 문제입니다. 퀵 정렬, 병합 정렬, 이진 탐색 등이 있습니다.
6. 동적 그래프: 그래프 구조에서 동적인 변화를 다루는 문제입니다. 플로이드-와샬 알고리즘, 벨만-포드 알고리즘 등이 있습니다.
7. 문자열 처리: 문자열에 대한 다양한 처리를 다루는 문제입니다. 문자열 압축, 회문 판별, 문자열 매칭 등이 있을 수 있습니다.
8. 기타: 그 외에도 수학적인 문제, 비트 연산 문제, 시뮬레이션 문제, 동적 계획법과 그래프의 결합 문제 등 다양한 유형의 문제가 출제될 수 있습니다.