• Approximation algorithms for NP-hard problems
• Approximation algorithm example 1: Traveling Salesman Problem (TSP)
• Approximation algorithm example 2: Bin Packing

Handling NP-Hard Problems

NP-Hard 문제는 일반적으로 다항 시간 안에 정답을 찾는 알고리즘이 존재하지 않습니다.

따라서 완벽한 해답 대신, 현실적으로 쓸 수 있는 두 가지 전략이 자주 사용:

• Backtracking and branch-and-bound:
  - Explore all solutions, prune unpromising paths.
  - Worst-case time is exponential, but often efficient with good heuristics.

• 가능한 모든 해를 탐색하지만,
• 조건을 만족하지 않을 가능성이 높은 경우는 미리 잘라내고(prune) 더 이상 진행하지 않음

• Approximation algorithms: 
  - Do not guarantee optimal solutions.
  - Provide solutions close to optimal within a proven bound.

정답(최적해)을 보장하지 않지만, 최적해에 가까운 결과를 빠르게 구하는 알고리즘

Approximation Algorithms for NP-hard

NP-Hard 문제는 정답(최적해)을 빠르게 구하기 어렵기 때문에, 최적해에 근접한 결과를 빠르게 구할 수 있는 알고리즘을 사용.

이것이 바로 근사 알고리즘.

• An approximation algorithm finds near-optimal solutions efficiently.
• ρ-approximation algorithm:
  - If ρ > 1: opt ≤ appr ≤ ρ × opt
  - If ρ < 1: ρ × opt ≤ appr ≤ opt

Approximation Algorithm Example 1: TSP

가능한 한 비용이 적은 경로를 찾는 문제

• Traveling Salesman Problem

• known as NP-complete/NP-hard problem
• No polynomial algorithm exists

• Euclidean TSP
  • w(u,w) <= w(u,v) + w(v,w)
  • The path from u to w is shorter than the path from u to w through v.
  • For G = (V,E) and arbitrary path (v1,v2,...,vk), w(v1,vk) <= w(v1,v2,...,vk)
• Similarity in spanning tree and Hamiltonian Circuit(HC)
  • Spanning tree has no cycle 스패닝 트리는 트리이므로, 사이클이 없으면서 모든 정점이 연결
  • HC는 모든 정점을 연결하는 사이클이므로, HC에서 어느 하나의 엣지만을 제거하면 스패닝 트리가 됨.
  • MST has polynomial time algorithm such as Prim and Kruskal algorithms while TSP doesn't have it.
  • Thus, let's use MST to find the lower-bound weight sum of HC
• spanning tree 와 Hamiltonian Circuit(HC) 의 유사성

1. Spanning tree 

• 주어진 그래프의 모든 정점을 연결하되, 사이클이 없는 구조
• 간선 수 = 정점 수 - 1
• 대표 알고리즘: Prim, Kruskal
• 다항 시간 내에 최적 해(MST)를 구할 수 있음

2. HC, Hamiltonian Circuit

• 모든 정점을 정확히 한 번씩 방문하고 출발점으로 돌아오는 순환 경로
• 즉, 모든 정점을 포함하고, 간선 수 = 정점 수 (사이클을 구성)
• 이 문제는 NP-complete → 최적해를 다항 시간에 구할 수 없음.

중요한 관찰: HC와 Spanning Tree의 구조적 유사성

• 해밀토니안 사이클에서 간선 하나를 제거하면,
  → 사이클이 제거되면서 모든 정점을 연결하는 스패닝 트리가 됨.
• 반대로, MST에 적절한 간선 하나를 더하면 HC 후보가 될 수 있음.

결론: MST를 HC 또는 TSP의 하한선으로 사용 가능

• MST는 정점을 최소한으로 연결하는 구조이므로,
  → MST의 총 가중치는 TSP 또는 HC의 최소 경로 비용보다 작거나 같다.

MST weight ≤ TSP or HC weight → mst ≤ opt.

• 따라서 TSP의 최적 해를 추정할 때, MST를 하한선(lower bound) 으로 사용할 수 있다.

TSP는 모든 도시(정점)를 정확히 한 번씩 방문하고 다시 출발지로 돌아오는 경로 중에서 총 비용이 최소가 되는 경로를 찾는 문제.
이 문제는 NP-Hard로 분류되어, 최적해를 구하기 위한 계산 시간이 매우 오래 걸릴 수 있다.

Input: G
Output: Approximate solution F

[ 알고리즘 단계 ]

1. MST 구성
   주어진 그래프에서 MST를 만든다.
   Prim 또는 Kruskal 알고리즘을 사용하여 최소 비용으로 모든 정점을 연결.
2. MST를 전위 순회(DFS)
   트리 형태의 MST를 DFS(깊이 우선 탐색) 순서로 탐색한다.
   이 순서를 따라 정점을 방문하면 하나의 경로가 만들어진다.
3. 중복 정점 제거 및 순회 경로 완성
   DFS로 탐색하면서 중복 방문된 정점을 생략하고, 각 정점을 한 번씩만 포함하여 경로를 구성한다.
   마지막에 시작점으로 돌아와 순회 경로를 만든다.

MST 기반 2-approximation algorithm

TSP 문제를 완전히 해결하는 대신, 최적해에 가까운 근사해를 다항 시간 안에 구하는 방법이 사용.
이 알고리즘은 최소 신장 트리(MST)를 기반으로 구성.

• 근사 해의 총 비용은 최적해의 두 배 이내.
• 즉, 최적 TSP 경로의 비용이 opt일 때, 근사 알고리즘이 구한 경로의 비용은 최대 2 × opt를 넘지 않는다.

Approximation Algorithm Example 2: Bin Packing

• Problem: Given items with sizes 0 < si ≤ 1, pack them into minimum number of bins (capacity 1).

크기가 0 < s_i ≤ 1인 n개의 물건이 주어졌을 때, 각 상자의 용량이 1일 때,
이 물건들을 가능한 최소 개수의 상자에 나누어 담는 문제.

• NP-Hard 문제로, 최적해를 구하는 것이 어렵다.
• 그래서 근사 알고리즘을 사용하여 빠르게 "좋은 해"를 구한다.

• Next-fit Algorithm:
  - Place each item in the current bin if it fits; otherwise, start a new bin.

• 현재 사용 중인 상자에 넣을 수 있으면 그대로 넣고,
• 넣을 수 없으면 새로운 상자를 하나 꺼내서 그 안에 넣는다.

  - Worst-case: uses ≤ 2 × OPT bins.

• 최악의 경우, 사용되는 상자 수는 최적해의 2배 이내

• First-fit Algorithm:
  - Place each item in the first bin where it fits.

• 물건을 순서대로 하나씩 보면서,
• 지금까지 사용한 상자 중 가장 먼저 들어갈 수 있는 상자에 넣는다.
• 빈 상자 중에서 앞에서부터 검사하므로 "First-fit"

  - Known to use ≤ 1.7 × OPT + 0.7 bins.
  - Worst-case time complexity = O(n²)

