Skip to main content
HashnodeMy dev journey

Command Palette

Search for a command to run...

Overview of Dynamic Programming (1/3)

동적프로그래밍 개요

Updated
•22 min read
Overview of Dynamic Programming (1/3)
H
Heesu Noh
Part of seriesComputer Algorithms

Contents

1️⃣ 동적 프로그래밍 (Dynamic Programming)
2️⃣ 행렬 경로 문제 (Matrix Path Problem)
3️⃣ 돌 놓기 문제 (Stone Placing Problem)

Summary

동적 프로그래밍은 행렬 경로 문제와 돌 놓기 문제와 같이 최적화가 필요한 문제를 작은 하위 문제로 나누어 해결하는 데 효과적이다. DP 테이블을 이용해 중간 결과를 저장함으로써 중복 계산을 방지하고, 최적의 해결책을 효율적으로 구할 수 있다.

1. 동적 프로그래밍(DP) 개요 (Dynamic Programming (DP) Overview)

  • 동적 프로그래밍은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 방법을 뜻한다.

  • DP는 특히 최적 부분 구조, Optimal Substructure (큰 문제의 최적 해가 작은 문제의 최적 해에 의존함)와 중복되는 부분 문제, Overlapping Subproblems (같은 하위 문제가 여러 번 해결되는 경우) 특성을 가진 문제에 유용하다.

  • DP는 하위 문제의 해결 결과를 저장(메모이제이션, memoizing)하여, 불필요한 계산을 피함으로써 효율적인 해결을 가능하게 한다.

2. 행렬 경로 문제 (Matrix Path Problem)

  • 문제: n x n 크기의 그리드가 주어지고, 각 칸에 숫자가 있을 때, 왼쪽 위에서 오른쪽 아래로 이동하면서 합이 최소가 되는 경로(minimum sum path)를 찾는 문제이다. 이동은 오른쪽이나 아래쪽으로만 가능하다.

  • 접근법: DP를 사용하여 각 칸에서의 최소 경로 합을 저장한다. 위나 왼쪽에서 오는 경로 중 최소값을 사용해 현재 칸의 최소 합을 계산한다.

  • 핵심 아이디어: 각 칸의 최소 경로 합은 위쪽이나 왼쪽 칸의 최소 합을 기준으로 하므로, 이를 이용해 DP 테이블을 업데이트하여 목적지까지의 최적 경로(optimal path)를 찾을 수 있다.

3. 돌 놓기 문제 (Stone Placing Problem)

  • 문제: 각 칸에 숫자가 기록된 3×N 크기의 테이블이 주어졌을 때, 각 열에 제한된 규칙에 따라 돌을 놓아 선택한 칸의 숫자 합이 최대가 되도록 하는 문제이다. 예를 들어, 같은 행이나 인접한 열에는 돌을 놓을 수 없다.

  • 접근법: DP를 사용하여 각 열과 패턴에 대한 최대 점수를 저장한다.

  • 핵심 아이디어: 각 열에서 돌을 놓을 수 있는 여러 패턴 중에서, 이전 열에서 가능한 패턴 중 최대 점수를 선택해 현재 열의 최대 점수를 계산한다. 이를 통해 전체 최댓값을 효율적으로 구할 수 있다.

  • 최적화(Optimization): DP 테이블을 사용해 이전에 계산된 점수를 저장하여, 중복 계산을 피하고 효율성을 높인다.

1️⃣ 동적 프로그래밍 (Dynamic Programming)

동적 프로그래밍 # 1:
개요 (Overview of Dynamic Programming)

💡요약: 재귀적 알고리즘은 큰 문제를 작은 문제로 나누어 해결하는 강력한 도구이다. 올바르게 사용하면 효율적인 해결책을 제공하지만, 잘못 사용하면 불필요한 함수 호출이 많아져 비효율적이 될 수 있다.

  • 큰 문제안에 작은 문제가 깃들어 있다 (Small Problems within Large Problems): 재귀적 알고리즘에서는 큰 문제를 더 단순한 형태의 작은 문제들로 나눌 수 있으며, 각 작은 문제는 원래 문제와 닮아 있다.

  • 잘 쓰면 보약, 잘못 쓰면 맹독 (Efficient if Used Correctly, Trouble if Not): 재귀는 제대로 사용하면 매우 강력하고 효율적일 수 있지만, 신중하게 사용하지 않으면 시간과 자원을 과도하게 소비하는 비효율적인 해결책이 될 수 있다.

  • 관계중심으로 파악함으로써 문제를 간명하게 볼 수 있음 (Relationship-Focused, Simplifying the Problem): 재귀적 알고리즘은 문제를 관계 중심으로 이해할 수 있게 하여 복잡한 문제를 전체적인 구조에서 간명하게 볼 수 있도록 도와준다.

  • 재귀적 해법을 사용하면 심한 중복 함수 호출이 일어나는 경우가 있음 (Risk of Excessive Repeated Function Calls): 재귀를 사용할 때 같은 함수가 반복적으로 호출될 위험이 있으며, 이는 성능 문제로 이어질 수 있다. 이러한 문제를 해결하기 위해 동적 프로그래밍에서는 메모이제이션 같은 최적화 기법이 자주 사용된다.

동적 프로그래밍 # 2:

장단점 (Pros and Cons of Dynamic Programming)

💡요약: 재귀적 알고리즘은 정렬(sort), 계승(factorial) 계산과 같은 특정 문제에 적합하지만, 피보나치 수열처럼 중복 계산이 많은 경우 비효율적이 될 수 있다. 이런 경우에는 메모이제이션(Memoization) 같은 기법을 사용하여 중복 계산을 줄이는 것이 좋다.

