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

✅ 정수를 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로 만드는 최소 횟수를 저장하고, 이미 계산한 결과를 재사용하기 때문에 효율적으로 문제를 해결할 수 있게 된다.

사용할 수 있는 연산

3으로 나누기: x가 3으로 나누어 떨어질 때, 3으로 나눈다.
2로 나누기: x가 2로 나누어 떨어질 때, 2로 나눈다.
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)이다. 단순히 문제를 입력받고 규칙에 따라 연산을 반복적으로 수행하여 결과를 구하는 방식으로 문제를 해결한다. 단순하고 이해하기 쉽지만 숫자가 커질수록 계산량이 증가하여 비효율적이다.

입력(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로 만드는 방법을 계산해본다. 각 숫자에 대해 가능한 연산을 수행한 결과 중 최소 값을 선택하여 최적의 해를 구한다.

위에서 언급된 입출력 시뮬레이션을 점화식으로 표현하여 동적 프로그래밍의 원리를 적용할 것이다. 시뮬레이션 방식은 숫자가 커질수록 비효율적이지만, 동적 프로그래밍은 계산 결과를 저장하여 중복 계산을 방지하므로 효율적이다.

각 숫자 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가지 연산 방법 들은 연산 중 하나일 뿐, 최종 최소값이 아닐 수도 있다. 모든 연산 결과를 비교하여 가장 작은 값을 선택하는 것이 핵심이다.

숫자를 1로 만들기 위해 각 숫자마다 필요한 최소 연산 횟수를 계산하여 테이블에 저장한다. 예를 들어, 숫자 6을 1로 만들기 위한 최솟값을 계산할 때 세 가지 연산 중 가능한 최솟값을 찾게된다.

예제 1: 숫자 2를 1로 만들기 : D[2]의 경우

연산 중 1을 빼는 연산을 선택하면, D[2−1] + 1 = D[1] + 1 = 1 이 된다.
연산 중 2로 나누는 연산을 선택할 수도 있다. D[2/2] + 1 = D[1] + 1 = 1 이 된다.

따라서, D[2]의 값은 1이다. 즉, 숫자 2를 1로 만들기 위한 최소 연산 횟수는 1이 된다.

예제 2: 숫자 6을 1로 만들기 : D[6]의 경우

1을 빼는 연산을 선택하면, D[6−1] + 1 = D[5] + 1 = 4 가 된다.
2로 나누는 연산을 선택하면, D[6/2] + 1 = D[3] + 1 = 2가 된다.
3으로 나누는 연산을 선택하면, D[6/3] + 1 = D[2] + 1 = 2 가 된다.

이 세 가지 방법 중 최솟값은 2이다. 따라서, D[6]의 값은 2이며, 숫자 6을 1로 만들기 위한 최소 연산 횟수는 2가 된다.

예제 3: 숫자 10을 1로 만들기: D[10]의 경우

1을 빼는 연산을 선택하면, D[10−1] + 1 = D[9] + 1 = 3이 된다.
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 테이블에 저장하여, 반복 계산을 줄이는 방법을 설명한다.

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)로 구현한 예제이다. 동적프로그래밍 기법이 사용되었다.

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)

💡요약: 마지막 행렬 곱셈이 수행되는 상황에 여러가지 방법이 가능하다. 이 방법들 중 최적의 행렬 곱셈 순서를 찾기 위해서는 가능한 모든 순서를 살펴보고 가장 적은 연산 횟수로 곱셈이 이루어지도록 선택해야 한다.

마지막 곱셈 방식
- 행렬 A1, A2,…,An을 곱할 때 마지막에 행렬을 곱하는 방법에는 여러 가지 선택지가 있다.
- 위의 이미지에서도 볼 수 있듯이, 전체 행렬 곱셈을 A1 (A2…An) 또는 (A1A2)(A3…An)과 같이 마지막에 어느 부분을 묶어서 곱할지 여러 가지 방식으로 나눌 수 있다.
재귀적 관계
- 가능한 모든 곱셈 순서(n-1가지 경우)를 고려하여 최소의 연산 횟수를 찾는 것이 목적이다.
- 각 경우마다 행렬의 곱셈 횟수를 계산하고, 가장 적은 곱셈 횟수를 필요로 하는 방식을 찾아야 한다.
최적의 순서를 찾기 위한 접근법
- 동적 프로그래밍을 이용하면 중복된 계산을 줄이고 효율적으로 최적의 순서를 찾을 수 있게 된다.

행렬 곱셈 순서 문제 # 2: 행렬 곱을 수행하는 최소 비용 (Minimum Cost for Matrix Chain Multiplication, MCM)

💡요약: 여러 행렬을 곱할 때 연산 횟수를 최소화하기 위한 비용 계산 방법을 점화식으로 표현하여 보여준다.