• 최악의 경우, 사용 상자 수 (# of bins used) ≤ 1.7×OPT + 0.7
• OPT: optimal solution (min number of bins)

첫 번째 증명 아이디어
First-Fit이 m개의 상자를 사용했다면, 그 중 최소 m-1개는 절반 이상 채워져 있어야 한다.
이유: 만약 절반 이하로 채워진 상자가 2개 이상 있다면? → 두 상자의 물건을 하나로 합쳐서 쓸 수 있으므로, First-Fit 알고리즘은 그 중 하나에 담았어야 함 → 따라서 대부분의 상자들은 절반 초과로 채워져야 한다는 성질이 생김.
시각 예시: 물건 a, b가 각각 용량의 ½ 이하이면 → 같은 상자에 들어갈 수 있음 First-Fit은 이걸 활용하지 못하는 경우가 거의 없음

두 번째 수학적 증명
전제: 모든 물건의 크기 합을 ∑s_i (i=1 to n)이라 하자.
상자의 용량은 1이므로, 최적 해는 이보다 작을 수 없음 → opt ≥ ∑s_i
반면, First-Fit이 m개의 상자를 사용했는데, 그 중 m-1개는 절반 이상 채워져 있다고 가정하면, ∑s_i > (m-1) / 2
정리: m ≤ 2×opt

First-Fit 알고리즘이 어떻게 동작하든, 그가 사용하는 상자 수 m은 항상 m≤2×opt 를 만족한다는 것을 수학적으로 증명.

• First-fit Decreasing Algorithm:
  - Sort items in non-increasing order and apply first-fit.
  - Uses ≤ 11/9 × OPT + 0.7 bins.

알고리즘 개요

First-Fit Decreasing(FFD)는 Bin Packing 문제에서 널리 쓰이는 근사 알고리즘 중 하나.

*FFD는 다음과 같은 순서로 동작:

1. 정렬(Sort)
   모든 물건을 크기(무게) 기준으로 내림차순(non-increasing order) 으로 정렬.
   예: [0.5, 0.4, 0.3, 0.2, 0.2, 0.2]
2. First-Fit 적용
   정렬된 물건들을 순서대로 보면서, 가장 먼저 들어갈 수 있는 상자(bin)에 넣습니다.
   빈 상자가 없으면 새 상자를 시작.

알고리즘 특징

• 최적해를 항상 주지는 않음. → BUT. 굉장히 우수한 품질의 해를 빠르게 제공.
• 최악의 경우, Time complexity = O(n^2)
  • 왜냐하면 각 아이템에 대해 이미 존재하는 모든 상자를 확인할 수 있기 때문.

근사 품질 보장

• 이 알고리즘은 이론적으로 다음과 같은 근사 보장을 가짐:
  • 사용한 상자 수 ≤ (11/9×OPT)+0.7
  • 여기서 OPT는 최적해(즉, 가장 적은 상자 수)를 의미.

• 그림은 FFD가 어떻게 동작하는지 시각적으로 보여줌.
  • 객체 리스트: [0.5, 0.4, 0.3, 0.2, 0.2, 0.2, 0.2]
  • 먼저 0.5와 0.4는 한 상자에 들어갈 수 있으므로 첫 상자에 배치.
  • 다음 0.3은 두 번째 상자에 혼자 들어감.
  • 그다음 0.2들 네 개는 남은 공간에 채워지며, 새로운 상자는 필요한 만큼 추가.
  • 마지막 0.2 하나는 따로 남아서 새 상자를 차지.

• P vs NP
• Problem transformation
• NP-complete
• NP-complete example
• NP-hard

P, NP

• A polynomial-time non-deterministic algorithm is a non-deterministic algorithm whose verification stage is a polynomial-time algorithm.
• NP is the set of all decision problems that can be solved by polynomial-time non-deterministic algorithms.
• Every problem in P is also in NP. (P ⊆ NP)
• Most decision problems discussed (e.g., TSP, 0-1 Knapsack, Hamiltonian Cycle) are in NP.
• P는 빨리 풀 수 있는 문제이고, NP는 빨리 확인할 수 있는 문제입니다.

• 비결정적 다항 시간 알고리즘이란, 정답을 추측하고 그 정답이 맞는지 다항 시간 내에 확인할 수 있는 알고리.
• NP는 이러한 알고리즘으로 다항 시간 안에 검증 가능한 결정 문제들의 집합.
• P는 다항 시간 안에 직접 해결 가능한 문제들의 집합.
• 따라서 모든 P 문제는 NP에 속합니다. (P ⊆ NP)
• 우리가 다루는 대표적인 결정 문제들(TSP, 0-1 배낭, 해밀토니안 사이클 등)은 모두 NP에 속함.
• 요약하면, P는 문제를 빨리 ‘풀 수 있는’ 것이고, NP는 정답을 빨리 ‘확인할 수 있는’ 것.

P vs NP

• 현재까지 NP에 속하지만 P에 속하지 않는 문제가 있는지 아무도 증명하지 못함.• 핵심 질문: P = NP인가?
    - P ≠ NP를 증명하려면, NP에 속하지만 P에 속하지 않는 문제 하나를 찾아야 합니다.
    - P = NP를 증명하려면, NP에 있는 모든 문제에 대해 다항 시간 알고리즘을 제시해야 합니다.
• 이는 클레이 수학연구소의 밀레니엄 문제 중 하나입니다.

Problem Transformation

(문제 변환 또는 환원)

• 문제 A를 문제 B로 바꿔서, B에 대한 알고리즘으로 A를 해결하는 방법.
1. 문제 A의 입력을 문제 B의 입력으로 변환 (transform)
2. B 알고리즘 실행
3. B의 출력을 A의 출력으로 다시 변환

• 예시:
    A: 부분집합의 합이 K가 되는 집합을 찾는 문제
    B: 두 부분집합의 합이 같은 경우 찾기
    → 집합에 특정 값을 추가하여 변환 가능.

Polynomial Transformation (or reduction)

(다항 시간 변환)

1. 변환 함수 T가 다항 시간 내에 계산 가능하고,
2. 모든 입력 x에 대해 문제 A의 정답과 문제 B의 정답이 일치하면,

→ 문제 A는 문제 B로 다항 시간 변환 가능하다고 함: A ∝ B

NP-complete

(NP-완전 문제)

현실적인 시간엔 풀 수 없다 추정되면서 서로 강력한 논리적 연관성을 가진 특이한 문제들.

• A problem A is polynomially transformable to B if there is a polynomial transformation from A to B.
• Then, we write A ∝ B. 
• 문제 A를 문제 B로 다항 시간 문제 변환 가능

• 문제 A가 NP이고, 모든 NP 문제가 A로 다항 시간 내에 변환 가능하면, A는 NP-complete 문제.

• NP-complete 문제 중 하나라도 다항 시간 알고리즘이 존재한다면, P = NP가 됩니다.

• 대표적으로 CNF 만족 문제(CNF-SAT)가 최초의 NP-complete 문제로 Cook이 1971년에 증명함 (Cook-Levin 정리)

• To show that a problem P' is in NP-complete,
  1. P' is in NP
     • 문제 P′에 대한 해답이 주어졌을 때, 그 해답이 다항 시간 내에 검증 가능함을 보이면 됨.
  2. Choose a known NP-complete problem P and then reduce P to P'
     • 이미 NP-complete임이 알려진 문제 P를 고르고,
     • 문제 P를 문제 P′로 다항 시간 내에 환원(Reduction).
       • 문제 P의 입력을 문제 P′의 입력으로 변환하는 알고리즘이 다항 시간 내에 존재함을 보이면 됨.
       • 이 과정을 통해 "문제 P′가 적어도 문제 P만큼 어렵다"는 것을 의미.

Cook's Theorem

모든 NP 문제는 다항 시간 내에 CNF-SAT 문제로 환원 가능하다.
즉, CNF-SAT 문제는 NP-complete 문제이다.

NP-complete Example: TSP

• TSP(Traveling Salesman Problem)가 NP-complete임을 보이기 위한 절차:
    (i) TSP는 NP에 속함
    (ii) NP-complete 문제인 Hamiltonian Circuit(HC)으로부터 TSP로 다항 시간 변환 가능함을 보임. HC ∝ TSP

1. 문제 정의

해밀토니안 사이클 문제 (HC: Hamiltonian Circuit)

• 입력: 무방향 그래프 G=(V,E)
• 질문: 그래프 G에는 모든 정점을 정확히 한 번씩 방문하고 출발점으로 돌아오는 사이클이 존재하는가?

외판원 문제 (TSP: Traveling Salesman Problem)

• 입력: 가중치가 부여된 그래프 G_W=(V,E′), 정수 k
• 질문: 모든 정점을 한 번씩 방문하고 다시 시작점으로 돌아오는 총 경로 길이 ≤ k 인 투어(tour)가 존재하는가?

2. 문제 변환 (HC → TSP)

아이디어:

• HC 문제를 TSP 문제로 바꾸려면, 가중치 그래프 G_W*를 새로 만들어야 함

변환 방법:

1. 모든 정점쌍 (u, v) 에 대해 간선을 추가해 완전 그래프를 만든다.
2. 간선의 가중치를 다음과 같이 정의한다:
   • w(u,v)=1 if (u,v) ∈ E → 원래 HC 그래프에 존재했던 간선
   • w(u,v)=2 if (u,v) ∉ E → 없는 간선은 일부러 "비싸게" 만든다

→ 이렇게 하면, HC의 경로만이 총 비용이 정점 개수 n인 투어가 됨

3. 논리 관계

• 만약 G에 Hamiltonian Circuit(HCP)이 있다면,
  G_W에는 길이 n인 투어가 존재한다. (모든 간선의 가중치가 1인 경우)
• 반대로 G_W에 길이 n인 투어가 존재한다면,
  그것은 G에서 실제로 존재하는 간선만으로 이루어진 경로 → G에 해밀토니안 사이클이 있다는 뜻.

4. 시간 복잡도

• 이 변환 과정은 각 정점쌍을 한 번씩 검사하면 되므로,
  • 시간 복잡도는 O(V²) 또는 O(VE) 수준
  • 따라서 Polynomial Time 내에 변환 가능함

5. 결론

이 슬라이드는 HC 문제를 다항 시간 내에 TSP 문제로 환원할 수 있음을 보여주며,
TSP가 NP-complete임을 보이는 핵심 절차 중 하나.

Prime Number Problem

정수 n(>=2) 은, n과 서로소인 모든 정수 a에 대해 다음식이 성립할 때만 소수이며, 그렇지 않으면 합성수이다

If (a,n) = 1, then (X+a)^n = X^n+a (mod n)

if and only if n is prime.

• "n이 소수인가?" → 결정 문제, 이는 P에 속함 (AKS 소수 판별 알고리즘, 2004년)
• 하지만 소인수분해(prime factorization)는 여전히 매우 어려움 → NP에 속하지만 NP-complete인지 불분명
• 소수가 아닌지를 묻는 문제(factorization problem)는 NP에 속하고, 소수 문제는 co-NP에 속함

NP (Nondeterministic Polynomial time)
정답을 추측하면 다항 시간 내에 "검증"할 수 있는 문제들의 집합
예: "이 수는 소수가 아니다" → 어떤 인수를 제시해주면 금방 확인 가능

co-NP
NP의 반대 개념 "정답이 '아니다'일 때 쉽게 검증되는 문제"
예: "이 수는 소수이다" → 틀렸다는 걸 쉽게 증명할 수는 없음.


[소수(primality) vs 소수가 아님(factorization)]
1. 소수가 아닌지를 묻는 문제
“이 수는 소수가 아니다”라는 것을 증명하려면? → 어떤 약수(인수) 하나만 제시하면 됨 (예: 15는 3×5니까 소수 아님)
후보(인수)를 추측한 다음, 나눠보기만 하면 되므로 이 문제는 NP에 속함

2. 소수인지를 묻는 문제
“이 수는 소수이다”를 어떻게 증명할까? → 인수분해를 할 수 없다는 걸 보이는 건 어려움.
'소수가 아니다'는 쉽게 증명되지만, '소수다'는 반례가 없음을 보여줘야 해서 더 어려움.
→ 그래서 이 문제는 co-NP에 속한다고 분류함
(즉, “소수가 아니다”라는 주장이 NP에 속하면, “소수다”는 co-NP에 속하게 됨)

NP-hard

• NP-hard는 NP-complete보다 더 넓은 개념으로, NP-complete 문제만큼 또는 그보다 더 어려운 문제들을 포함합니다.
• NP-complete ∈ NP-hard
• NP-hard 문제 중 하나라도 다항 시간에 풀 수 있다면 NP = P가 성립함

If a polynomial time algorithm exists for any NP-hard problem,
you can easily solve the NP-complete problem in polynomial time.

• 최적화 문제나 계산 문제도 포함됨.

How to Handle NP-hard Problems

• backtracking algorithm or branch-and-bound algorithm 사용 → 모든 경우 탐색하되, 불필요한 경우 제거하는 방식
• approximation algorithm 사용 → 최적해는 아니지만 충분히 좋은 해를 빠르게 구함

• Realistic / Unrealistic algorithms
• Tractable / Intractable problems
• Non-deterministic algorithms
    - Polynomial-time non-deterministic algorithms
• P, NP
• NP examples

Realistic Algorithms

An algorithm is considered "realistic" if its execution cost grows polynomially with respect to the input size.

입력 크기 nnn에 대해 실행 비용(수행 시간)이 다항 시간(Polynomial Time) 내에서 증가하는 알고리즘

Examples of polynomial time complexities: O(n²), O(n³.⁵), O(n¹⁰⁰)

O(n²), O(n³.⁵), O(n¹⁰⁰) 등
→ 입력 크기가 커질수록 실행 시간이 증가하긴 하지만, 그 성장이 기하급수적으로 빠르지 않고, 점진적으로 증가.

These are manageable because computer performance improves over time (e.g., doubles every two years).

• 컴퓨터 성능은 지속적으로 발전하고 있고,
  (예: 약 2년마다 처리 속도가 2배가 됨 — 무어의 법칙)
• 다항 시간 알고리즘은 이런 성능 향상으로 충분히 해결 가능한 범위 내에 있음

The class P consists of all problems that can be solved in polynomial time, thus at a realistic cost.

• P(Class P): 입력에 대해 다항 시간 내에 해결 가능한 문제들의 집합
• 즉, 현실적으로 풀 수 있는 문제들이라고 볼 수 있습니다.

Unrealistic Algorithms

Algorithms with exponential time complexities, 

실행 시간이 지수 함수적으로 증가하는 알고리즘

such as O(2ⁿ), O(2.5ⁿ), O(100ⁿ), are considered unrealistic.

입력 크기 nnn이 조금만 커져도 실행 시간이 폭발적으로 증가.

Even small inputs lead to astronomical running times, beyond what is feasible with any computing power.

입력 값이 조금만 커져도 계산 불가능한 수준의 시간이 걸림

Efficiency vs Difficulty

Efficiency: Is the algorithm practically fast? Only low-degree polynomial algorithms are truly efficient.

• 알고리즘이 실제로 빠르게 동작하는가?
• 이 질문은 단순히 시간 복잡도가 다항식(Polynomial) 이냐가 아니라,
  그 다항식의 차수가 얼마나 낮은가에 따라 달라집니다.
• 따라서, 낮은 차수의 다항 시간 알고리즘만이 진짜 효율적

Difficulty: Are there fundamental limits preventing a problem from being solved efficiently?

• 근본적으로 이 문제는 효율적으로 풀 수 없는 구조인가?
• 다시 말해, 현재까지 어떤 알고리즘도 이 문제를 다항 시간 내에 해결하지 못하고 있다면,
  이 문제는 본질적으로 어려운 문제라고 판단.
• 이런 문제들은 보통 NP-hard 또는 NP-complete 문제로 분류됨.

Tractable / Intractable Problems

( 다룰 수 있는 문제 vs 다루기 어려운 문제 )

A problem is tractable if it can be solved in polynomial time (Θ(n^k)).

• 다항 시간 내에 해결할 수 있는 문제를 의미.
• 즉, 문제의 입력 크기를 nnn이라고 했을 때, 해결 시간 또는 계산량이 Θ(nk) 수준인 문제.

예시:

• 정렬 알고리즘: O(n log n)
• 최단 경로 문제 (Dijkstra, Floyd-Warshall 등)

→ 현실적으로 풀 수 있는 문제들입니다.
→ P 클래스에 속하는 문제들이 여기에 해당됩니다.

A problem is intractable if no known polynomial time algorithm exists (e.g., Θ(2^k), Θ(n!)).

• 현재까지 다항 시간 알고리즘이 알려지지 않은 문제.
• 즉, 알고 있는 알고리즘들이 Θ(2k), Θ(n!) 같은 지수적 또는 팩토리얼 복잡도를 가질 때.

예시:

• 0-1 Knapsack 문제 (완전 탐색 시 O(2^n))
• 외판원 문제(TSP: Travelling Salesman Problem)
• 그래프 색칠 문제(Graph Coloring)

→ 이론적으로는 계산 가능하지만, 현실에서는 너무 느려서 풀 수 없음

Deterministic vs Non-deterministic Algorithms

Deterministic algorithms always produce the same output for a given input.

• 항상 같은 입력에 대해 같은 출력을 내는 알고리즘.
• 내부 동작이 완전히 예측 가능하고 명확하게 정의되어 있음.

예시:

• 이진 탐색 알고리즘
• 선택 정렬, 합병 정렬 등

→ 매번 동일한 방식으로 계산되므로, 결과도 항상 동일.

Non-deterministic algorithms may 'guess' a solution and then verify it.

• 일종의 “추측”을 통해 해를 고르고, 그 해가 맞는지 검증하는 방식을 취하는 알고리즘.
• 마치 모든 가능성을 동시에 시도할 수 있는 초능력 머신을 상상한 것처럼 작동.

실제 의미:

• 이론적인 개념이며, 실제 컴퓨터가 구현할 수 있는 방식은 아님
• NP 문제들은 바로 이런 방식으로 “정답인지 아닌지를 빠르게 검증할 수 있는” 구조입니다.

예시:

• 그래프 색칠 문제에서:
  • “색칠을 먼저 해본다” (추측)
  • “서로 인접한 정점이 다른 색인지 확인” (검증)

Polynomial-time Non-deterministic Algorithms

(다항 시간 비결정적 알고리즘)

These algorithms guess a solution and verify it in polynomial time.

They do not necessarily find the optimal solution in polynomial time.

1. 정답이 무엇일지 "추측"한다.
2. 그 정답이 정말 맞는지 확인하는 과정은 다항 시간 내에 가능하다.

• 정답을 직접 계산해내는 게 아니라,
  마치 누군가가 "정답 후보"를 제시해주었다고 가정하고,
• 그것이 올바른 해인지 빠르게(다항 시간 내에) 검증만 하면 되는 구조입니다.

Definition of NP

NP is the set of decision problems solvable by non-deterministic algorithms in polynomial time.

비결정적 알고리즘으로 다항 시간 내에 풀 수 있는 결정 문제들의 집합
An optimization problem can often be transformed into a corresponding decision problem.

최적화 문제는 결정 문제로 바꿀 수 있음.

Optimization vs Decision Problem

Example - Graph Coloring:
• Optimization: Find the minimum number of colors to color the graph.

[최적화 문제] 그래프를 색칠할 때 필요한 최소 색 수를 구하라.
• Decision: Can the graph be colored with k or fewer colors?

[결정 문제] 주어진 그래프가 k개의 색으로 색칠 가능한가?

P vs NP

P ⊆ NP ⊆ Decision Problem. 

Every problem in P is also in NP.

Every problem that can be solved in polynomial time can also be verified in polynomial time.
It remains unknown whether P = NP. Most computer scientists believe P ≠ NP.

General Categories of Problems

(1) Problems with known polynomial-time algorithms (e.g., sorting)

• 다항 시간 알고리즘이 알려진 문제들

(2) Intractable problems (e.g., 0-1 knapsack)

• 다룰 수 없는 문제들 (비효율적 문제들)

(3) Undecidable problems (e.g., the halting problem)

• 판단 불가능한 문제들

How to Decide the given problem is in NP

Step 1: Reformulate as a decision problem.

결정 문제로 바꾸기 (Reformulate as a decision problem)

원래의 최적화 문제를 예/아니오로 답할 수 있는 결정 문제로 바꿈. NP는 결정 문제만 포함하므로, 이 과정이 필수.
[예시]
최적화 문제: 그래프를 최소한의 색으로 색칠하라.→ 결정 문제: 이 그래프를 4가지 색으로 색칠할 수 있는가? (Yes/No)

Step 2: Guess a solution.

해답을 "추측"하기 (Guess a solution)

비결정적 알고리즘이라고 생각하고, 어떤 정답 후보를 "마법처럼" 하나 고른다고 가정.
이 정답은 반드시 올바른 정답일 필요는 없지만, 검증 가능한 형태여야함.
[예시]
앞서 말한 색칠 문제라면, 각 정점에 특정 색을 할당한 배열을 ‘추측’했다고 가정.

Step 3: Check if the solution can be verified in polynomial time.

추측한 해답을 다항 시간 내에 검증할 수 있는지 확인 (Verify in polynomial time)

추측한 정답이 정말 맞는지 확인하는 데 걸리는 시간이 다항 시간 이내인지 확인.
이 검증이 빠르게 가능하다면, 그 문제는 NP에 속합니다.
[예시]
색칠 배열을 보고, 모든 인접한 정점이 다른 색인지 확인 → 간선 개수만큼 확인 → O(E) → 다항 시간 가능 → NP

Problem: For the list s = [3, 9, 12, 5, 8, 10, 7], is there an element equal to 8?
이 리스트에 숫자 8이 존재하는가?

Decision version: Is there an element in the list that equals 8?

• 예(Yes) 또는 아니오(No)로 대답할 수 있는 형태.
• 결정 문제 조건 만족 → NP 문제로 표현 가능

Guessing stage: Guess an index i = 3

i = 3 이라고 추측하면 → s[3] = 5
→ s[3] ≠ 8 이므로 이 추측은 틀린 해답

Verification stage: Check if s[3] = 8. Since s[3] = 5 ≠ 8, output is NO.

추측한 인덱스의 값이 8인지 한 번 확인

This problem is in NP because verification (checking if a guessed index gives the target) is possible in constant/polynomial time.

검증은 다항 시간 내에 가능 → NP 조건 만족

NP Example 2: Traveling Salesman Problem (TSP)

Problem: Find a tour that visits each vertex exactly once with minimal total cost.
모든 도시(정점)를 정확히 한 번씩 방문하고, 다시 출발점으로 돌아오는 가장 짧은 경로를 찾는 문제

Decision version: Is there a tour of cost ≤ k?
모든 도시를 한 번씩 방문하고 되돌아오는 경로 중, 총 비용이 k 이하인 경로가 존재하는가? 

→ 예/아니오로 대답 가능 → 결정 문제 조건 만족

Guessing stage: Propose a vertex sequence (v1, v2, ..., vn).

비결정적 알고리즘은 해답(경로)을 먼저 추측한다고 가정

Verification stage: Add up the weights of the edges in the sequence and check if the total ≤ k.

1. 경로에 포함된 모든 간선이 실제 그래프에 존재하는지 확인
2. 모든 정점을 정확히 한 번씩 방문했는지 확인
3. 경로의 총 비용을 계산하고 k 이하인지 비교

The problem is in NP because we can verify the guessed tour cost in polynomial time.
→ 각 단계는 정점 수 n에 대해 O(n²) 이내로 가능
→ 검증은 다항 시간(polynomial time) 내에 가능

NP Example 3: Graph Coloring

Problem: What is the minimum number of colors needed to color a graph G?
그래프 G에 색깔이 최소 몇 개 필요?

Decision version: Can the graph G be colored using k or fewer colors?
k개 색깔을 이용하여 그래프 G를 칠할 수 있는가?

decision version으로 바꾸기 

Guessing stage: Assign colors to all vertices.
모든 정점에 색 할당

Verification stage: Check all adjacent pairs of vertices to ensure no two share the same color.
같은 색이 겹치지 않는지 검증

This can be verified in O(VE) time, so the problem is in NP.
→ 정점 수 V, 간선 수 E일 때,
→ 최대 E개의 인접 정점 쌍을 확인하므로,
→ 총 검증 시간: O(E)

∴ 검증은 다항 시간 내 가능 → NP 조건 만족

NP Example 4: Hamiltonian Cycle

Problem: Does graph G contain a Hamiltonian cycle (visiting all nodes once and returning to start)?
주어진 그래프 G가 있을 때, 모든 정점을 정확히 한 번씩 방문하고, 시작점으로 돌아오는 닫힌 경로(cycle) 가 존재하는가?

Decision version: Does such a cycle exist?

예 / 아니오로 대답할 수 있으므로, 결정 문제 조건 만족

Guessing stage: Propose a sequence of vertices forming a cycle.
비결정적 알고리즘이라고 가정하고, 정점들의 순서를 하나의 순열로 "추측"

Verification stage:

Check that each consecutive pair (and the last to first) are connected and all nodes are visited exactly once.

1. 모든 정점을 정확히 한 번씩 포함하고 있는가?
2. 각 정점 쌍이 실제 간선으로 연결되어 있는가?
   (예: v1과 v3 사이에 간선이 있어야 함)
3. 마지막 정점이 처음 정점으로 돌아오는가?
   (즉, 사이클을 형성하는가?)

This verification is doable in polynomial time ⇒ NP.
→ 정점 수 n일 때, 확인해야 할 간선 수는 n개
→ 검증 시간은 O(n) 또는 O(n²) 로, 다항 시간 내 가능

NP Example 5: Subset Sum

Problem: Given a set of positive integers S and a target M, find if any subset sums to M.
정수 집합 S와 목표 값 M이 주어졌을 때, 어떤 부분집합을 선택해서 그 합이 정확히 M이 되는지를 찾는 문제

Decision version: Is there a subset of S whose sum is exactly M?
S의 부분집합 중 합이 정확히 M이 되는 것이 존재하는가?

→ 예/아니오로 대답 가능

Guessing stage: Pick a subset.
비결정적 알고리즘이라고 가정하고, 어떤 부분집합을 임의로 골라서 추측

Verification stage: Add elements of the subset and check if the sum equals M.

• 선택한 부분집합의 원소들을 모두 더해서, 그 합이 목표값 M과 같은지 확인.

Sum check is linear ⇒ polynomial time ⇒ in NP.

→ n개의 원소에 대해 덧셈만 수행하면 되므로 시간 복잡도는 O(n)

NP Example 6: Bin Packing

Problem: Given n objects with sizes 0 < si ≤ 1, what is the minimum number of bins (capacity 1) needed to pack them?

n개의 물건이 있고, 각 물건의 크기는 0<si≤1입니다.
용량이 1인 상자(bin) 들이 있을 때, 모든 물건을 넣기 위해 필요한 최소 상자 수는 몇 개인가?

Decision version: Can all objects be packed into k bins?

“이 물건들을 k개의 상자에 모두 넣을 수 있는가?” → 예/아니오로 대답할 수 있게 바꿈.

Guessing stage: Assign objects to bins.
각 물건이 어떤 상자에 들어가는지를 제시

Verification stage: For each bin, check if the total sum of sizes ≤ 1.
추측한 배정이 유효한지 확인하기 위해, 각 상자의 총 물건 크기를 더해서 1을 초과하지 않는지 확인.

Since this check is polynomial in n, the problem is in NP.

NP Example 7: CNF Satisfiability

Problem:

Given a CNF formula (conjunction of clauses, each a disjunction), is there a truth assignment that satisfies the formula?
어떤 참/거짓(True/False) 변수 할당이 이 논리식을 참(True)으로 만들 수 있는가?

Guessing stage: Assign True/False to each variable.
비결정적 알고리즘이라고 가정하고,
모든 변수에 대해 참(True) 또는 거짓(False) 으로 값을 할당.

Verification stage: Plug in the assignment and check if the entire formula evaluates to True.

• 각 절을 순서대로 확인
• 각 절 안의 리터럴 중 하나라도 참이면 그 절은 참
• 모든 절이 참이면 전체 CNF는 참

This checking can be done in polynomial time ⇒ problem is in NP.

변수 개수가 n, 절이 m개이면
→ 시간 복잡도는 O(n × m) 이내
→ 검증은 다항 시간 내 가능

 

Today’s Topics

1. Optimality Principle
   최적 부분 구조 (Principle of Optimality)
2. Example 7: Floyd-Warshall’s Algorithm
   모든 쌍 최단 경로 문제 (All-Pair Shortest Path Problem)
3. Example 8: 0-1 Knapsack Problem
   0-1 배낭 문제 (0-1 Knapsack)

Optimality Principle

• 어떤 문제의 최적해(optimal solution) 가 존재할 때,
  그 문제의 모든 부분 문제(subproblem) 에 대해서도 최적해가 포함되어야 한다는 성질을 의미합니다.

즉, 전체 문제의 최적 해결 방법은 각 부분 문제들의 최적 해결 방법을 포함해야 한다.

Example7: Floyd-Warshall Algorithm (모든 쌍 최단 경로)

- Find the shortest paths between all pairs of vertices in a graph using dynamic programming.
- 점화식 (Recursive formula): D(k)[i][j] = min(D(k-1)[i][j], D(k-1)[i][k] + D(k-1)[k][j])

# D[i][j] = i에서 j까지 바로 가는 기존 거리와 i → k → j로 우회하는 거리 중 더 짧은 것을 선택.

# Python Pseudo-code
def floyd_warshall(dist, length):
    for k in range(length):
        for i in range(length):
            for j in range(length):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

 

모든 정점 쌍 (i, j)에 대해 최단 경로의 거리를 구하는 알고리즘.
그래프에 음의 가중치가 있어도 사용 가능하며, 동적 계획법(DP)을 사용한 대표적인 알고리즘 중 하나.

 

언제 쓰이는가?

• 입력: 가중치가 있는 방향 그래프 (음수 가능, 음의 사이클은 없어야 함)
• 목적: 모든 쌍 정점 간의 최단 거리를 구하고 싶을 때

D[k][i][j]: 정점 i에서 j로 가는 최단 거리인데, 중간 정점으로 1~k번 정점까지만 허용할 때의 최단 거리

 

 

• 초기화
  • dist[i][j]는 i → j의 직접 경로 거리로 설정 (없으면 무한대)
  • dist[i][i] = 0 (자기 자신으로 가는 거리)
• 중간 정점 k를 하나씩 증가시키며 업데이트

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]​

 

Step 0: 초기값

• D⁽⁰⁾[2][5] = ∞
  (v₂에서 v₅로 가는 직접 경로가 없으므로 무한대)

Step 1: 중간 정점으로 v₁만 허용

• 시도: v₂ → v₁ → v₅
  • 거리 = v₂→v₁ (9) + v₁→v₅ (5) = 14

Step 2, 3: v₂, v₃ 허용

• 중간 정점이 v₂(v₂→v₂→v₅), v₃ → 의미 없음 (자기자신이거나 무효경로)
• 그대로 유지: D⁽²⁾[2][5] = D⁽¹⁾[2][5] = 14, D⁽³⁾[2][5] = 14

Step 4: v₄를 중간 정점으로 추가

• 후보 경로 3가지:
  1. D⁽³⁾[2][5] = 14 (이전 값 유지)
  2. v₂ → v₄ → v₅ → 2 + 3 = 5
  3. v₂ → v₁ → v₄ → v₅ → 9 + 1 + 3 = 13
  4. v₂ → v₃ → v₄ → v₅ → 3 + 4 + 3 = 10

Step 5: 모든 정점 허용

• 추가 정보 없음 → 최단 거리 그대로 유지

- Time complexity: O(n^3)

- Space complexity: O(n^2) #가능한 모든 정점 쌍은 n × n = n²개, 즉 2차원 행렬이 필요.

---

Example 8. 0-1 Knapsack Problem (배낭 문제)

- Given weights and profits of items, find the maximum profit we can carry without exceeding the weight limit.

- 무게 제한이 있는 배낭에, 가치(value) 와 무게(weight) 가 정해진 물건들을 최대한 가치 있게 넣는 방법을 찾는 문제.

( 단, 각 물건은 한 번만 넣을 수 있고(0 또는 1), 반쯤 자르거나 나눠서 넣을 수는 없습니다. )

1. DP 테이블 만들기

• 행: 물건 개수 + 1
• 열: 가능한 배낭 무게 0부터 W까지

K[i][w] = 앞에서 i번째 물건까지 고려했을 때,
          무게가 w일 때 만들 수 있는 최대 가치

2. 점화식 (Recurrence Relation)

if wt[i-1] <= w:
    K[i][w] = max(
        K[i-1][w],                    # 현재 물건을 안 넣음
        K[i-1][w - wt[i-1]] + val[i-1]  # 현재 물건을 넣음
    )
else:
    K[i][w] = K[i-1][w]  # 무게 초과라서 못 넣음

3. pack 과정: 실제 물건 넣는 순서 구하기

DP 테이블이 다 채워졌다면, 역추적을 통해 무엇을 넣었는지 확인:

1. i = n, w = W부터 시작
2. 아래 조건을 만족하면, i번째 물건을 넣었다고 판단
3. 물건을 넣었다면:
   • w = w - wt[i-1] 로 줄여줌 (남은 공간 계산)
   • i = i - 1
4. 반복

K[i][w] ≠ K[i-1][w]  
→ 무언가 바뀐 경우 = 물건 i가 포함됨

• 행(i): 물건 번호 (0부터 시작)
  • i = 0: 아직 아무 물건도 고려하지 않은 상태 → 모든 값은 0
  • i = 1: 1번 물건(5kg, 10만원)을 고려
  • i = 2: 1번, 2번 물건까지 고려 (4kg, 40만원 포함)
  • i = 3: 1~3번 물건까지 고려 (6kg, 30만원 포함)
  • i = 4: 모든 물건 고려 완료 (4번: 3kg, 50만원)
• 열(w): 배낭의 현재 무게 한도 (0kg부터 10kg까지)
  • w = 0: 배낭이 아무것도 담을 수 없음 → 항상 0
  • w = 5: 최대 5kg까지 물건을 담을 수 있음
  • w = 10: 배낭 최대 용량 → 우리가 구하고자 하는 해답

각 칸 K[i][w]의 의미
i번째 물건까지 고려했을 때, 배낭 무게가 w일 경우 가능한 최대 총 가치

i = 1 (1번 물건만 고려) 의 경우
물건 1: 무게 5kg, 가치 10
- w < 5 담을 수 없음
- w ≥ 5 담을 수 있으므로 가치 10

i = 2 (물건 1, 2 고려) 의 경우
물건 2: 무게 4kg, 가치 40 예: K[2][9] = max(K[1][9], K[1][5] + 40) = max(10, 10 + 40) = 50
→ 이 칸은 물건 1(5kg, 10)과 물건 2(4kg, 40)를 둘 다 넣을 수 있는 조합임

i = 3 (물건 1~3 고려) 의 경우
물건 3: 무게 6kg, 가치 30 예: K[3][10] = max(K[2][10], K[2][4] + 30) = max(50, 40 + 30) = 70
→ 무게 10kg에 2번(4kg, 40) + 3번(6kg, 30) 넣은 조합이 최적

i = 4 (모든 물건 고려) 의 경우
물건 4: 무게 3kg, 가치 50 예: K[4][10] = max(K[3][10], K[3][7] + 50) = max(70, 40 + 50) = 90
→ 최종 해답: 배낭에 무게 10kg 채우면 최대 가치 90

K[4][7]: 4번 물건(3kg, 50)을 넣고, 남은 공간 4kg에 2번 물건(4kg, 40) 을 함께 넣음.

#Pseudo-code

def knapSack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i - 1] <= w:
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]
    return K[n][W]

- Time complexity: O(nW)

- Space complexity: O(nW)

• n: 물건의 개수
• W: 배낭이 수용할 수 있는 최대 무게 (정수값)

Today's Topics

Example 5. Revisit Chained Matrix Multiplication

Example 6. Edit distance

Example 5. Revisit Chained Matrix Multiplication

- 목표: 행렬 곱셈의 순서를 바꿔 곱셈 연산 수를 최소화

- How many distinct arrangements of n pairs of left-right parentheses are there all of which does?

- The n-th Catalan number, C(n)

• C(1) = 1, ()
• C(2) = 2 ()() and (())
• C(3) = 5 ()()(), ()(()),(())(),((()))

At very last step, we compute (Ai × Ai+1 × ... × Ak) × (Ak+1 × ... × Aj) at some point k, i ≤ k < j
So, the chain is split into these two subchains,
that is, find the minimum number of multiplications for (Ai × Ai+1 × ... × Ak) and the one for (Ak+1 × ... × Aj). 
Thus, Cost(Ai...j) = min_k ( Cost(Ai...k) + Cost(Ak+1...j) + pi-1 * pk * pj )

Establish recursive property:

If i=j, then 0
If i<j, m[i][j] = min(m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]) 

[예시] A_1: 30x1, A_2: 1x40, A_3: 40x10, A_4: 10x25 

(A₂×A₃) × (A₄): 400 + 0 + 1×10×25 = 400 + 250 = 650
(A₁) × (A₂×A₃×A₄): 0 + 650 + 30×1×25 = 650 + 750 = 1400
→ 최소 곱셈 수: 1400

• m[1][3] = min( (A₁)×(A₂×A₃), (A₁×A₂)×(A₃) ) = min(0 + 400 + 30×1×10, 1200 + 0 + 30×40×10)
• m[2][4] = min( (A₂)×(A₃×A₄), (A₂×A₃)×(A₄) ) = min(0 + 10,000 + 1×40×25, 400 + 0 + 1×10×25)
• m[1][4] = (A₁) × (A₂×A₃×A₄) = m[1][1] + m[2][4] + p₀×p₁×p₄ = 0 + 650 + 30×1×25 = 1400

- 시간 복잡도: O(n^3), 공간 복잡도: O(n^2)

Example 6: Edit distance

- 정의: 문자열 S를 T로 바꾸기 위해 필요한 최소 편집 연산 수 (삽입, 삭제, 치환)

- Example (S='agaatgca', T='acaagrga')

Compute the edit distance between cat and cake.

[step1] Create the table with rows(' ','c','a','t') and columns(' ','c','a','k','e') and compute edit distance when one side is  null.

[step2] If the characters are same, take the value on left above

[step3] For other cases, take the minimum on values on left-above, left, and above and then increment by 1.

두 문자의 비교 결과가 서로 다를 때 (si ≠ tj) 이 경우에는 3가지 연산 중 하나를 선택:
1) 삽입 (Insert): 왼쪽 값 → d[i][j-1]
2) 삭제 (Delete): 위쪽 값 → d[i-1][j]
3) 교체 (Replace): 대각선 왼쪽 위 값 → d[i-1][j-1]
이 셋 중 가장 작은 값을 선택하고 +1을 더함 → 편집 연산 1회를 추가 의미.

- 점화식:
    d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + t[i][j])
    where t[i][j] = 0 if s[i] == t[j], else 1

- 초기값: d[i][0] = i, d[0][j] = j

- Time complexity and Space complexity: O(mn), m은 S의 길이, n은 T의 길이

Dynamic Programming (Part 2) - Summary

1. What is Dynamic Programming?

Dynamic Programming (DP) is an algorithmic technique for solving optimization problems by breaking them down into simpler subproblems and solving each subproblem only once, storing the results for future reuse.

동적 계획법(DP)은 최적화 문제를 더 단순한 부분 문제들로 분할하여, 각 부분 문제를 한 번만 해결하고 그 결과를 저장함으로써 중복 계산을 방지하고 전체 문제를 효율적으로 해결하는 알고리즘 기법이다.

*Key characteristics:
- Recursive relation

문제의 해를 더 작은 부분 문제의 해로 표현하는 재귀적 관계를 설정한다.
- Bottom-up computation

가장 작은 부분 문제부터 차례대로 해결하면서 큰 문제의 해를 점진적으로 완성해 나간다.
- Table (memoization) to store subproblem solutions

각 부분 문제의 결과를 배열(또는 테이블)에 저장하여 같은 계산을 반복하지 않도록 한다.

2. Example 1: Binomial Coefficients

- The recursive formula for binomial coefficients is:
B(i, j) = 1 if j == 0 or j == i
B(i, j) = B(i-1, j-1) + B(i-1, j) if 0 < j < i

- This can be represented using Pascal’s Triangle.

P[i][j]=P[i][j-1]*(i-(j-1))//(j-1)

- A dynamic programming approach avoids redundant computation by filling values bottom-up.

동적 계획법 접근 방식은 값을 아래에서부터 채워 나가는 방식으로 중복 계산을 피한다

3. Example 2: Longest Increasing Subsequence (LIS)

- Given a sequence, find the length of the longest increasing subsequence.

- For example, S=(9,5,2,8,7,3,1,6,4): the longest increasing subsequence has length 3 and is either (2,3,4) or (2,3,6).

: predecessor 배열은 LIS (Longest Increasing Subsequence) 를 추적할 때, 각 위치에서 현재 수열에 붙는 직전 원소의 인덱스를 기록해두는 중요한 구조.

* predecessor[6]=3

• a_3 = 2에서 끝나는 LIS: [2] → 길이 = 1
• 거기에 a_6 = 3을 붙이면 → [2, 3] → 길이 = 2
• 따라서 h[6] = h[3] + 1 = 2
  그리고 그 직전 원소의 인덱스는 3 → predecessor[6] = 3

- How many searches we can expect?

2^n searches (or subsets)

- Recursive relation:
h[i] = max(h[j] + 1) for all j < i where a[j] < a[i]
LIS length = max(h[i])

- Implementation uses a nested loop to compute LIS in O(n^2) time.

[1단계]

먼저, 수열의 각 원소에서 끝나는 LIS의 길이를 저장할 배열 h를 초기화합니다.

모든 위치는 최소 자기 자신 하나만으로 LIS를 구성할 수 있으므로, h의 모든 값을 1로 초기화합니다.

[2단계]

그 다음, 바깥쪽 루프는 두 번째 원소부터 순차적으로 i = 1부터 n-1까지 진행되며,

현재 인덱스 i에서 끝나는 LIS의 길이를 업데이트합니다.

내부 루프에서는 j = 0부터 i-1까지의 모든 인덱스를 검사합니다.

- 이때 arr[j] < arr[i] 조건을 만족하는 경우, arr[i]는 arr[j]를 이어 증가 수열을 만들 수 있습니다.

그 경우에 h[i] < h[j] + 1이라는 조건도 확인합니다. 조건이 참이면 h[i]를 h[j] + 1로 갱신합니다.

[3단계]

이 과정을 반복하면, 각 i에 대해 그 지점에서 끝나는 가장 긴 증가 부분 수열의 길이가 h[i]에 저장됩니다. 반복문이 모두 끝난 후에는 h 배열에서 가장 큰 값을 찾아 반환합니다. 그 값이 전체 수열에서의 최장 증가 부분 수열의 길이가 됩니다.

예를 들어 수열 [10, 22, 9, 33, 21, 50, 41, 60]의 경우, h_i 배열은 [1, 2, 1, 3, 2, 4, 4, 5].

따라서 이 수열에서 LIS의 길이는 5이며, 가능한 수열 중 하나는 [10, 22, 33, 50, 60]입니다.

Today's Topic

Exampe 3: Number Triangles

Example 4: Revisit minimum coin change

4. Example 3: Number Triangles

- Goal: Maximize the sum from top to base in a number triangle.

숫자 삼각형의 꼭대기에서 바닥까지 내려가는 경로 중, 지나간 숫자의 합이 최대가 되도록 하는 경로를 찾는 것.

- Recursive relation: best(r, c) = a[r][c] + max(best(r-1, c-1), best(r-1, c))
이는 (r, c) 위치에 도달하기 위한 경로가 윗줄에서 왼쪽 대각선 (r-1, c-1) 또는 바로 위 (r-1, c) 중 하나에서 올 수 있으므로, 이 둘 중 더 큰 경로 합을 선택하여 현재 위치의 값을 더해주는 방식.

- This DP approach reduces the exponential time of exhaustive search to O(n^2).

Dynamic Programming - Number Triangle Summary

1. 문제 설명

숫자가 삼각형 형태로 배치된 구조에서, 꼭대기에서 바닥까지 내려가는 경로 중 지나가는 숫자의 합이 최대가 되는 경로를 찾는 문제이다. 한 번에 아래로 이동할 때는 왼쪽 아래 대각선 또는 오른쪽 아래 대각선으로만 이동할 수 있다.

2. 완전 탐색의 한계

삼각형의 레벨이 k일 경우, 가능한 경로의 수는 2^(k-1)개가 되며, 시간 복잡도는 Θ(2^n)으로 매우 비효율적.

3. 동적 계획법 접근

- 동적 계획법을 적용하기 위해 다음과 같은 재귀 관계를 정의:

best(r, c) = a[r][c] + max(best(r-1, c-1), best(r-1, c))

→ 여기서 a[r][c]는 r번째 행 c번째 열의 값이며, best(r-1, c-1)과 best(r-1, c)는 그 위쪽에서 내려올 수 있는 두 경로의 누적 합을 의미. 이 중 더 큰 값에 현재 값을 더해 최적 합을 계산.

4. 구현 방식

1) 첫 번째 행(꼭대기)은 그대로 사용.
2) 이후 각 행에 대해 다음과 같이 값을 갱신:
- 왼쪽 끝 열(c = 0): 바로 위에서만 올 수 있음 → dp[r][0] = dp[r-1][0] + a[r][0]
- 오른쪽 끝 열(c = r): 왼쪽 위에서만 올 수 있음 → dp[r][r] = dp[r-1][r-1] + a[r][r]
- 나머지: 두 경로 중 큰 누적 값을 선택 → dp[r][c] = a[r][c] + max(dp[r-1][c-1], dp[r-1][c])

5. 시간 복잡도

삼각형의 각 칸을 한 번씩만 계산하므로 총 연산 수는 1 + 2 + ... + n = n(n+1)/2.

따라서 전체 알고리즘의 시간 복잡도는 O(n²). 이는 완전 탐색의 지수 시간 복잡도에 비해 매우 효율적.

5. Example 4: Revisit Minimum Coin Change

- Given coins of different denominations, find the minimum number of coins to make a certain value y.

- Recursive relation:
minCoins[y] = min(minCoins[y - coin] + 1 for coin in coins if coin <= y)

- Greedy algorithms may fail; DP provides an optimal solution using a table of size y+1.

- Time complexity: O(m*y) where m is the number of coin types.

1. 문제 설명

동전의 종류가 여러 개 주어졌을 때, 특정 금액 y를 만들기 위한 최소 동전 개수를 구하는 문제.

예를 들어, 동전이 [1원, 5원, 10원]이고 목표 금액이 11원이라면, 최소 동전 개수는 2개(10원 + 1원)이다.

2. 재귀 관계

이 문제는 다음과 같은 재귀 관계를 기반으로 해결할 수 있다:

minCoins[y] = min(minCoins[y - coin] + 1 for coin in coins if coin <= y)

즉, 금액 y를 만들기 위해 모든 가능한 동전 coin에 대해 y - coin 값을 만들 수 있는 최소 동전 수를 확인하고, 그 값에 현재 coin 하나를 더한 것 중 최소값을 선택하는 방식.

이 문제를 해결하기 위한 핵심 아이디어는 '큰 문제를 더 작은 문제로 나누는 재귀 관계'를 세우는 것.

예를 들어, 어떤 동전 c₁을 먼저 선택했다고 하면, 그 이후에는 남은 금액 y - c₁에 대해 동일한 문제를 다시 푸는 방식으로 진행된다.

이 아이디어를 기반으로 한 재귀 관계는 다음과 같다:
minCoins(y) = min { minCoins(y - c_i) + 1 | 모든 c_i ≤ y }

- minCoins(y): 금액 y를 만들기 위한 최소 동전 수
- c_i: 사용 가능한 동전 중 하나
- y - c_i: 현재 동전 하나를 사용하고 남은 금액
- +1: 현재 사용한 동전 1개를 의미

#Pseudo-code (recursive version)

if y == 0:
    return 0
if y > 0:
    return min(1 + minCoins(y - coin[i])) for all coin[i] ≤ y

3. DP 방식의 장점

탐욕적(greedy) 알고리즘은 항상 최적 해를 보장하지 않는다.

: 예를 들어, 동전이 [25원, 20원, 10원, 5원, 1원]이고 목표 금액이 65원일 때,

가장 큰 동전부터 선택하는 탐욕 방식은 4개(25+25+10+5)를 사용하지만,

최적 해는 3개(20+20+25)이므로, 이 문제는 동적 계획법(DP)을 사용하는 것이 더 안정적이고 정확.

4. 구현 방식 [Explore with dynamic programming]

1) DP를 활용하기 위해 길이가 y+1인 테이블을 생성한다.

2) 테이블의 각 인덱스 i는 금액 i를 만들기 위한 최소 동전 수를 저장.

3) 테이블의 초기값은 모두 무한대로 설정하고, 0원을 만들기 위한 최소 동전 수는 0으로 초기화.

4) 그 후 각 금액 i에 대해 가능한 모든 동전 coin을 확인하면서, i - coin 위치에 저장된 값에 1을 더한 값과 현재 값을 비교하여 최소값으로 갱신.

min { 1+minCoins(y-Coin{i]) }

5. 시간 복잡도

이중 반복문을 사용하므로 시간 복잡도는 O(m*y)이다. 여기서 m은 동전 종류의 개수, y는 목표 금액이다.

각 금액에 대해 모든 동전을 시도하기 때문에 m번의 반복이 필요하고, y까지 계산하므로 전체 시간은 O(m*y)이다.

- Time Complexity: O(my)

- Space Complexity: O(y)