✅ Desirable Examples of Recursive Solutions (재귀적 해법의 바람직한 예): 재귀가 효율적이고 적절하게 쓰이는 경우를 나타낸다. 예를 들어,

  • 퀵 정렬(Quick Sort)과 병합 정렬(Merge Sort) 같은 정렬 알고리즘(Sorting Algorithms)은 큰 문제를 작은 부분 문제로 나눠 효율적으로 해결한다.

  • 계승(Factorial) 계산은 작은 값부터 쌓아 올라가며 단순한 계산으로 이어지기 때문에 재귀적 접근이 적합하다.

  • 그래프의 DFS (Depth-First Search)는 그래프의 각 노드를 재귀적으로 방문하여 탐색하는데, 재귀가 간단하고 효과적이다.

✅ Inefficient Examples of Recursive Solutions (재귀적 해법이 치명적인 예): 재귀가 비효율적일 수 있는 경우를 나타낸다. 예를 들어,

  • 피보나치 수(Fibonacci Sequence)는 단순 재귀로 계산할 경우, 같은 값을 여러 번 계산하게 되어 불필요한 중복이 발생하게 된다.

  • 행렬 곱셈 최적 순서(Matrix Chain Multiplication) 문제에서는 최적의 순서를 찾는 데 많은 계산이 필요하므로, 단순한 재귀로는 매우 비효율적일 수 있다.

동적 프로그래밍 # 3:

Calculating Fibonacci Sequence - Recursive Formula
(피보나치 수 구하기 - 점화식)

💡요약: 피보나치 수열 계산은 동적 프로그래밍의 필요성을 보여주는 대표적인 예시이다. 단순한 재귀로 해결할 수 있지만, 메모이제이션을 통해 성능을 크게 향상시킬 수 있다.

✅ Recursive Formula (점화식): 피보나치 수열의 각 요소는 이전 두 요소의 합으로 정의된다. f(n)은 수식을 의미하고 f(1)은 초기값을 뜻한다.

  • 위의 피보나치 수열 계산은 매우 간단한 문제처럼 보이지만, 동적프로그래밍의 동기(motivation)과 구현이 포함되어있다.

동적 프로그래밍 # 4:

Calculating Fibonacci Sequence - Recursive Algorithm
(피보나치 수 구하기 - 재귀적 알고리즘)

💡요약: 아래 이미지는 피보나치 수열을 재귀적으로 계산하는 방법을 설명하며, 기본적인 알고리즘 구조와 그로 인한 비효율성을 보여준다.

✅Basic Recursive Approach (기본 재귀적 접근): 피보나치 수열에서 f(n)은 f(n−1)과 (n−2)의 합으로 정의된다.

fib(n):
    if (n = 1 or n = 2)
        then return 1;
    else return (fib(n-1) + fib(n-2)

✅ Excessive Duplicate Calls (엄청난 중복 호출): 이 재귀적 접근은 같은 값을 여러 번 중복 계산하게 되어 성능이 매우 떨어진다. 예를 들어, fib(5)를 계산할 때 fib(3)이 여러 번 호된다.

동적 프로그래밍 # 5:

Calculating Fibonacci Sequence - Function Call Tree
(피보나치 수 구하기 - 함수 호출 트리)

💡요약: 피보나치 수열을 계산할 때 발생하는 중복 호출(Duplicate Calls) 문제를 함수 호출 트리를 통해 시각적으로 보여주는 예제이다. 이는 재귀적으로 피보나치 수를 계산할 때 같은 함수가 여러 번 호출되며, 성능이 떨어지는 원인을 설명한다.

✅ Duplicate Calculations (중복 계산): 피보나치 수를 단순 재귀로 계산할 때, 같은 값이 여러 번 계산된다. 예를 들어, fib(7)을 계산하기 위해 fib(6)과 fib(5)가 호출되며, fib(6)을 계산할 때 다시 fib(5)와 fib(4)가 호출된다. 이 과정에서 fib(2)와 같은 값이 여러 번 중복으로 호출되는 것을 볼 수 있다.

✅ Performance Issue (성능 문제): 중복 호출은 계산량을 기하급수적으로 증가시키며, 큰 입력값에 대해 계산 속도가 크게 떨어지게 된다.

동적 프로그래밍 # 6:

Calculating Fibonacci Sequence - Bottom-Up Approach
(피보나치 수 구하기 - bottom up 방식)

💡요약: 피보나치 수열을 동적 프로그래밍의 Bottom-Up 방식으로 계산하는 알고리즘을 소개한다. 이 방식의 동적 프로그래밍은 재귀나 메모이제이션이 없어도 피보나치 수열을 효율적으로 계산할 수 있다. 이전 값들을 저장하여 빠르게 다음 값을 계산하는, 작은 문제부터 차례대로 계산하여 마지막 결과를 얻는 방식이다.

Bottom-up 방식의 특징

  • 이 알고리즘은 반복문을 사용하여 n번 순회하므로 O(n)의 선형 시간 복잡도를 가진다.

  • 재귀 방식(top-down)보다 효율적이다.

fibonacci(n):
    f[1] ← f[2] ← 1; #초기화
    for i ← 3 to n #반복문
        f[i] = f[i - 1] + f[i - 2]
    return f[n] #결과반환

  • fibonacci(n): 함수 이름이며, 입력값 n에 대해 피보나치 수열의 n번째 값을 계산한다.

  • 초기화: 피보나치 수열의 첫 번째(f[1])와 두 번째(f[2]) 값은 1로 초기화된다. 이는 피보나치 수열의 기본 조건이다. f[1] = 1 (첫 번째 항), f[2] = 1 (두 번째 항)

  • 반복문: i를 3부터 n까지 순회하며, 피보나치 수열의 값을 계산한다. 각 단계에서 f[i]는 이전 두 값의 합으로 정의된다. f[i] = f[i-1] + f[i-2]

    • 예를들어, f[3] = f[2] + f[1] 나 f[4] = f[3] + f[2] 와 같이 계속해서 n번째 항까지 계산한다.

  • 결과반환: 계산된 f[n] 값을 반환한다. 이 값이 입력된 n번째 피보나치 수이다.

💡예제: fibonacci(5)를 실행할 경우

  • f[1] = 1, f[2] = 1

  • f[3] = f[2] + f[1] = 1 + 1 = 2

  • f[4] = f[3] + f[2] = 2 + 1 = 3

  • f[5] = f[4] + f[3] = 3 + 2 = 5

  • 결과: f[5] = 5

동적 프로그래밍 # 7:

Calculating Fibonacci Sequence - Top down Approach
(피보나치 수 구하기 - Top down 방식)

💡요약: Top-Down 방식의 동적 프로그래밍은 재귀 호출과 메모이제이션을 결합하여 효율적인 피보나치 계산을 제공한다. 이는 중복 계산을 피하고, 필요한 값만 계산하도록 하여 성능을 최적화하게 된.

  • Top-Down Approach (탑다운 방식): 이 방식은 재귀 호출을 사용하여 큰 문제를 작은 문제로 쪼개지만, 이전에 계산된 값을 저장해 두어 다시 계산하지 않는 방식이다.

    • 배열 f의 모든 원소를 0으로 초기화한다. f[n] 값이 0이 아니면 이미 계산된 값으로 간주하여 바로 반환하게 된다.

    • f[1]과 f[2]는 1로 설정하고, 이후 f[n]이 처음 계산될 때만 재귀 호출을 통해 값을 구한다.

  • Memoization (메모이제이션): 이미 계산된 값을 저장하여 중복 호출을 방지하고 성능을 향상시킨다. 즉, 피보나치 수열에서 한 번도 계산되지 않은 값은 0으로 표시되며, 이를 통해 추가 계산을 하지 않게 한다. 중복 호출을 방지하므로 시간 복잡도는 O(n)으로 줄어들게 된다.

fib(n): #함수정의
    if(f[n] ==! 0) return f[n] #값이 이미 계산된 경우
    else #값이 계산되지 않은 경우
        if(n=1 or n=2) f[n] ← 1
        else f[n] ← fib(n-1) + fib(n-2);
        return f[n] #결과반환

초기 조건: 배열 f의 모든 원소는 0으로 초기화되어야 한다. f[n]의 값이 0이면 해당 값이 아직 계산되지 않았음을 의미한다.

함수 정의: 입력값 n에 대해 피보나치 수열의 n번째 값을 계산한다.

값이 이미 계산된 경우: f[n]이 0이 아니라면, 이미 계산된 값이므로 바로 반환한다. 이는 메모이제이션의 핵심이다. 중복 계산을 방지하여 실행 시간을 단축시키기 때문이다.

값이 계산되지 않은 경우: 만약 f[n]이 계산되지 않았다면: n = 1 또는 n = 2인 경우, 초기 조건에 따라 f[n] = 1로 설정한다. 그렇지 않다면(else) 재귀적으로 fib(n-1)과 fib(n-2)를 호출하여 두 값을 더한 값을 저장한다.

결과반환: 계산된 f[n]값을 반환한다.

💡예시: fib(5)를 호출한다고 가정하면 fib(5)는 다음과 같이 계산된다.

    1. fib(5) 호출: f[5] = fib(4) + fib(3)

      1. fib(4) 호출: f[4] = fib(3) + fib(2)

      2. fib(3) 호출: f[3] = fib(2) + fib(1)

      3. 계산된 값을 메모이제이션하여 중복 호출을 방지: f[2] = 1, f[1] = 1

결과적으로: f[3] = 2, f[4] = 3, f[5] = 5

👀공통점과 차이점 (Bottom-up vs Top-down) 👀

💡요약: Bottom-Up 방식은 메모이제이션을 필요로 하지 않으며 반복문으로 순차적으로 계산하기 때문에 재귀 호출의 오버헤드가 없는 반면, Top-Down 방식은 재귀 호출로 인해 복잡도가 증가할 수 있지만, 문제를 점진적으로 해결할 수 있다는 장점이 있다. 상황에 따라 두 방식 중 더 적합한 방식을 선택하여 사용한다.

공통점(Common)

  1. 중복 계산 방지(Prevent duplicated calculation): 두 방식 모두 피보나치 수열과 같은 문제에서 중복 계산을 방지하여 효율성을 높이는 역할을 한다. 이를 통해 각 부분 문제를 한 번만 계산하게 된다.

  2. 메모리 사용(Using memory): 두 방식 모두 이전 계산 결과를 저장하여 다음 계산에 활용하기 때문에 메모리를 사용하여 결과를 저장한다. 저장 공간을 통해 최적화된 계산이 가능해진다.

  3. 동적 프로그래밍(Dynamic Programming): 두 방식 모두 동적 프로그래밍 기법을 이용하며, 문제를 작은 부분 문제로 나누어 해결하는 접근 방식이다.

차이점(Difference)

  • Bottom-Up 방식은 작은 문제부터 순서대로 계산을 누적해 나가며 최종 값을 얻는 방식이다. 예를 들어, 피보나치 수열을 계산할 때 f[1], f[2]부터 시작하여 f[n]까지 순서대로 값을 채운다.

  • Top-Down 방식은 큰 문제를 작은 문제로 분할하면서 필요한 값만 계산한다. 재귀적으로 큰 문제를 풀고, 이미 계산한 부분은 저장(메모이제이션)하여 다시 계산하지 않도록 한다.

동적 프로그래밍 # 8: 동적 프로그래밍의 적용요건(Conditions for Applying Dynamic Programming)

💡요약: 동적 프로그래밍은 특정 유형의 문제에서만 효과적으로 사용될 수 있으며, 아래 조건을 만족해야 합니다. 1) 최적 부분구조(optimal substructure) 2)중복 호출(overlapping recursive calls)의 특성을 가진 문제에 적합하다. 이러한 문제에서 동적 프로그래밍은 중복 계산을 방지하고, 최적의 해결책을 빠르게 찾는 데 효과적이다.

✅Optimal Substructure (최적 부분구조): 큰 문제의 최적 해결책에 작은 문제의 최적 해결책이 포함되는 구조이다.

  • 예를 들어, 피보나치 수열에서 f(n) 값은 f(n-1)과 f(n-2) 값을 더해 계산됩니다. 각각의 작은 문제(f(n-1), f(n-2))가 최적의 해결책을 제공할 때 큰 문제(f(n))도 최적의 해결책을 가질 수 있게 되는 것과 같다.

✅Overlapping Recursive Calls (재귀호출 시 중복): 재귀적 방법으로 문제를 풀 때 같은 문제에 대한 호출이 반복적으로 일어나는 경우이다.

  • 피보나치 수열을 단순 재귀로 계산할 경우, f(2)와 같은 값이 여러 번 계산되는데, 동적 프로그래밍은 이미 계산된 값을 저장하여 이 중복 호출을 방지함으로써 효율성을 높일수 있다.

2️⃣ 행렬 경로 문제 (Matrix Path Problem)

💡요약: 행렬 경로 문제(Matrix Path Problem)를 설명한다. 제한된 이동 조건에서 행렬의 한쪽 끝에서 다른 쪽 끝까지 이동할 때 방문한 칸의 값을 최소화하는 문제이다. 이 문제는 동적 프로그래밍의 대표적인 문제로, 최적의 경로를 찾기 위해 각 단계에서 최소 비용을 계산한다.

✅ Problem Analysis (문제 분석):

  • 주어진 n × n 행렬에서 왼쪽 위(좌상단)에서 출발하여 오른쪽 아래(우하단)로 이동한다.

✅ Movement Constraints (제한된 이동 조건)

  • 오른쪽(right) 또는 아래쪽(down)으로만 이동할 수 있다.

  • 왼쪽(left), 위쪽(up), 대각선(diagonal) 방향 이동은 허용되지 않는다.

✅Objective (목표)

  • 왼쪽 위에서 시작하여 오른쪽 아래로 이동하면서 방문한 칸의 숫자를 더한 값이 최소화되도록 경로를 찾는 것

행렬 경로 문제 # 1:행렬 경로 문제에서 불법 이동의 예 (Examples of Illegal Moves in the Matrix Path Problem)

💡요약: 행렬 경로 문제에서 경로를 찾을 때 오른쪽(right)과 아래쪽(down)으로만 이동할 수 있다. 위쪽(up)이나 왼쪽(left)으로의 이동은 불법 이동(Illegal Move)으로 간주된다.

  • Illegal Move (상향 이동): 행렬에서 위쪽(상향)으로 이동하는 것은 허용되지 않는다. 첫 번째 그림에서 상향 이동이 발생한 부분이 강조되어 있다.

  • Illegal Move (좌향 이동): 행렬에서 왼쪽(좌향)으로 이동하는 것도 허용되지 않는다. 두 번째 그림에서 좌향 이동이 발생한 부분이 강조되어 있다.

행렬 경로 문제 # 2: 행렬 경로 문제에서 유효한 이동 예시와 최소 합 계산 (Example of Valid Moves in the Matrix Path Problem with Minimum Sum Calculation)

  • Valid Moves (유효한 이동): 행렬의 경로에서 오른쪽(→)과 아래쪽(↓)으로 이동하는 경로만 유효한 이동으로 간주된다. 두 그림에서 각 경로는 이동 제약 조건을 준수하며, 경로의 모든 숫자를 더한 값이 최소화되는 최적 경로이다.

  • Minimum Path Sum (최소 합 계산): 유효한 경로의 모든 숫자를 더하여 최소합을 계산한다. 각 칸까지 도달하는 최소 비용을 동적 프로그래밍으로 계산할 수 있으며, 마지막 칸의 값이 최소합이 된다.

행렬 경로 문제 # 3: 행렬 경로 문제 - 재귀적 의사코드 Matrix Path Problem (Recursive Pseudo-Code)

💡요약: 행렬 경로 문제(Matrix Path Problem)를 재귀적으로 해결하기 위한 의사코드를 소개한다. 이 코드는 특정 위치 (i, j)까지의 최고 점수(maximum score)를 계산한다. 재귀적 접근 방식을 사용하여 각 칸까지의 점수를 계산하며, 이전 경로의 최대 점수를 이용해 최적 경로를 찾는다.

아래는 해당 의사코드를 Python 코드로 변환한 예제입니다.

def matrix_path(matrix, i, j):
    # 기저 사례: 행렬의 경계에 도달했을 때
    if i == 0 or j == 0:
        return 0
    # 재귀 호출 (Recursive Step)
    return matrix[i][j] + max(matrix_path(matrix, i - 1, j), matrix_path(matrix, i, j - 1))

# 예제 행렬
matrix = [
    [0, 0, 0, 0],
    [0, 6, 7, 12, 5],
    [0, 5, 3, 11, 18],
    [0, 7, 17, 3, 3],
    [0, 8, 10, 14, 9]
]
# 예제 호출
# (3,3) 위치까지의 최고 점수를 출력
print(matrix_path(matrix, 3, 3))

위의 의사코드는 (i, j) 위치까지 가는 경로 중에서 가장 높은 점수를 찾기 위한 재귀적 방법을 보여준다.왼쪽과 위쪽에서 오는 경로 중 더 높은 점수를 선택해 누적하는 방식으로 최적의 경로를 찾는다.

✅ matrixPath(i, j) : (i, j) 위치까지 이동할 때 얻을 수 있는 최고 점수를 계산하는 함수

✅ 기저 사례(Base Case): i = 0 또는 j = 0이라는 것은 경로가 행렬의 가장 왼쪽 열이나 위쪽 행에 있다는 의미이다. 이 경로는 경계에 도달한 것으로 간주하여 더 이상 이동할 수 없으므로 0을 반환한다. 이 값은 더 이상 경로가 없음을 나타낸다.