✅비용 계산의 의미

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) 기법을 추가하면 효율성이 크게 향상되게 된다.

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³)로 개선된다.

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번부터 N번까지의 도시가 있다.
출발 및 순회: 특정 도시에서 출발하여 모든 도시를 한 번씩 방문하고, 다시 원래의 출발 도시로 돌아와야 한다.
중복 방문 불가: 한 번 방문한 도시는 다시 방문할 수 없다.
이동 비용: 각 도시 간의 이동 비용이 주어지며, 행렬 W[i][j]로 표현된다. 이 행렬은 대칭적이지 않을 수 있다.
목표: 이동 비용의 합이 가장 적은 경로를 찾는 것이다.

외판원의 순회 경로 문제 #1 : 입력과 출력 (Traveling Salesman Problem - Input and Output)

💡요약: 아래의 입력과 출력의 형식 예제를 통해 도시 간 이동 비용과 최소 비용을 계산하는 방법을 알아보자. 문제의 난이도 때문에, 도시의 수 (N)는 2 이상 16 이하로 제한되었다. 주어진 비용 행렬(Cost Matrix)를 사용해 최소 순회 비용을 찾는다.

✅ 입력 설명 (Input)

첫 번째 줄에는 도시의 수 (N)가 주어집니다. (도시의 수는 2에서 16 사이)
그다음 N개의 줄에는 각 도시 간의 이동 비용을 나타내는 비용 행렬 (Cost Matrix)이 주어진다.
- 행렬의 각 성분은 1,000,000 이하의 양의 정수이다.
- 갈 수 없는 경로는 0으로 표시되며, 예를 들어 W[i][j]가 0이면 도시 i에서 도시 j로 이동할 수 없다는 의미이다.
문제에서는 항상 순회가 가능하도록 입력이 주어진다.

✅ 출력 설명 (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번을 모두 방문했다는 의미이다.

십진수 변환 이진수는 십진수로 변환할 수도 있다
- 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번 방문).

✅ 점화식 설명

D[c][v]: 현재 도시가 c일 때, v라는 도시 리스트를 방문하고 남은 도시를 순회하는 최소 비용을 저장한다.

식의 우측에서 Math.min 함수를 사용하여 현재 저장된 값과 새로운 경로를 비교해 더 작은 값을 유지하도록 한다.
v | (1 << i) 연산을 통해 도시 리스트에 i번 도시를 추가하고, W[c][i]로 이동 비용을 더해준다.

✅ 모든 도시 순회 여부를 판단하는 연산식

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)

💡요약: 특정 방문한 도시를 저장하고 특정 도시 방문 여부를 확인하는 연산식을 알아본다.

✅ 방문 도시 저장 연산식

v | (1 << i): 이 연산은 특정 도시(도시 번호 i)를 방문했다는 정보를 저장한다.
예를 들어, i = 2일 때, 1 << 2는 100 (이진수)으로 변환되며, 이는 3번째 도시를 의미한다.
v | (1 << i)는 이 정보를 기존 v 값에 추가하여 방문한 도시 리스트에 반영하게 된다.

✅ 방문 도시 확인 연산식:

if ((v & (1 << i)) == 0): 이 조건문은 특정 도시(도시 번호 i)가 이미 방문되었는지 확인하는 용도로 사용된다.
예를 들어, i = 3일 때, 1 << 3는 1000 (이진수)으로 변환되어, 이는 4번째 도시를 의미한다.
(v & (1 << i)) == 0이면 해당 도시는 아직 방문하지 않은 상태임을 나타낸다.

외판원의 순회 경로 문제 #5: 점화식 4 (Traveling Salesman Problem - Recurrence Relation 4)

💡요약: 외판원 문제에서 각 단계는 출발 도시에서 다른 도시로의 첫 이동부터 시작하여, 모든 도시를 순차적으로 방문하고 마지막에 출발지로 돌아오는 경로를 계산한다. 동적 프로그래밍을 통해 각 단계에서 누적된 최소 비용을 유지하며, 최종적으로 최소 비용의 경로를 찾게 된다.

✅ 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 방식의 동적 프로그래밍으로 해결하는 방법이다. 모든 도시를 방문 후 시작 도시로 돌아가는 최소 비용을 계산하며, 이미 계산된 경로는 메모이제이션을 통해 중복 계산을 피한다. 비트 연산을 통해 방문한 도시를 관리하며, 최소 비용을 갱신하는 방식으로 효율적으로 문제를 해결하게 된다.

코드 설명

N(도시 개수): 방문해야 할 도시의 총 개수를 나타낸다.
W[i][j]: W[i][j]는 도시 i에서 도시 j로 이동하는 비용을 나타내는 행렬이다.
D[c][v]: 현재 도시가 c이고, 방문한 도시 목록이 v일 때 남은 모든 도시를 경유하는 데 필요한 최소 비용을 저장하는 DP 테이블이다.

✅ for i = 0 ~ N: W 행렬에 각 도시 간의 이동 비용을 초기화한다. 이 부분에서는 도시 간 비용을 미리 설정한다.

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

💡요약: