# Matrix Chain Multiplication(MCM), Travelling salesman problem(TSP) in Dynamic Programming (2/3)
---
**1️⃣** 정수를 1로 만드는 동적 프로그래밍 (Dynamic Programming to Make a Number 1)
**2️⃣** 행렬 곱셈 순서 문제 (Matrix Chain Multiplication, MCM)
**3️⃣** 외판원의 순회 경로 짜기 (Travelling salesman problem, TSP)
---
## Summary
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1732022349374/3f42de8c-b264-4d30-8c02-9e1a00407233.png align="center")
✅ **정수를 1로 만들기**(**Making a Number 1**)
* 목표: 세 가지 연산을 사용하여 주어진 정수를 1로 만드는 최소 연산 횟수를 구한다.
* 접근법: 각 정수에 대한 최소 연산 횟수를 저장하는 DP 테이블을 구성한다.
**✅ 행렬 곱셈 순서 문제(Matrix Chain Multiplication(MCM)**
* 목표: 행렬 곱셈의 연산 수를 최소화하는 곱셈 순서를 찾는다.
* 접근법: 부분 행렬 곱셈의 최소 비용을 계산하고 이를 DP 테이블에 저장한다.
**✅외판원의 순회 경로 문제 (Travelling salesman problem(TSP)**
* 목표: N개의 도시를 최소 비용으로 순회하고 시작점으로 돌아오는 경로를 구한다.
* 접근법: 현재 도시와 방문 상태에서 남은 도시를 순회하는 최소 비용을 DP 테이블로 계산한다.
---
## **1️⃣** 정수를 1로 만드는 동적 프로그래밍 (Dynamic Programming to Make a Number 1)
**💡요약:** 주어진 정수 N을 **1로 만들기 위해 최소한의 연산 횟수**를 구하는 문제이다. 사용할 수 있는 연산은 세 가지로 제한된다. 이 **최소 연산 횟수**를 찾기 위해 동적 프로그래밍(DP)을 사용된다. DP를 사용하면 각 정수에 대해 1로 만드는 최소 횟수를 저장하고, 이미 계산한 결과를 재사용하기 때문에 효율적으로 문제를 해결할 수 있게 된다.
### 사용할 수 있는 연산
1. **3으로 나누기**: x가 3으로 나누어 떨어질 때, **3으로 나눈다**.
2. **2로 나누기**: x가 2로 나누어 떨어질 때, **2로 나눈다**.
3. **1 빼기**: 그 외의 경우 **1을 뺀다**.
이 세 가지 연산을 사용하여, **주어진 정수 N을 1로 만드는 데 필요한 최소 연산 횟수**를 위의 세가지 연산을 적절히 사용해 출력하는 것이 목표이다.
**💡예제:** 어떤 수 x에 대해 최소 연산 횟수를 계산할 때, x의 세 가지 가능한 경우를 고려하여 가장 작은 연산 횟수를 선택한다.
---
### 정수를 1로 만드는 동적 프로그래밍 #1 : 입출력 시뮬레이션 (Input and Output Simulation for Dynamic Programming to Make a Number 1)
**💡요약:** 이 문제의 목표는 정수 N을 최소한의 연산으로 1로 만드는 것이며, 가능한 연산은 **3으로 나누기 (Divide by 3)**, **2로 나누기 (Divide by 2)**, **1 빼기 (Subtract 1)**이다. 단순히 문제를 입력받고 규칙에 따라 연산을 반복적으로 수행하여 결과를 구하는 방식으로 문제를 해결한다. 단순하고 이해하기 쉽지만 숫자가 커질수록 계산량이 증가하여 비효율적이다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731932462163/0500e5c1-83f9-42a4-b4dc-338196bbd1cd.png align="center")
* **입력(Input)**: 하나의 정수 N이 주어지며, NNN은 **1보다 크거나 같고, 10^6보다 작거나 같은 정수**이다.
* **출력(Output)**: 최소한의 연산으로 N을 1로 만들기 위한 **연산 횟수**를 출력한다.
**사용 가능한 연산:**
* N이 3으로 나누어 떨어지면, **3으로 나누기** 연산을 사용한다.
* N이 2로 나누어 떨어지면, **2로 나누기** 연산을 사용한다.
* 그 외의 경우, **1을 뺀다.**
**예제 입력과 출력:**
* **예제 입력 1**: 10, **예제 출력 1**: 3 (10에서 시작하여 5, 4, 2, 1로 만든다. 총 3회 연산)
* **10에서 시작**: 10은 2로 나눌 수 있으므로, **10 ÷ 2 = 5**. (첫 번째 연산)
* **5에서 연산**: 5는 3으로 나눌 수 없고, 2로도 나눌 수 없다. 따라서, **5 - 1 = 4**. (두 번째 연산)
* **4에서 연산**: 4는 2로 나눌 수 있으므로, **4 ÷ 2 = 2**. (세 번째 연산)
* **2에서 연산**: 2는 2로 나눌 수 있으므로, **2 ÷ 2 = 1**. (네 번째 연산)
* **예제 입력 2**: 2
* **예제 출력 2**: 1 (2에서 1로 가기 위해 1회 연산)
---
### 정수를 1로 만드는 동적 프로그래밍 #2: 점화식 (Recurrence Formula for Dynamic Programming to Make a Number 1)
**💡요약:** 점화식 (Recurrence Formula)을 사용하여 최소한의 연산으로 정수를 1로 만드는 방법을 계산해본다. 각 숫자에 대해 가능한 연산을 수행한 결과 중 최소 값을 선택하여 최적의 해를 구한다.
위에서 언급된 입출력 시뮬레이션을 점화식으로 표현하여 동적 프로그래밍의 원리를 적용할 것이다. 시뮬레이션 방식은 숫자가 커질수록 비효율적이지만, 동적 프로그래밍은 계산 결과를 저장하여 중복 계산을 방지하므로 효율적이다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731933542051/6ee43834-d398-46ad-b379-25bd97a8322d.png align="center")
* 각 숫자 i에 대해 **1 빼기 (Subtract 1)**, **2로 나누기 (Divide by 2)**, **3으로 나누기 (Divide by 3)** 세 가지 연산 중 가능한 모든 연산을 수행한다.
* 각 연산에서 최소 값을 선택하여 **최소 연산 횟수 테이블 (D\[i\])**을 업데이트한다.
* 마지막으로 D\[N\]에는 N을 1로 만들기 위한 최소 연산 횟수가 저장된다.
**✅** `D[i] = D[i - 1] + 1`: 현재 수에서 **1을 빼는 연산**을 하는 경우, 이전 단계의 최소 연산 횟수 D\[i - 1\]에 1을 더한다.
**✅** `if(i % 2 == 0) D[i] = min(D[i], D[i / 2] + 1)`: i가 2로 나누어 떨어질 때, **2로 나누는 연산**을 사용한다. 이때, D\[i\]는 **D\[i / 2\] + 1**과 기존의 D\[i\] 값 중 **작은 값**으로 업데이트 된다.
**✅** `if(i % 3 == 0) D[i] = min(D[i], D[i / 3] + 1)` : i가 3으로 나누어 떨어질 때, **3으로 나누는 연산**을 사용한다. 이때, D\[i\]는 **D\[i / 3\] + 1**과 기존의 D\[i\]값 중 **작은 값**으로 업데이트 된다.
---
### 정수를 1로 만드는 동적 프로그래밍 #3: DP 테이블 (DP Table for Dynamic Programming to Make a Number 1)
**💡요약:** DP 테이블 (DP Table)은 **동적 프로그래밍 (Dynamic Programming)**에서 중간 계산 값을 저장해 두는 배열이다. 이를 통해, 이미 계산한 값을 다시 계산하지 않고 테이블에서 가져와 사용할 수 있어 **중복 계산을 줄이고 효율성**을 높일 수 있다. 아래의 3가지 연산 방법 들은 연산 중 하나일 뿐, 최종 최소값이 아닐 수도 있다. **모든 연산 결과를 비교**하여 가장 작은 값을 선택하는 것이 핵심이다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731938826238/f426e6d5-d2c3-49f8-b79e-81e0a6b9c0a8.png align="center")
숫자를 1로 만들기 위해 각 숫자마다 필요한 **최소 연산 횟수**를 계산하여 테이블에 저장한다. 예를 들어, 숫자 6을 1로 만들기 위한 최솟값을 계산할 때 세 가지 연산 중 가능한 최솟값을 찾게된다.
**예제 1: 숫자 2를 1로 만들기 : D\[2\]의 경우**
1. 연산 중 **1을 빼는 연산**을 선택하면, D\[2−1\] + 1 = D\[1\] + 1 = 1 이 된다.
2. 연산 중 **2로 나누는 연산**을 선택할 수도 있다. D\[2/2\] + 1 = D\[1\] + 1 = 1 이 된다.
따라서, **D\[2\]의 값은 1**이다. 즉, 숫자 2를 1로 만들기 위한 최소 연산 횟수는 1이 된다.
---
**예제 2: 숫자 6을 1로 만들기 : D\[6\]의 경우**
1. **1을 빼는 연산**을 선택하면, D\[6−1\] + 1 = D\[5\] + 1 = 4 가 된다.
2. **2로 나누는 연산**을 선택하면, D\[6/2\] + 1 = D\[3\] + 1 = 2가 된다.
3. **3으로 나누는 연산**을 선택하면, D\[6/3\] + 1 = D\[2\] + 1 = 2 가 된다.
이 세 가지 방법 중 **최솟값은 2**이다. 따라서, **D\[6\]의 값은 2**이며, 숫자 6을 1로 만들기 위한 최소 연산 횟수는 2가 된다.
---
**예제 3: 숫자 10을 1로 만들기: D\[10\]의 경우**
1. **1을 빼는 연산**을 선택하면, D\[10−1\] + 1 = D\[9\] + 1 = 3이 된다.
2. **2로 나누는 연산**을 선택하면, D\[10/2\] + 1 = D \[5\] + 1 = 4가 된다.
두 가지 방법 중 **최솟값은 3**이다. 따라서, **D\[10\]의 값은 3**이며, 숫자 10을 1로 만들기 위한 최소 연산 횟수는 3이 된다.
✅ **5 + 1**을 계산하는 것이 아니라, **D\[5\] + 1**에서 **D\[5\]**의 값을 가져와서 거기에 1을 더하는 것이다.
---
### 정수를 1로 만드는 동적 프로그래밍 #4: DP 테이블 의사코드 (DP Table pseudocode for Dynamic Programming to Make a Number 1)
**💡요약: ** 이 과정은 Bottom-Up 방식으로, 작은 문제를 해결해가면서 점점 큰 문제를 해결하는 방식이다. 각 정수에 대해 최적의 연산 방법을 찾기 위해 가능한 연산 결과 중 가장 작은 값을 DP 테이블에 저장하여, 반복 계산을 줄이는 방법을 설명한다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731939841654/ac2dc85f-f1af-4a1c-b693-8b127c58c5ca.png align="center")
* **D\[i\]**는 **i를 1로 만들기 위한 최소 연산 횟수**를 저장하는 배열이다.
* 1에서 시작하여 **2부터 N까지** 순차적으로 최소 연산 횟수를 계산한다.
* 가능한 세 가지 연산이 있다
* **1을 빼는 연산**: `D[i-1] + 1`
* **2로 나누는 연산**: `D[i/2] + 1` (2로 나누어떨어질 때만 적용)
* **3으로 나누는 연산**: `D[i/3] + 1` (3으로 나누어떨어질 때만 적용)
* 각 연산에서 **가장 작은 값**을 **D\[i\]**에 저장하여 진행한다.
---
### 정수를 1로 만드는 동적 프로그래밍 #5: 파이썬으로 구현 (Python DP Table for Dynamic Programming to Make a Number 1)
**💡요약: 파이썬 코드(Python Code)**로 구현한 예제이다. 동적프로그래밍 기법이 사용되었다.
```python
import sys
input = sys.stdin.readline
N = int(input())
D = [0]*(N+1)
D[1] = 0
for i in range(2, N + 1):
D[i] = D[i - 1] + 1
if i % 2 == 0:
D[i] = min(D[i], D[i // 2] + 1)
if i % 3 == 0:
D[i] = min(D[i], D[i // 3] + 1)
print(D[N])
```
✅`import sys`: **표준 입력을 빠르게 받기 위해** `sys` 모듈을 가져온다.
✅`input = sys.stdin.readline`: **빠른 입력을 위해** 표준 입력을 설정한다.
✅`N = int(input())` **사용자로부터 정수 N을 입력받고, 이를 정수형으로 변환**하는 초기화단계이다. 여기서 N은 1로 만들고자 하는 목표 정수이다.
✅ `D = [0] * (N + 1)`: **0으로 초기화된 DP 테이블**을 생성한다. 이 테이블은 **각 수를 1로 만드는 최소 연산 횟수**를 저장한다.
✅ `D[1] = 0`: **D\[1\]은 0**으로 설정한다. **1은 이미 1이므로 연산이 필요 없다.**
✅ `for i in range(2, N + 1):`: **2부터 N까지 반복**하며, 각 수를 1로 만들기 위한 최소 연산을 계산하는 for loop 이다.
✅ `D[i] = D[i - 1] + 1`: **1을 빼는 연산**을 수행했을 때의 연산 횟수를 저장한다.
✅`if i % 2 == 0:`: **i가 2로 나누어떨어질 경우**에만 실행된다.
✅`D[i] = min(D[i], D[i // 2] + 1)`: **현재 값 D\[i\]와 2로 나누는 연산을 비교하여 더 작은 값을 저장**한다.
✅ `if i % 3 == 0:`: **i가 3으로 나누어떨어질 경우**에만 실행된다.
✅ `D[i] = min(D[i], D[i // 3] + 1)`: **현재 값 D\[i\]와 3으로 나누는 연산을 비교하여 더 작은 값을 저장**한다.
✅ `print(D[N])`: **N을 1로 만들기 위한 최소 연산 횟수**를 출력한다.
---
## **2️⃣** 행렬 곱셈 순서 문제 (Matrix Chain Multiplication, MCM)
**💡요약:** 여러 개의 행렬을 곱할 때, 어떤 순서로 곱하느냐에 따라 곱셈 연산의 횟수가 크게 달라질 수 있다. 동적 프로그래밍을 이용해 가장 적은 곱셈 횟수를 구할 수 있다.
예를들어 행렬 **A, B, C**의 곱셈 순서가 있다고 하자. 이럴땐 **(AB)C** 또는 **A(BC)**의 곱셈이 가능하며, 이 순서에 따라 곱셈 횟수가 다르게 나오게 된다.
**A = 10x100, B = 100x5, C = 5x50**일 때:
* **(AB)C** 순서로 곱하면 **7,500번**의 곱셈이 필요하게 된다.
* **A(BC)** 순서로 곱하면 **75,000번**의 곱셈이 필요하게 된다.
**행렬의 곱셈 순서를 어떻게 설정하느냐에 따라 연산 횟수가 크게 차이**가 나기 때문에, 효율적인 계산을 위해 동적 프로그래밍을 사용하여 최소 곱셈 횟수를 구하는 방법을 찾는 것이 중요하다. 이런식의 문제를 행렬 체인 곱셈 문제(Matrix Chain Multiplication Problem)이라고한다.
---
## 행렬 곱셈 순서 문제 # 1: **재귀적 관계** (Recursive Relation in Matrix Chain Multiplication, MCM)
**💡요약:** 마지막 행렬 곱셈이 수행되는 상황에 여러가지 방법이 가능하다. 이 방법들 중 최적의 행렬 곱셈 순서를 찾기 위해서는 가능한 모든 순서를 살펴보고 가장 적은 연산 횟수로 곱셈이 이루어지도록 선택해야 한다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731943300686/1395ec05-84e1-4169-948c-1a4025e1e573.png align="center")
* **마지막 곱셈 방식**
* 행렬 A1, A2,…,An을 곱할 때 마지막에 행렬을 곱하는 방법에는 여러 가지 선택지가 있다.
* 위의 이미지에서도 볼 수 있듯이, 전체 행렬 곱셈을 A1 (A2…An) 또는 (A1A2)(A3…An)과 같이 마지막에 어느 부분을 묶어서 곱할지 여러 가지 방식으로 나눌 수 있다.
* **재귀적 관계**
* 가능한 모든 **곱셈 순서(n-1가지 경우)를 고려하여 최소의 연산 횟수를 찾는 것이 목적**이다.
* 각 경우마다 행렬의 곱셈 횟수를 계산하고, 가장 적은 곱셈 횟수를 필요로 하는 방식을 찾아야 한다.
* **최적의 순서를 찾기 위한 접근법**
* 동적 프로그래밍을 이용하면 중복된 계산을 줄이고 효율적으로 최적의 순서를 찾을 수 있게 된다.
---
## 행렬 곱셈 순서 문제 # 2: 행렬 곱을 수행하는 최소 비용 (Minimum Cost for Matrix Chain Multiplication, MCM)
**💡요약:** 여러 행렬을 곱할 때 연산 횟수를 최소화하기 위한 비용 계산 방법을 점화식으로 표현하여 보여준다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731943604025/0d3e8e5f-93b2-455b-a721-7983d95a86be.png align="center")
**✅비용 계산의 의미**
* c\_ij는 행렬 A\_i부터 A\_j 까지의 곱을 계산하는데 필요한 **최소 비용 (Minimum Cost)**을 의미한다.
* 행렬 A\_k의 **차원 (Dimension)**은 p\_k-1 \* p\_k로 표시된다. 이 정보를 통해 행렬의 곱셈 비용을 계산할 수 있게 된다.
**✅점화식 (Recurrence Relation)**
* **i = j일 때** C\_ij = 0 이다. 즉, 행렬이 하나만 있을 때는 곱셈 비용이 필요하지 않으므로 비용이 0이 된다.
* **i < j일 때**는 c\_ij = min {c\_ik + c\_k+1\_j + p\_i−1p\_kp\_j} 를 사용해 최소 비용을 계산한다.
* 이 수식에서 c\_ik 는 **앞 부분**의 최소 비용을 나타내고, c\_k + 1\_j 는 **뒷 부분**의 최소 비용을 나타낸다.
* p\_i−1p\_kp\_j 는 행렬 A\_i에서 A\_k와 A\_k+1에서 A\_j를 곱할 때 드는 비용을 의미한다.
* 이를 통해 각 구간에서 최소 비용을 찾고, 전체 곱셈의 최소 비용을 계산할 수 있다.
* **일반 형태**
* 예를 들어, 이미지에서 보이는 일반형 처럼 중간에 행렬을 나눠서 곱하면 각 부분의 최소 비용을 계산할 수 있다.
---
## 행렬 곱셈 순서 문제 # 3: 최소값을 구하는 재귀적인 방법 (Recursive Method for Minimum Cost of Matrix Chain Multiplication, MCM)
**💡요약:** 재귀적 방법 (Recursive Method)을 사용하여 행렬 곱셈의 순서를 결정할 때 최소 곱셈 비용을 계산한다. **최소 비용 (Minimum Cost)**을 찾는 것이 목적이며, 이 코드는 여러 가지 가능한 곱셈 순서 중 최적의 순서를 찾아내게 된다.
* **Top-Down(재귀)** 방식으로 구현되었다.
* 동일한 부분 문제를 중복 계산하므로, 동적 프로그래밍의 **메모이제이션(Memoization)** 기법을 추가하면 효율성이 크게 향상되게 된다.
```python
rMatrixChain(i, j) :
if (i = j) then return 0;
min ← ∞;
for k ← i to j - 1 :
q ← rMatrixChain(i, k) + rMatrixChain(k + 1, j) + p_{i-1}p_kp_j;
if (q < min) min ← q;
return min;
```
#### ✅ 입력값 `rMatrixChain(i, j)` 행렬 곱 A\_i 부터 A\_j 까지의 최소 곱셈 비용을 구하는 함수이다.
* 출력값 최소 비용: A\_i 부터 A\_j 까지 행렬 곱셈의 최소 곱셈 횟
#### ✅ `if (i = j) then return 0;` # 만약 i 와 j 가 같다면, 즉 행렬이 하나뿐이라면 곱셈이 필요 없으므로 비용은 0이다.
✅ `min ← ∞;` 최소 비용을 무한대로 설정한 뒤, 가능한 모든 곱셈 순서를 탐색하면서 최소값을 갱신한다.
✅`for k ← i to j - 1 :` 행렬 A\_i부터 A\_j 까지 곱하는 순서를 찾기 위해, k를 기준으로 문제를 두 부분으로 나눈다.
✅ `q ← rMatrixChain(i, k) + rMatrixChain(k + 1, j) + p_{i-1}p_kp_j;`
* `rMatrixChain(i, k)` A\_i부터 A\_k까지의 최소 곱셈 비용
* `rMatrixChain(k + 1, j)` A\_k+1 부터 A\_j 까지의 최소 곱셈 비용
* 두 부분 문제의 비용(왼쪽 부분과 오른쪽 부분)을 더하고, A\_i부터 A\_k와 A\_k+1 부터 A\_j를 곱하는 비용을 추가로 계산한다.
* `p_{i-1}p_kp_j;` 두 부분을 결합할 때 발생하는 비용이다. 각 행렬의 차원을 나타낸다.
✅ `if (q < min) min ← q;` 계산된 비용 q 가 현재 최소 비용보다 작다면, min을 업데이트한다.
✅ `return min;` 가능한 모든 k에 대해 최소 비용을 반환한다.
---
## 행렬 곱셈 순서 문제 # 4: 최소값을 구하는 동적 프로그래밍을 이용한 최적화 (Dynamic Programming for Minimum Cost of Matrix Chain Multiplication, MCM)
**💡요약:** 위에서 언급된 재귀적인 방법은 중복 호출 문제가 발생하여 시간 복잡도가 O(2^n)에 가깝게 된다. 동적 프로그래밍을 사용하여 DP 테이블 m을 사용해 중간 결과를 저장함으로써 계산 효율성을 높일 수 있다.
* 재귀적 풀이와 달리, **Bottom-Up 방식**으로 테이블을 채우며 최적의 해를 구한다.
* 시간 복잡도가 O(n³)로 개선된다.
```python
MatricChain(i,j):
for i ← 1 to n: #초기화
m[i, i] ← 0;
for r ← 1 to n-1 #하위 문제 크기 결정
for i ← 1 to n-r: #하위 문제의 시작점 설정
j ← i + r;
m[i, j] ← min(m[i, k] + m[k+1, j] + p[i-1]p[k]p[j]); #최소비용계산
return m[1, n]; #결과 반환
```
#### **✅입력값**
* #### n: 곱해야하는 행렬의 개수
* p\[\]: 행렬의 크기를 나타내는 배열이고 길이는 n + 1이다.
* p\[i−1\] × p\[i\] : A\_i 행렬의 크기
#### **✅ 출력값**
* m\[1\]\[n\] : A\_1 부터 A\_n 까지 모든 행렬을 곱하는 데 필요한 최소 곱셈 비용
**✅ 초기화**
* 행렬이 하나일 경우 비용은 0으로 설정한다. 예) m\[1\]\[1\]=0, m\[2\]\[2\]=0 등
**✅ 하위 문제 크기 결정**
* 하위 문제의 크기를 결정한다. r = j - i + 1 즉 곱셈에 포함된 행렬의 개수.
**✅ 하위 문제의 시작점 설정**
* i : 하위 문제의 시작 인덱스.
* j : 하위 문제의 끝 인덱스 (i + r)
**✅ 최소 비용 계산**
* m\[k+1, j\]: A\_k+1 부터 A\_j까지의 곱셈 비용
* m\[i\] m\[j\] : 가능한 모든 분할에서 최소값을 저장
* m\[i, k\]: A\_i부터 A\_k까지의 곱셈 비용
**✅결과 반환**
m\[1\]\[n\]: 전체 행렬 A\_1부터 A\_n지의 최소 곱셈 비용
---
## **3️⃣** 외판원의 순회 경로 짜기 (Travelling salesman problem, TSP)
**💡요약:** 외판원의 순회 경로 문제 (Traveling Salesman Problem)는 컴퓨터 과학 분야에서 매우 중요한 문제로, 다양한 응용 분야가 있다. 이 문제의 목적은 가장 적은 비용으로 모든 도시를 방문하고 원래 출발한 도시로 돌아오는 최적의 경로를 찾는 것이다. 비대칭적 비용 (Asymmetric Costs)을 가지므로, 한 방향의 이동 비용이 다른 방향과 같지 않을 수 있다.
#### 문제 요약
1. **여러 도시 방문**: 1번부터 N번까지의 도시가 있다.
2. **출발 및 순회**: 특정 도시에서 출발하여 모든 도시를 한 번씩 방문하고, 다시 원래의 출발 도시로 돌아와야 한다.
3. **중복 방문 불가**: 한 번 방문한 도시는 다시 방문할 수 없다.
4. **이동 비용**: 각 도시 간의 이동 비용이 주어지며, 행렬 W\[i\]\[j\]로 표현된다. 이 행렬은 대칭적이지 않을 수 있다.
5. **목표**: 이동 비용의 합이 가장 적은 경로를 찾는 것이다.
---
### **외판원의 순회 경로 문제 #1 : 입력과 출력 (Traveling Salesman Problem - Input and Output)**
**💡요약:** 아래의 **입력과 출력의 형식** 예제를 통해 도시 간 이동 비용과 최소 비용을 계산하는 방법을 알아보자. 문제의 난이도 때문에, **도시의 수 (N)**는 2 이상 16 이하로 제한되었다. 주어진 비용 행렬(Cost Matrix)를 사용해 최소 순회 비용을 찾는다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731980244950/871d3dbc-64ae-4ad7-a482-0d4df90d2898.png align="center")
#### ✅ 입력 설명 (Input)
1. **첫 번째 줄**에는 **도시의 수 (N)**가 주어집니다. (도시의 수는 2에서 16 사이)
2. 그다음 N개의 줄에는 각 도시 간의 이동 비용을 나타내는 **비용 행렬 (Cost Matrix)**이 주어진다.
* 행렬의 각 성분은 1,000,000 이하의 양의 정수이다.
* 갈 수 없는 경로는 **0**으로 표시되며, 예를 들어 W\[i\]\[j\]가 0이면 도시 i에서 도시 j로 이동할 수 없다는 의미이다.
3. 문제에서는 항상 순회가 가능하도록 입력이 주어진다.
#### ✅ 출력 설명 (Output)
* 외판원이 모든 도시를 순회하고 다시 출발지로 돌아오는 **최소 비용 (Minimum Cost)**이 출력되었다.
---
### 외판원의 순회 경로 문제 #2: 점화식 정의 (Traveling Salesman Problem - Recurrence Relation Definition)
**💡요약: ** 점화식을 통해 현재 도시와 방문한 도시 리스트를 통해 남은 도시를 경유하는 최소 비용을 구하며, 방문 리스트는 **이진수**로 표현된다.
**✅ 점화식 정의: 점화식**은 현재 도시에서 앞으로 남은 도시를 순회하는 데 필요한 최소 비용을 구하는 방법을 나타낸다.
* **D\[c\]\[v\]**: 여기서 **c**는 **현재 위치한 도시**를 의미하고, **v**는 **현재까지 방문한 도시의 리스트**를 나타낸다. 이 값은 현재 도시가 **c**일 때 앞으로 남은 모든 도시를 방문하고 원래 출발지로 돌아오는 데 필요한 최소 비용을 의미한다.
#### ✅ 이진수 표현 방식:
도시 방문 리스트 **v**는 이진수(binary)로 표현한다. 이렇게 하면 특정 도시를 방문했는지 쉽게 표현할 수 있게 되기 때문이다.
* **4번, 1번 도시를 방문한 경우**: 도시 4번에서 1번 도시만 방문했을 때는 이진수로 **1001**로 표시되고, 1001을 십진수로 변환하여 **D\[i\]\[9\]**와 같이 표현된다.
* **3번, 2번 도시를 방문한 경우**: 도시 3번에서 2번 도시를 방문하면 이진수 **0110**이 되고, 0110을 십진수로 변환하여 **D\[i\]\[6\]**와 같이 표현된다.
* **모든 도시를 방문한 경우**: 도시 4번, 3번, 2번, 1번을 모두 방문하면 이진수 **1111**이 되며, **D\[i\]\[15\]**로 표시된다.
**🤔이진수와 도시 매핑**
#### 1\. **도시와 비트의 매핑**
* 이진수의 **각 비트 위치**는 특정 도시를 나타낸다.
* **오른쪽에서 첫 번째 비트**: 도시 1번 방문 여부.
* **오른쪽에서 두 번째 비트**: 도시 2번 방문 여부.
* **오른쪽에서 세 번째 비트**: 도시 3번 방문 여부.
* **오른쪽에서 네 번째 비트**: 도시 4번 방문 여부.
#### 2\. **비트의 값**
* #### **1**: 해당 도시를 방문했다는 뜻 / **0**: 해당 도시를 방문하지 않았다는 뜻.
#### 💡예제: 도시가 4개 (1번, 2번, 3번, 4번)
* 이진수 `0001`: 첫 번째 비트만 **1**이고 나머지 비트는 **0**이다? 이는 **도시 1번만 방문했다**는 의미이다.
* 이진수 `0010`: 두 번째 비트만 **1**이고 나머지 비트는 **0**이다? 이는 **도시 2번만 방문했다**는 의미이다.
* 이진수 `1001`: 네 번째 비트와 첫 번째 비트가 **1**이고, 나머지 비트는 **0**이다? 이는 **도시 4번과 도시 1번을 방문했다**는 의미이다.
* 이진수 `1111`: 모든 비트가 **1**이다? 이는 **도시 1번, 2번, 3번, 4번을 모두 방문했다**는 의미이다.
3. **십진수 변환** 이진수는 십진수로 변환할 수도 있다
* **0001 (2진수)** → 2^0 = 1 (십진수 1).
* **0010 (2진수)** → 2^1 = 2 (십진수 2).
* **1001 (2진수)** → 2^3 + 2^0 = 8 + 1 = 9 (십진수 9).
* **1111 (2진수)** → 2^3 + 2^2 + 2^1 + 2^0 = 8 + 4 + 2 + 1 = 15 (십진수 15).
---
### 외판원의 순회 경로 문제 #3: 점화식 2 (Traveling Salesman Problem - Recurrence Relation 2)
**💡요약:** 위에서 점화식을 정의하였으니 현재 위치와 방문한 도시 리스트를 기반으로 최소 비용을 계산하고 모든 도시를 방문했는지 판단하는 방법을 더 자세히 알아보자
**✅ 용어 설명**
* `c`: **현재 위치한 도시:** 현재 외판원이 머무르고 있는 도시를 나타낸다.
* `v`: **방문한 도시 리스트 (이진수로 표현):** 외판원이 이미 방문한 도시들의 집합을 나타낸다. 이는 이진수로 표현되며, 각 비트가 특정 도시의 방문 여부를 뜻한다. 예) v = 0110 (도시 2번과 3번 방문).
* `i`: **다음 방문할 도시:** 외판원이 현재 도시 c에서 다음에 방문할 도시 i를 나타낸니다.
* `D[c][v]`: 현재 도시 c에서 방문 상태 v일 때, 나머지 도시를 모두 순회하는 데 필요한 최소 비용을 뜻한다. 이 값을 점화식을 통해 반복적으로 계산하고 저장하게 된다.
* `W[c][i]`: 현재 위치한 도시 c에서 다음 방문할 도시 i로 이동하는 비용.
* `v | (1 << i)` : **다음 도시 i를 방문한 도시 리스트인 v에 추가**
* **비트 연산**을 통해 방문한 도시 리스트인 v에 도시 i를 추가한다.
* 예) v=0010 v = 0010v=0010 (도시 2번 방문).
* i=3i = 3i=3 (도시 3번 추가).
* v∣(1<<3)=1010v | (1 << 3) = 1010v∣(1<<3)=1010 (도시 2번과 3번 방문).
**✅ 점화식 설명**
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731981660103/75b3574e-1ba7-4648-ac46-cc70eabac2f0.png align="center")
* **D\[c\]\[v\]**: **현재 도시**가 **c**일 때, **v**라는 도시 리스트를 방문하고 남은 도시를 순회하는 최소 비용을 저장한다.
* 식의 우측에서 **Math.min** 함수를 사용하여 현재 저장된 값과 새로운 경로를 비교해 더 작은 값을 유지하도록 한다.
* **v | (1 << i)** 연산을 통해 도시 리스트에 **i**번 도시를 추가하고, **W\[c\]\[i\]**로 이동 비용을 더해준다.
**✅ 모든 도시 순회 여부를 판단하는 연산식**
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1732004263736/6b9d64f2-a08f-4df3-bd20-09a98981b82d.png align="center")
* **if(v == (1 << N) - 1)**: 모든 도시를 방문했는지 확인하는 조건문이다.
* 예를 들어 **N = 4 (도시의 개수가 4)**인 경우, **(1 << 4) - 1 = 16 - 1 = 15**이므로 **v == 15**이면 모든 도시를 방문한 상태임을 의미한다.
* 15를 이진수로 변환하면 1111이 되어 **모든 도시가 방문**되었음을 나타내게 된다.
---
### 외판원의 순회 경로 문제 #4: 점화식 3 (Traveling Salesman Problem - Recurrence Relation 3)
**💡요약:** 특정 방문한 도시를 저장하고 특정 도시 방문 여부를 확인하는 연산식을 알아본다.
**✅ 방문 도시 저장 연산식**
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1732004685441/077ea6f6-03dd-4ebd-8230-fb83828cb2eb.png align="center")
* `v | (1 << i)`: 이 연산은 **특정 도시**(도시 번호 **i**)를 방문했다는 정보를 저장한다.
* 예를 들어, **i = 2**일 때, **1 << 2**는 **100** (이진수)으로 변환되며, 이는 **3번째 도시**를 의미한다.
* **v | (1 << i)**는 이 정보를 기존 **v** 값에 추가하여 **방문한 도시 리스트**에 반영하게 된다.
✅ **방문 도시 확인 연산식**:
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1732004692730/1514874c-b333-4fd5-aeee-3270e9139ea2.png align="center")
* `if ((v & (1 << i)) == 0)`: 이 조건문은 **특정 도시**(도시 번호 **i**)가 이미 방문되었는지 확인하는 용도로 사용된다.
* 예를 들어, **i = 3**일 때, **1 << 3**는 **1000** (이진수)으로 변환되어, 이는 **4번째 도시**를 의미한다.
* `(v & (1 << i)) == 0`이면 해당 도시는 **아직 방문하지 않은 상태**임을 나타낸다.
---
### 외판원의 순회 경로 문제 #5: 점화식 4 (Traveling Salesman Problem - Recurrence Relation 4)
**💡요약:** 외판원 문제에서 각 단계는 출발 도시에서 다른 도시로의 **첫 이동부터** 시작하여, 모든 도시를 **순차적으로 방문하고 마지막에 출발지로 돌아오는 경로**를 계산한다. **동적 프로그래밍**을 통해 각 단계에서 누적된 최소 비용을 유지하며, 최종적으로 최소 비용의 경로를 찾게 된다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1732004850130/10dd160d-8841-448d-b188-8d35ed101635.png align="center")
#### **✅ 1번째 방문 (First Visit)**
첫 번째 방문 단계에서는 **출발 도시**에서 다른 도시들로 이동을 시작하게 된다. 출발 도시는 임의로 고정되어 있으며, 여기에서는 도시 **0**번을 출발지로 가정한다.
* 예를 들어, `D[0][1]`은 출발지 **0번 도시**에서 **1번 도시**로 이동한 상태이다.
* 출발 도시는 모든 도시로의 이동 비용을 한 번씩 계산하여 다음 방문할 도시를 결정한다.
#### **✅ 2번째 방문 (Second Visit)**
2번째 방문 단계는 **첫 번째 방문에서 선택한 도시**에서 시작하여 **다음 도시**로 이동하는 과정이다. 이 단계에서는 **이미 방문한 도시를 제외**한 다른 도시로 이동하게 된다.
* 예를 들어, `D[1][3] + W[0][1]`은 **1번 도시**를 방문한 후 **3번 도시**로 이동하면서 추가된 이동 비용을 계산한다.
* 이때, 현재까지의 누적 비용을 저장하여 다음 단계에서도 최소 비용을 유지할 수 있게 한다.
#### **✅ 3번째 방문 (Third Visit)**
3번째 방문 단계에서는 **두 번째 방문 단계에서 이동한 도시**에서 또 다른 도시로 이동한다. 이 단계부터는 **이전 단계에서 방문한 도시를 제외한 도시들 중** 다음 방문할 도시를 선택하여 경로를 확장하게 된다.
* 예를 들어, `D[2][7] + W[1][2]`는 **2번 도시**를 방문한 후 **7번 도시**로 이동하는 상태이며, 여기서도 이동 비용을 추가하여 누적한다.
* 이 단계는 가능한 모든 경로에 대해 최소 비용을 계속 갱신한다.
#### **✅ N번째 방문 (Nth Visit)**
**N번째 방문**은 **마지막 도시를 방문하는 단계**로, 모든 도시를 한 번씩 방문하여 경로를 완성하는 단계가 된다. 이 단계에서는 **방문 가능한 모든 도시를 다 거친 후 남은 마지막 도시**로 이동한다.
* 예를 들어, `D[3][15] + W[2][3]`은 **3번 도시**까지 방문하고 남은 도시로 이동하면서 마지막 비용을 더한 상태이다.
* 이 단계가 끝나면, 모든 도시를 방문하고 다시 출발지로 돌아올 준비를 마치게 된다.
#### **✅ 시작 도시로 순회 (Return to Starting City)**
모든 도시를 한 번씩 방문한 후에는 **출발 도시로 돌아오는 경로**를 계산한다. 이는 순회 경로를 완성하는 마지막 단계로, 최종적으로 **최소 비용**으로 출발 도시로 돌아오는 방법을 구하는 것이다.
* 예를 들어, `D[3][15] + W[3][0]`은 마지막 도시 **3번**에서 **출발 도시 0번**으로 돌아오는 경로의 비용을 나타낸다.
* 이렇게 모든 경로를 거쳐 최소 비용을 유지하는 최적의 순회 경로가 결정된다.
---
### 외판원의 순회 경로 문제 #6: 의사코드 (Pseudocode - Recurrence Relation)
**💡요약:** 외판원 문제를 **Top-Down 방식**의 동적 프로그래밍으로 해결하는 방법이다. 모든 도시를 방문 후 시작 도시로 돌아가는 최소 비용을 계산하며, 이미 계산된 경로는 메모이제이션을 통해 중복 계산을 피한다. 비트 연산을 통해 방문한 도시를 관리하며, 최소 비용을 갱신하는 방식으로 효율적으로 문제를 해결하게 된다.
**코드 설명**
1. **N(도시 개수)**: 방문해야 할 도시의 총 개수를 나타낸다.
2. **W\[i\]\[j\]**: `W[i][j]`는 도시 i에서 도시 j로 이동하는 비용을 나타내는 행렬이다.
3. **D\[c\]\[v\]**: 현재 도시가 c이고, 방문한 도시 목록이 v일 때 남은 모든 도시를 경유하는 데 필요한 최소 비용을 저장하는 DP 테이블이다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1732006395790/a26d5b9b-a867-4cf8-983c-115694125969.png align="center")
✅ `for i = 0 ~ N:` W 행렬에 각 도시 간의 이동 비용을 초기화한다. 이 부분에서는 도시 간 비용을 미리 설정한다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1732006563102/a7c49137-9f18-4d5b-ba8a-82181236244e.png align="center")
✅ `tsp(c, v):` `tsp` 함수는 외판원의 순회 경로 문제를 재귀적으로 해결하기 위한 함수이다. `c`는 현재 도시, `v`는 방문한 도시 목록을 뜻한다.
✅ `if 모든 도시를 방문 했을 경우`: 모든 도시를 방문한 경우, 시작 도시로 돌아가는 비용을 반환한다. 만약 시작 도시로 돌아갈 수 없는 경우, 무한대(Inf)를 반환하여 불가능함을 표시한다.
✅ `if 이미 계산한 적이 있을 때`: 메모이제이션을 활용하여 이미 계산한 경로의 최소 비용이 존재하면 저장된 값(DP테이블)을 바로 반환한다. 이를 통해 중복 계산을 방지한다.
✅ `for i = 0 ~ N:` 방문하지 않은 도시들을 순회하며 이동 가능한 도시의 비용을 계산한다. `min_val`을 업데이트하며 최소 비용을 찾는다.
✅`D[c][v] = min_val` & `return D[c][v]`: 최소 비용을 `D[c][v]`에 저장한 후 반환한다. 이는 다음 호출에서 재사용될 수 있다.
---
### 외판원의 순회 경로 문제 #7: 파이썬 코드 (Python Pseudocode - Recurrence Relation)
**💡요약:**
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1732021315126/2f72b492-19c9-411c-b214-5183c62dfa11.png align="center")
**✅ 초기화**
* `import sys` : **시스템 라이브러리**(System Library)를 불러온다.
* `input = sys.stdin.readline` : 빠른 입력을 위해 표준 입력을 사용한다.
* `N = int(input())` : 도시의 개수를 입력받는다.
* `W = []` : **이동 비용을 저장할 리스트**(List for Storing Travel Costs)를 초기화한다.
**✅ 입력된 이동 비용 저장**
```python
for i in range(N):
W.append([])
W[i] = list(map(int, input().split()))
```
* `W.append([])`각 행마다 이동 비용을 리스트에 저장한다. **도시 간 이동 비용**(Travel Cost Between Cities)이 주어지며, `W[i][j]`는 i번 도시에서 j번 도시로 가는 비용을 나타낸다.
**✅DP 테이블 초기화**
```python
D = [[0 for j in range(1 << 16)] for i in range(16)]
```
* **DP 테이블**(DP Table)을 초기화한다. 각 상태에서의 최소 비용을 저장하기 위한 2차원 리스트이다.
![](https://cdn.hashnode.com/res/hashnode/image/upload/v1732021324101/a8aefc4c-ea78-4459-99b7-d81659b05b9f.png align="center")
**✅ tsp 함수 정의**
* **tsp 함수**는 현재 도시 `c`와 방문한 도시 상태 `v`를 매개변수로 받는다.
* 모든 도시를 방문했을 때 `v == (1 << N) - 1`이면 시작 도시로 돌아가야 하며, 돌아갈 수 없으면 무한대(`float('inf')`)를 반환한다.
* 이미 계산된 적이 있으면 저장된 값을 반환해 **중복 계산을 방지**(Avoid Redundant Calculations)한다.
* 방문하지 않은 도시가 있을 경우, 그 도시로 이동해 최소 비용을 계산한다.
**
✅ 정답출력**
* `tsp(0, 1)`을 호출하여, 0번 도시에서 출발해 모든 도시를 순회하는 최소 비용을 구하고 출력한다.