# Overview of Dynamic Programming  (1/3)

---

**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)  

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

* **큰 문제안에 작은 문제가 깃들어 있다 (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)

**<mark>💡요약: </mark>** 재귀적 알고리즘은 정렬(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  
(피보나치 수 구하기 - 점화식)

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731824702738/6fcd0657-1071-44ed-89d2-128c3f6ebc0f.png align="center")

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

---

### 동적 프로그래밍 # 4:  
Calculating Fibonacci Sequence - Recursive Algorithm  
(피보나치 수 구하기 - 재귀적 알고리즘)

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

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

```python
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  
(피보나치 수 구하기 - 함수 호출 트리)

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731825192908/2b1179dc-710a-4807-b4aa-ca4b5dc7f9a2.png align="center")

✅ **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 방식)

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

**Bottom-up 방식의 특징**

* 이 알고리즘은 반복문을 사용하여 `n`번 순회하므로 **O(n)**의 선형 시간 복잡도를 가진다.
    
* 재귀 방식(`top-down`)보다 효율적이다.
    

```python
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`번째 피보나치 수이다.
    

**<mark>💡예제:</mark>** `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 방식)

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

* **Top-Down Approach (탑다운 방식)**: 이 방식은 재귀 호출을 사용하여 큰 문제를 작은 문제로 쪼개지만, 이전에 계산된 값을 저장해 두어 다시 계산하지 않는 방식이다.
    
    * 배열 `f`의 모든 원소를 0으로 초기화한다. `f[n]` 값이 0이 아니면 이미 계산된 값으로 간주하여 바로 반환하게 된다.
        
    * `f[1]`과 `f[2]`는 1로 설정하고, 이후 `f[n]`이 처음 계산될 때만 재귀 호출을 통해 값을 구한다.
        
* **Memoization (메모이제이션)**: 이미 계산된 값을 저장하여 중복 호출을 방지하고 성능을 향상시킨다. 즉, 피보나치 수열에서 한 번도 계산되지 않은 값은 0으로 표시되며, 이를 통해 추가 계산을 하지 않게 한다. 중복 호출을 방지하므로 시간 복잡도는 O(n)으로 줄어들게 된다.
    

```python
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]`값을 반환한다.

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

* 1. `fib(5)` 호출: `f[5] = fib(4) + fib(3)`
        
    2. `fib(4)` 호출: `f[4] = fib(3) + fib(2)`
        
    3. `fib(3)` 호출: `f[3] = fib(2) + fib(1)`
        
    4. 계산된 값을 메모이제이션하여 중복 호출을 방지: `f[2] = 1`, `f[1] = 1`
        

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

---

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

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

  
**공통점(Common)**

1. **중복 계산 방지(Prevent duplicated calculation)**: 두 방식 모두 피보나치 수열과 같은 문제에서 중복 계산을 방지하여 효율성을 높이는 역할을 한다. 이를 통해 각 부분 문제를 한 번만 계산하게 된다.
    
2. **메모리 사용(Using memory)**: 두 방식 모두 이전 계산 결과를 저장하여 다음 계산에 활용하기 때문에 메모리를 사용하여 결과를 저장한다. 저장 공간을 통해 최적화된 계산이 가능해진다.
    
3. **동적 프로그래밍(Dynamic Programming)**: 두 방식 모두 동적 프로그래밍 기법을 이용하며, 문제를 작은 부분 문제로 나누어 해결하는 접근 방식이다.  
    

**차이점(Difference)**

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731827519504/b4dac50c-e927-4547-8d4c-db64adb8a28e.png align="center")

* **Bottom-Up 방식**은 작은 문제부터 순서대로 계산을 누적해 나가며 최종 값을 얻는 방식이다. 예를 들어, 피보나치 수열을 계산할 때 `f[1]`, `f[2]`부터 시작하여 `f[n]`까지 순서대로 값을 채운다.
    
* **Top-Down 방식**은 큰 문제를 작은 문제로 분할하면서 필요한 값만 계산한다. 재귀적으로 큰 문제를 풀고, 이미 계산한 부분은 저장(메모이제이션)하여 다시 계산하지 않도록 한다.
    

---

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

**<mark>💡요약:</mark>** 동적 프로그래밍은 특정 유형의 문제에서만 효과적으로 사용될 수 있으며, 아래 조건을 만족해야 합니다. **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)

**<mark>💡요약: </mark>** 행렬 경로 문제(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)

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731893173356/c310df41-037d-49d2-91da-dd118ef62ff9.png align="center")

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

---

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731893438632/1b809128-c852-48a6-909b-423db6ddbb53.png align="center")

* **Valid Moves (유효한 이동)**: 행렬의 경로에서 오른쪽(→)과 아래쪽(↓)으로 이동하는 경로만 유효한 이동으로 간주된다. 두 그림에서 각 경로는 이동 제약 조건을 준수하며, 경로의 모든 숫자를 더한 값이 최소화되는 최적 경로이다.
    