✅ 재귀 호출(Recursive Step): m[i][j]는 (i, j) 위치의 값이고 matrixPath(i - 1, j)는 위쪽에서 오는 경로의 최고 점수이고 matrixPath(i, j - 1)는 왼쪽에서 오는 경로의 최고 점수이다. (i, j) 위치에서 얻을 수 있는 점수는 현재 위치의 값 m[i][j]에, 위쪽 경로와 왼쪽 경로 중에서 더 큰 점수를 더한 값이 된다.

행렬 경로 문제 # 4: 행렬 경로 문제에서 호출 트리 예시와 중복 호출 (Example of Call Tree in Matrix Path Problem Showing Redundant Calls)

💡요약: 행렬 경로 문제(Matrix Path Problem)를 해결할 때 발생하는 중복 호출(Redundant Calls) 문제를 호출 트리(Call Tree)를 통해 시각적으로 알아보자. 특정 위치까지의 경로 점수를 계산하기 위해 재귀적으로 호출을 진행할 때 같은 위치가 여러 번 계산되는 단점이다.

🤔호출 트리(Call Tree) : 재귀 호출이 진행되는 과정을 트리 구조로 나타낸 것

  • Redundant Calls (중복 호출): 예를 들어, mat(2, 1) 위치가 여러 번 반복 호출되는 것을 확인할 수 있다. 이런 중복 호출은 동일한 위치에 대해 계속해서 점수를 재계산하므로, 시간이 많이 걸리고 비효율적이다.

  • Performance Issue (성능 문제): 중복 호출이 많아질수록 연산량이 기하급수적으로 증가하게 된다. 특히 큰 행렬에서는 이러한 중복 호출이 성능에 큰 영향을 미친다.

  • Solution (해결 방법): 이 문제를 해결하기 위해 메모이제이션(Memoization)을 사용할 수 있다. 이미 계산된 위치의 점수를 저장해두고, 동일한 위치를 다시 호출할 때는 저장된 값을 사용하는 방식이다. 이를 통해 중복 호출을 방지하고 계산 시간을 크게 줄일 수 있게 된다.

행렬 경로 문제 # 5: 행렬 경로 문제 - 동적 프로그래밍 (Matrix Path Problem using Dynamic Programming)

💡요약: 중복 계산을 줄이기 위해, 이전에 계산된 값을 테이블에 저장하여 재사용하는 방식으로 행렬 경로 문제(Matrix Path Problem)를 동적 프로그래밍(DP) 방식으로 해결하는 의사코드이다.

✅ matrixPath(n) : (n, n) 위치까지 가는 경로에서 얻을 수 있는 최고 점수를 계산한다.

✅ for i ← 0 to n c[i, 0] ← 0; : 행렬의 첫 번째 열 c[i, 0]을 0으로 초기화한다. 경로가 행렬의 가장 왼쪽 끝에 있는 경우 더 이상 왼쪽으로 이동할 수 없으므로, 왼쪽 경계에 있는 칸들은 초기 값 0으로 설정한다.

✅ for j ← 1 to n c[0, j] ← 0; 행렬의 첫 번째 행 c[0, j]을 0으로 초기화한다. 경로가 행렬의 가장 위쪽에 있는 경우 더 이상 위로 이동할 수 없으므로, 위쪽의 경계에 있는 칸들 또한 초기 값 0으로 설정한다.

✅ for i ← 1 to n for j ← 1 to n c[i, j] ← m[i][j] + max(c[i - 1, j], c[i, j - 1]);
: (i, j) 위치에서 얻을 수 있는 최고 점수를 계산하는 함수이다. m[i][j]는 현재 위치 (i, j)의 점수를 뜻한다. c[i - 1, j]는 위쪽 칸의 최고 점수이며, c[i, j - 1]은 왼쪽 칸의 최고 점수이다. 두 값 중 더 큰 값에 m[i][j]를 더하여 c[i, j]에 저장하는 방식이다.

✅ return c[n, n]; (n, n) 위치까지의 최고 점수를 반환한다. 이 값이 (n, n) 위치까지 가는 경로 중에서 가장 높은 점수의 합이 된다.

💡예제: 위의 의사코드를 Python 코드로 변환한 예제를 살펴본다.

def matrix_path_dp(matrix):
    n = len(matrix) - 1
    # DP 테이블 초기화
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    # 첫 번째 열 초기화
    for i in range(1, n + 1):
        dp[i][0] = 0

    # 첫 번째 행 초기화
    for j in range(1, n + 1):
        dp[0][j] = 0

    # DP 테이블 채우기
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            dp[i][j] = matrix[i][j] + max(dp[i - 1][j], dp[i][j - 1])

    # 결과 반환
    return dp[n][n]

# 예제 행렬
matrix = [
    [0, 0, 0, 0, 0],
    [0, 6, 7, 12, 5],
    [0, 5, 3, 11, 18],
    [0, 7, 17, 3, 3],
    [0, 8, 10, 14, 9]
]

# 예제 호출
print(matrix_path_dp(matrix))  # 최적 경로의 최고 점수 출력

위 코드의 함수인 matrix_path_dp(matrix) 는 동적 프로그래밍을 사용하여 최고 점수를 계산하였다. 중복 계산 없이 각 위치에서 최적의 값을 누적해가므로 효율적이다. 참고로 이 방식은 Bottom-Up 방식의 동적 프로그래밍이다. (1차시에서 언급됨) Bottom-Up 방식은 작은 문제부터 시작해 점진적으로 큰 문제를 해결하는 방식으로, 주로 반복문을 사용하여 각 단계별로 결과를 누적해 나가는 특징이 있다.

3️⃣ 돌 놓기 문제 (Stone Placing Problem)

💡요약: 돌 놓기 문제는 3×N 테이블에 제약 조건을 지키면서 최대 합이 되도록 돌을 놓는 최적화 문제이다. 이 문제를 동적 프로그래밍을 통해 해결 할 수 있다.

✅Table Setup (테이블 구성)

  • 3×N (3행 N열) 크기의 테이블이 주어지고, 각 칸에는 양수 또는 음수의 정수가 기록되어 있다.

✅Stone Placing Constraints (제약 조건)

  • 돌은 가로나 세로로 인접한 두 칸에 동시에 놓을 수 없다. 즉, 같은 열의 인접한 칸이나 같은 행의 인접한 칸에 돌을 놓을 수 없다. 또한 각 열에는 적어도 하나 이상의 돌을 놓아야 한다.

✅ Objective (목표)

  • 돌이 놓인 칸에 있는 수의 합이 최대가 되도록 돌을 놓는 것이다.

돌 놓기 문제 # 1: 합법적인 예와 합법적이지 않은 예

(Stone Placing Problem - Valid and Invalid Examples)

💡요약: 각 열에 최소 한 개의 돌을 놓되, 인접한 위치에 놓지 않도록 돌을 배치하는 제약조건을 가진 최적화 문제의 예시이다. 이를 통해 돌이 놓인 칸들의 값의 합이 최대가 되도록 하는 것이 목표로 한다.

✅합법적인 예

  • 파란색으로 표시된 칸들이 돌이 놓인 위치이다.

  • 돌을 놓는 위치가 가로와 세로로 인접하지 않아 제약 조건을 모두 충족한다.

✅합법적이지 않은 예

  • 빨간색으로 표시된 칸들이 제약 조건을 위반한 위치이다.

  • 돌이 놓인 칸이 가로 또는 세로로 인접하여 Violation (위반)이 발생하였다. 예를 들어, (2, 2) & (2, 3)에 위치해있는 숫자 10과 14는 이 동시에 놓여 가로로 인접하는 위반이 발생하였다. [행(i), 열 (j)]

돌 놓기 문제 # 2: 조약돌 놓기 문제의 가능한 패턴 (Possible Patterns for Placing Stones)

💡요약: 돌 놓기 문제에서 돌을 놓을 수 있는 4가지의 가능한 패턴을 알아보자. 돌을 놓는 방식에는 제약 조건이 있기 때문에 각각의 열에 돌을 놓으면서 위반되지 않는 배치 패턴은 이 4가지로 제한되게 된다.

  • Pattern 1: 첫 번째 행에 돌을 놓는 패턴이다. 이 경우에는 해당 열에서 첫 번째 행에만 돌이 놓이며, 다른 행에 놓지 않는다.

  • Pattern 2: 두 번째 행에 돌을 놓는 패턴이다. 이 패턴에서는 각 열의 두 번째 행에만 돌이 놓이며, 첫 번째와 세 번째 행에는 놓지 않는다.

  • Pattern 3: 세 번째 행에 돌을 놓는 패턴이다. 이 경우에는 세 번째 행에만 돌이 놓이며, 첫 번째와 두 번째 행에는 놓지 않는다.

  • Pattern 4: 첫 번째와 세 번째 행에 돌을 놓는 패턴이다. 두 개의 행에 돌을 놓을 수 있는 유일한 경우이며, 두 번째 행에는 돌을 놓지 않는다.

돌 놓기 문제 # 3: 돌 놓기 문제의 서로 양립할 수 있는 패턴들(Compatible Patterns for Stone Placement)

💡요약: 돌 놓기 문제에서 사용 가능한 4가지 패턴이 서로 양립할 수 있는 방법을 알아본다.

특징

✅“양립할 수 있다"는 의미

두 패턴이 가로 또는 세로로 돌이 인접하지 않는 경우, 서로 양립 가능하다고 정의된다. 즉 특정 패턴 간 양립 가능 여부는, 두 패턴을 결합했을 때 규칙 위반(가로 또는 세로 인접)이 발생하지 않는 경우를 뜻한다.

✅ 패턴의 구조

각 패턴은 세로로 3칸짜리 열(column)로 구성되어 있다.

파란색 원은 돌이 놓인 위치를 나타낸다.

각 열은 해당 위치에 돌을 놓는 규칙에 따라 다르게 구성된다.

✅ 패턴 번호

패턴 1 ~ 패턴 4로 나뉘며, 각 패턴은 서로 다른 방식으로 돌이 배치된 상태를 나타낸다.

  1. 패턴 1: 첫 번째 열에서 첫 번째 행에만 돌을 놓는 방식.

    • 양립 가능: 패턴 2, 패턴 3과 양립 가능.

  2. 패턴 2: 첫 번째 열에서 두 번째 행에만 돌을 놓는 방식.

    • 양립 가능: 패턴 1, 패턴 3, 패턴 4와 양립 가능.

  3. 패턴 3: 첫 번째 열에서 세 번째 행에만 돌을 놓는 방식.

    • 양립 가능: 패턴 1, 패턴 2와 양립 가능.

  4. 패턴 4: 첫 번째 열에서 첫 번째와 세 번째 행에 돌을 놓는 방식.

    • 양립 가능: 패턴 2와 양립 가능.

  • 양립 규칙: 각 패턴은 인접 열에 다른 특정 패턴들과 함께 사용할 수 있으며, 이는 돌을 놓을 때 겹치지 않도록 하면서 제약을 지키기 위해 필요합니다.

  • 양립 가능한 패턴 활용: 이 규칙을 이용해 인접 열에 돌을 배치할 때 최적의 배치를 찾기 위해 동적 프로그래밍을 사용할 수 있습니다.

  • 이 문제를 통해 문제의 해를 효율적으로 구하거나 경우의 수를 줄일 수 있다.

돌 놓기 문제 #4 : 돌 놓기 문제에서 i열과 i-1열의 관계 (Relationship Between Column iii and Column i−1i-1i−1 in Stone Placing Problem)

💡요약: 돌 놓기 문제에서 현재 열 i와 이전 열 i−1 간의 관계를 설명하고 있다. 이전 열의 패턴에 따라 현재 열에 돌을 놓을 수 있는 방식이 제한되기 때문이다. 이 관계는 동적 프로그래밍을 사용하여 최적 경로를 계산 할 때 매우 중요하게 사용된다.

  • i-1열: 이전 열(i-1열)에는 돌이 3개의 위치에 놓여 있다: -5 (1행), 9 (2행), 4 (3행)

  • i열: 현재 열(i열)에는 돌이 하나(혹은 여러 개) 놓일 수 있다. 파란색으로 강조된 7은 i열의 돌이 놓인 위치를 나타낸다.

  • 연결 조건:

    • 현재 열의 돌 위치는 이전 열의 패턴에 따라 제약을 받는다.

    • i-1열에서 특정 패턴으로 끝났다면, i열의 돌은 해당 패턴과 양립 가능한 위치에만 놓일 수 있다.

i-1열의 패턴 (패턴 1, 3, 4): 이미지에서 언급된 i-1열의 패턴은 다음 세 가지로 정의된다

  1. 패턴 1 (아래 위로 두 칸 떨어진 배치):

    • i-1열의 돌이 패턴 1로 끝난다면, i열의 돌은 해당 규칙을 따라야 함.

  2. 패턴 3 (가장 위와 중간에 위치한 배치):

    • i-1열의 돌이 패턴 3으로 끝났다면, i열의 돌은 패턴 3과 충돌하지 않는 위치에 놓여야 함.

  3. 패턴 4 (중간 칸 위아래로 배치):

    • i-1열의 돌이 패턴 4로 끝났다면, i열의 돌도 패턴 4와 양립 가능한 위치에 놓여야 함.

결론: 각 패턴은 i-1열의 상태를 나타내며, i열에서 가능한 배치를 결정한다. 양립 가능한 패턴만 다음 열로 이어지므로, 가능한 상태 공간을 줄여 효율적으로 계산할 수 있다.

돌 놓기 문제 #5 : 돌 놓기 문제의 재귀적 의사코드 (Recursive Pseudo-Code for Stone Placing Problem)

💡요약: 돌 놓기 문제에서 재귀적으로 최적의 점수 합을 구하기 위한 알고리즘을 공부해본다. 각 열에서 가능한 모든 패턴을 탐색하며 최대 점수를 누적해 나가는 방식이다. 이를 통해 각 열에 대해 최적의 돌 배치와 점수 합을 구할 수 있으며, 동적 프로그래밍(DP) 메모이제이션을 통해 중복 계산을 방지할 수 있게 된다.

pebble(i,p): #함수정의
if (i == 1) return w[1, p] #기저조건(Base Case)
else: #재귀호출(Recursive Case)
    max ← -∞ #최대값 초기화
    for q ← 1 to 4: #반복문
        if (패턴 q가 패턴 p와 양립): #1) 양립 가능한 패턴 확인
            tmp ← pebble(i-1, q) #2) 재귀호출(Recursive Case)
            if (tmp > max) max ← tmp #3) 최대값 갱신
    return (max + w[i, p]) #4) 최종반환값

✅ pebble(i, p): i열에서 패턴 p로 돌을 놓았을 때 i열까지의 최대 점수 합을 구하는 함수이다. w[i, p]는 i열에서 패턴 p로 돌을 놓았을 때 해당 위치의 점수를 뜻한다. p는 {1, 2, 3, 4} 중 하나로, 가능한 돌 놓기 패턴을 의미한다.

✅기저조건(Base Case): 첫 번째 열(i == 1)인 경우

  • 첫 번째 열 (i = 1)에서는 이전 열이 없으므로 단순히 w[1, p] 값을 반환한다. 즉, 첫 번째 열의 해당 패턴에 있는 점수를 반환한다.

✅ 최대값 초기화 : 이후 열(i > 1)에서는 최대 점수를 계산하기 위해 max 변수를 매우 작은 값으로 초기화한다.

✅ 반복문 : 이전 열(i - 1)의 모든 패턴 q를 순회하면서, q와 p가 양립 가능한지 확인한다.

✅재귀호출(Recursive Case) i열의 최대 점수 계산

  1. q와 p가 양립 가능한 패턴일 경우, 이전 열에서 패턴 q를 선택했을 때의 최대 점수를 구하기 위해 pebble(i - 1, q)를 재귀적으로 호출하고 tmp에 저장한다.

  2. pebble(i-1, q)를 호출하여 i-1열까지의 최대 점수를 계산한다.

  3. tmp(i-1열까지의 점수)가 현재 max보다 크면 max를 tmp로 갱신하여 최대값을 유지한다.

  4. 최종적으로, 이전 열까지의 최대 점수 max와 현재 위치의 점수 w[i, p]를 더한 값을 반환한다.

돌 놓기 문제 #6 : 돌 놓기 문제에서 호출 트리 예시와 중복 호출 (Example of Call Tree in Stone Placing Problem Showing Redundant Calls)

💡요약: 위에서 배운 알고리즘의 재귀적 호출 과정에서 발생하는 중복을 알아본다.

✅ 중복된 호출:

  • 여러 노드에서 동일한 pebble(i, p) 함수가 반복적으로 호출되는 것을 볼 수 있다.

  • 예를 들어, pebble(2, 2)는 여러 경로에서 반복적으로 호출되고 있으며, 이는 불필요하게 동일한 계산을 여러 번 수행하게 만든다.

✅ 비효율성:

  • 이러한 중복 호출은 계산 시간이 불필요하게 길어지는 주요 원인이 된다. 동일한 값이 반복적으로 계산되므로, 성능이 저하된다.