* **Minimum Path Sum (최소 합 계산)**: 유효한 경로의 모든 숫자를 더하여 최소합을 계산한다. 각 칸까지 도달하는 최소 비용을 동적 프로그래밍으로 계산할 수 있으며, 마지막 칸의 값이 최소합이 된다.
    

---

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

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

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

```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))
```

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731894005021/6fcf7d9d-651f-44ed-95ff-4b71a2586f00.png align="center")

위의 의사코드는 `(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)

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731894624238/8c8b06b9-3af6-4c14-8c98-4300d5ab793a.png align="center")

* **Redundant Calls (중복 호출)**: 예를 들어, `mat(2, 1)` 위치가 여러 번 반복 호출되는 것을 확인할 수 있다. 이런 중복 호출은 동일한 위치에 대해 계속해서 점수를 재계산하므로, 시간이 많이 걸리고 비효율적이다.
    
* **Performance Issue (성능 문제)**: 중복 호출이 많아질수록 연산량이 기하급수적으로 증가하게 된다. 특히 큰 행렬에서는 이러한 중복 호출이 성능에 큰 영향을 미친다.
    
* **Solution (해결 방법)**: 이 문제를 해결하기 위해 `메모이제이션(Memoization)`을 사용할 수 있다. 이미 계산된 위치의 점수를 저장해두고, 동일한 위치를 다시 호출할 때는 저장된 값을 사용하는 방식이다. 이를 통해 중복 호출을 방지하고 계산 시간을 크게 줄일 수 있게 된다.
    

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731894826258/bf945505-13c7-47b1-a3a1-23e3c9b01d9d.png align="center")

**✅** `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)` 위치까지 가는 경로 중에서 가장 높은 점수의 합이 된다.

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

```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))  # 최적 경로의 최고 점수 출력
```

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731895323691/f4b5ed0a-1429-40e1-bf34-50eb3ab19ce2.png align="center")

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

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731906159114/3db480e8-0452-41de-b71d-63f53e56b4a6.png align="center")

**✅Table Setup (테이블 구성)**

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

**✅Stone Placing Constraints (제약 조건)**

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

**✅ Objective (목표)**

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

---

### 돌 놓기 문제 # 1: 합법적인 예와 합법적이지 않은 예  
(Stone Placing Problem - Valid and Invalid Examples)

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731906247714/72a9eccc-b256-42e1-bf98-7bcb0fc13110.png align="center")

**✅합법적인 예**

* 파란색으로 표시된 칸들이 돌이 놓인 위치이다.
    
* 돌을 놓는 위치가 가로와 세로로 인접하지 않아 제약 조건을 모두 충족한다.
    

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731906337737/f14e2a67-d738-44f2-a17a-e3f28ba1b1e6.png align="center")

**✅합법적이지 않은 예**

* 빨간색으로 표시된 칸들이 제약 조건을 위반한 위치이다.
    
* 돌이 놓인 칸이 가로 또는 세로로 인접하여 **Violation (위반)**이 발생하였다. 예를 들어, `(2, 2)` & `(2, 3)`에 위치해있는 숫자 10과 14는 이 동시에 놓여 가로로 인접하는 위반이 발생하였다. \[행(i), 열 (j)\]
    

---

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

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731906761455/da77a78a-6512-4371-9cf9-3c61e7907ad0.png align="center")

* **Pattern 1**: 첫 번째 행에 돌을 놓는 패턴이다. 이 경우에는 해당 열에서 첫 번째 행에만 돌이 놓이며, 다른 행에 놓지 않는다.
    
* **Pattern 2**: 두 번째 행에 돌을 놓는 패턴이다. 이 패턴에서는 각 열의 두 번째 행에만 돌이 놓이며, 첫 번째와 세 번째 행에는 놓지 않는다.
    
* **Pattern 3**: 세 번째 행에 돌을 놓는 패턴이다. 이 경우에는 세 번째 행에만 돌이 놓이며, 첫 번째와 두 번째 행에는 놓지 않는다.
    
* **Pattern 4**: 첫 번째와 세 번째 행에 돌을 놓는 패턴이다. 두 개의 행에 돌을 놓을 수 있는 유일한 경우이며, 두 번째 행에는 돌을 놓지 않는다.
    

---

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

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

특징

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

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

**✅ 패턴의 구조**

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

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

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

**✅ 패턴 번호**

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731906900893/5ee9f91c-121a-4116-a970-9a13efc6699e.png align="center")

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)

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731914561069/01dd73fa-b489-4646-997b-7cc87df8f346.png align="center")

* **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)

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

```python
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)

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731928771681/db737cae-bec2-4596-9164-ea719d011ae9.png align="center")

✅ **중복된 호출**:

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

✅ **비효율성**:

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

**✅ 해결 방법**:

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

---

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

**<mark>💡요약: </mark> 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)

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

```python
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개의 패턴 중에서 최대 점수를 선택하여 반환한다.
    
* 이를 통해 전체 열에서 돌을 최적 배치하여 얻을 수 있는 최대 점수를 구할 수 있다.