✅ 해결 방법:

  • 이 문제를 해결하기 위해 메모이제이션(Memoization)을 사용할 수 있다. 메모이제이션을 사용하면 한 번 계산된 pebble(i, p) 값을 저장해 두고, 같은 요청이 들어올 때 저장된 값을 반환하여 중복 계산을 방지할 수 있게 된다.

돌 놓기 문제 #7 : 돌 놓기 문제에서 DP 적용 조건 (Conditions for Applying Dynamic Programming (DP) in Stone Placing Problem)

💡요약: Optimal Substructure와 Overlapping Subproblems의 두 가지 조건을 만족하기 때문에, 돌 놓기 문제는 동적 프로그래밍을 적용하기 좋은 예제이다. 이렇듯 DP를 사용하면 중복 계산을 방지하여 효율적으로 최적의 점수를 구할 수 있게 된다.

✅ Optimal Substructure (최적 부분 구조):

  • 현재 단계의 최적 해 pebble(i, .)는 이전 단계의 최적 해 pebble(i - 1, .)를 포함한다.

  • 즉, 큰 문제의 최적 해는 작은 문제들의 최적 해를 포함하므로, 부분 문제를 해결하여 큰 문제의 최적 해를 구할 수 있게 된다.

✅ Overlapping Subproblems (중복되는 부분 문제):

  • 재귀적 알고리즘을 사용하면 동일한 부분 문제(예: pebble(i - 1, .))가 여러 번 호출된다.

  • 이러한 중복 호출은 비효율적이므로, 메모이제이션(Memoization)을 사용하여 중복 계산을 줄일 수 있다.

돌 놓기 문제 #8 : 돌 놓기 문제의 동적 프로그래밍 의사코드 (Dynamic Programming Pseudo-Code for Stone Placing Problem)

💡요약: 이 알고리즘은 각 열과 패턴에 대한 점수를 계산하여 DP 테이블에 저장하는 방식이다. 이전 열의 최적 해를 참고하여 현재 열의 최적 해를 구하기 때문에, 계산을 효율적으로 수행할 수 있다. 결과적으로 해당 알고리즘의 최종 목표는 마지막 열에서 가능한 최대 점수를 반환하여 전체 최적 해를 구하는 것이다. 시간 복잡도는 열의 개수 = n, 패턴의 개수 = 4 즉 모든 열에 대해 최대 4개의 패턴 조합을 확인하므로 O(n × 4 × 4) = O(n)의 시간 복잡도를 가진다.

pebble(n): #함수정의
     for p ← 1 to 4: #초깃값 설정
         peb[1, p] ← w[1, p]
     for i ← 2 to n #DP를 통해 점수 계산 ~ 각 열에 대한 반복문 설정
         for p ← 1 to 4 #각 패턴에 대해 최대 점수 계산
                peb[i, p] ← max {peb[i - 1, q]} + w[i, p] #이전 열의 최대값 찾기 및 현재 열 점수 계산
     return max {peb[n,p]} for p = 1, 2, 3, 4 #최종 결과 반환

✅ pebble(n) 열 n까지 돌을 놓았을 때 얻을 수 있는 최대점수를 계산하는 함수이다.

✅ 초깃값 설정 첫 번째 열(열 i = 1)에 대해 각 패턴 p에 따라 점수를 설정한다. p는 가능한 패턴을 의미하며, 여기서 1부터 4까지 4개의 패턴이 있다. peb[1, p] ← w[1, p]: 첫 번째 열에서 패턴 p로 돌을 놓을 때의 점수를 peb[1, p]에 저장합니다. 이는 초기값 설정으로, 첫 번째 열의 점수를 DP 테이블에 기록하는 단계이다. w[1, p]는 1열에서 패턴 p로 돌을 놓았을 때 해당 위치의 점수를 뜻한다.

✅ for i ← 2 to n 각 열에 대한 반복문 설정

  • 두 번째 열(i = 2)부터 마지막 열(i = n)까지 순차적으로 돌을 놓는 경우를 계산한다. 여기서 i는 현재 계산 중인 열을 의미한다.

✅ for p ← 1 to 4 각 패턴에 대해 최대 점수 계산

  • 각 열 i에서 가능한 패턴 p = 1, 2, 3, 4 중 하나를 선택하여 점수를 계산한다. 패턴 p에 따라 돌을 놓는 경우를 하나씩 고려한다.

✅ peb[i, p] ← max {peb[i - 1, q]} + w[i, p] 이전 열의 최대값 찾기 및 현재 열 점수 계산

  • max {peb[i - 1, q]}: 이전 열(i - 1)에서 현재 패턴 p와 양립 가능한 패턴 q 중 최대 점수를 찾는다.

  • w[i, p]: 현재 열 i에서 패턴 p로 돌을 놓을 때의 점수를 의미한다.

  • 이 식은 이전 열의 최적 점수와 현재 열의 점수를 더해 peb[i, p]에 저장한다는 뜻이다. 즉, 현재 열에서 패턴 p로 돌을 놓았을 때 얻을 수 있는 최대 점수를 구할수 있다.

✅ return max { peb[n, p] } for p = 1, 2, 3, 4 최종 결과 반환

  • 마지막 열(i = n)에서 가능한 4개의 패턴 중에서 최대 점수를 선택하여 반환한다.

  • 이를 통해 전체 열에서 돌을 최적 배치하여 얻을 수 있는 최대 점수를 구할 수 있다.

Computer Algorithms

Part 7 of 19

Through this subjects, I will be learning how to think systematically through algorithms and develop problem-solving skills. Also, I'm hoping to learn how to perform programming quickly and efficiently by applying computer algorithms.

Up next

Processing of Disjoint Sets using Union-Find Algorithms (9th weeks)

유니온파인드 알고리즘을 이용한 상호 배타적 집합의 처리

More from this blog

My dev journey

125 posts