[컴퓨터알고리즘] 기말고사정리 바탕 암기사항

정렬파트

버블정렬  선택정렬  삽입정렬  쉘 정렬  힙 정렬  정렬문제의하한  기수정렬  외부정렬

• 과정보이거나 stepbystep 안 들어감
• 나름의 정리하는 문제 정도로 각각의 방법들, 비교설명한다 보면 됨
• 방법 복잡도 어떤상황에서 어떤 알고리즘이 더 좋나(퀵소트도 어떤상황에서는 최악)
• 각 알고리즘 특징 갖고 비교서술 할 정도로 익히기
• (1~2문제)
• 비교설명하시오- 항상 2~3가지 비교설명해야 함

*비교정렬문제의 하한은 O(nlogn) 이므로 이것보다 낮은 시간복잡도 존재 불가

📌 1. 정렬 알고리즘의 분류

• 내부 정렬: 메모리에 전부 올릴 수 있을 때 → 대부분 알고리즘 여기 포함
• 외부 정렬: 데이터가 너무 클 때, 디스크에 있는 데이터를 읽어가며 정렬

→ 분류명 & 개념 구분 확실히!!

---

📌 2. 알고리즘별 핵심 특징 + 복잡도 (표처럼 암기)

 

    알고리즘            최선               평균               최악              공간      안정성                    특징

버블 정렬	O(n)	O(n²)	O(n²)	O(1)	✅	인접한 것 비교. 거의 정렬 시 빠름
선택 정렬	O(n²)	O(n²)	O(n²)	O(1)	❌	항상 일정한 비교횟수, 교환 최소
삽입 정렬	O(n)	O(n²)	O(n²)	O(1)	✅	거의 정렬된 경우 최적
쉘 정렬	O(nlogn)	?	O(n^1.5)	O(1)	❌	gap 이용 삽입정렬 확장. 빠름
힙 정렬	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	❌	항상 일정. 캐시 미스 가능성
퀵 정렬	O(nlogn)	O(nlogn)	O(n²)	O(logn)	❌	가장 빠름. pivot 잘못 잡으면 망함
합병 정렬	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	✅	항상 안정적. 공간 더 씀
기수 정렬	O(kn)	O(kn)	O(kn)	O(n+r)	✅	비교X. 자리수 단위, 숫자/문자 특화

 

 

→ 이 표 구조로 외워두면 거의 모든 비교 문제 대응 가능

✅ External Sort – 합병 방식 핵심 요약표

방식핵심 개념장점단점

2-way 합병	블록 2개씩 합병	구조 단순, 구현 쉬움	합병 단계 많아 느림
Multi-way 합병 (p-way Merge)	블록 p개씩 한 번에 합병	합병 횟수 줄어듦 → 빠름	p개의 저장장치 필요
Polyphase 합병	(p+1)개 저장장치로 p-way 수행	저장장치 개수 최소화	초기 블록 조정 필요 (피보나치 수 활용)

 

 

✅ 공통 시간 복잡도: O(log(N/M))
📌 N = 전체 데이터 크기, M = 메모리 크기

 

🔹 요약

• 정렬 알고리즘은 내부 정렬(Internal sort) 과 외부 정렬(External sort) 로 분류됨

✅ 내부 정렬

• 입력의 크기가 주기억 장치 공간보다 크지 않은 경우 수행됨

✅ 외부 정렬

• 입력의 크기가 주기억 장치 공간보다 큰 경우,
  → 보조 기억 장치에 있는 입력을 여러 번 나누어 주기억 장치에 읽어 들인 후,
  → 정렬하여 다시 보조 기억 장치에 저장하는 과정을 반복함

---

🔹 정렬 알고리즘별 핵심 요약

🟡 버블 정렬 (Bubble Sort)

• 이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복
• 시간 복잡도: O(n²)

🟡 선택 정렬 (Selection Sort)

• 매번 최소값을 선택하여 정렬
• 시간 복잡도: O(n²)

🟡 삽입 정렬 (Insertion Sort)

• 정렬 안 된 부분의 원소를 정렬된 부분에 적절한 위치에 삽입
• 시간 복잡도: O(n²)
  → 최선: O(n), 평균: O(n²)

🟡 쉘 정렬 (Shell Sort)

• 삽입 정렬을 확장하여
  → 배열 뒷부분의 작은 숫자를 앞부분으로 ‘빠르게’ 이동시키고
  → 앞부분의 큰 숫자는 뒷부분으로 보내는 방식
• 시간 복잡도: O(n²)

🟡 힙 정렬 (Heap Sort)

• 힙 자료 구조를 이용하는 정렬 알고리즘
• 시간 복잡도: O(nlogn)

---

🔹 정렬 문제의 하한 (Lower Bound)

• 비교 기반 정렬의 시간 복잡도 하한은 Ω(nlogn)

---

🔹 기수 정렬 (Radix Sort)

• 숫자를 부분적으로 비교하는 정렬 방법
• 시간 복잡도: O(k(n + r))
  → k: 자릿수, r: radix(진수)

---

🔹 외부 정렬 (External Sort)

• 내부 정렬을 활용하여, 데이터를 부분적으로 읽어 정렬하고,
  다시 합병하는 과정을 반복하는 방식
• 주요 방식:
  • 다방향 (p-way Merge)
  • 다단계 (Polyphase Merge)

---

📌 3. 비교 설명 대비: 자주 묻는 비교 대상 세트

 

✅ 삽입 정렬 vs 선택 정렬을 방법, 시간복잡도, 적합한 상황 측면에서 비교하시오.

• 삽입 정렬은 정렬된 부분에 하나씩 끼워 넣는 방식으로 정렬을 확장한다.
• 선택 정렬은 전체에서 최솟값을 선택해 교환하는 방식이다.

② 복잡도

• 둘 다 평균/최악 O(n²)
• 삽입 정렬은 최선 O(n) (거의 정렬된 경우), 선택 정렬은 항상 일정

③ 적합한 상황

• 삽입 정렬: 거의 정렬된 데이터 / 소규모 데이터
• 선택 정렬: 입력 상태 상관없이 항상 일정한 성능 원할 때

 

✅ 버블 정렬과 삽입 정렬을 정렬 방식, 시간 복잡도, 적합한 입력의 특성 측면에서 비교하시오.

답안:
① 정렬 방식

• 버블 정렬: 인접한 두 원소를 반복 비교하여 큰 값을 뒤로 보내는 방식
• 삽입 정렬: 현재 값을 정렬된 부분에 끼워 넣는 방식

② 시간 복잡도

• 둘 다 평균/최악은 O(n²)
• 삽입 정렬은 최선의 경우 O(n)

③ 적합한 입력

• 버블 정렬: 거의 정렬된 데이터 (하지만 실효성은 낮음)
• 삽입 정렬: 거의 정렬된 입력에 매우 효율적

 

✅ 선택 정렬과 삽입 정렬을 정렬 방식, 입력 민감도, 교환 횟수 측면에서 비교하시오.

답안:
① 정렬 방식

• 선택 정렬: 전체에서 최솟값을 골라 앞쪽 원소와 교환
• 삽입 정렬: 앞쪽에 정렬된 부분을 유지하며 현재 원소 삽입

② 입력 민감도

• 선택 정렬: 입력 상태와 무관 (언제나 같은 횟수의 비교)
• 삽입 정렬: 입력이 정렬돼 있을수록 빠름

③ 교환 횟수

• 선택 정렬: 교환 최소 (n번 정도)
• 삽입 정렬: 이동이 많아 교환 횟수가 더 큼

---

✅ 5. 내부 정렬 vs 외부 정렬을 방법, 시간복잡도, 적합한 상황 측면에서 비교하시오.

• 내부 정렬은 데이터가 주기억장치에 모두 올라와 있는 상태에서 수행
• 외부 정렬은 일부만 메모리에 올려 내부 정렬 후 합병 반복

② 복잡도

• 내부 정렬: 알고리즘에 따라 다름 (보통 O(nlogn))
• 외부 정렬: O(log(N/M)), N=전체 크기, M=메모리 크기

③ 적합한 상황

• 내부 정렬: 입력이 메모리에 수용 가능한 일반 상황
• 외부 정렬: 대용량 입력 (수십~수백 GB 이상)

•  

---

📌 4. 기타 꼭 외워야 하는 개념

🔸 정렬 문제의 하한

• 비교 기반 정렬의 하한 = Ω(nlogn)
  → 어떤 알고리즘도 이보다 빨라질 수 없음
• 결정 트리로 증명
  → n!개의 정렬 경우의 수 → log(n!) = O(nlogn)

🔸 기수 정렬(Radix Sort)

• 자리수 기반 정렬, 비교X
• LSD (오른쪽부터) / MSD (왼쪽부터) 구분
• 시간복잡도 = O(k(n+r))
  → k = 자리수, r = 진수 (radix)

🔸 외부 정렬

• 주기억장치보다 데이터가 클 때
• 읽기-쓰기 최소화가 목표
• 합병 방식 2가지 기억!
  • p-way Merge: 여러 블록을 병합 (장치 여러 개 필요)
  • Polyphase Merge: 피보나치 블록, 저장장치 적게 씀
• 시간복잡도 = O(log(N/M))

---

🧠 외울 때 팁 정리

• 복잡도는 세 가지(최선/평균/최악)를 나눠서 기억
• **삽입 정렬: 거의 정렬된 입력에 O(n)**이라는 점 암기
• 선택 정렬: 항상 일정이라 입력에 민감하지 않음
• 힙 정렬: 항상 nlogn이지만 캐시 미스 가능성 있음
• 기수 정렬은 비교 기반 X → 하한 Ω(nlogn) 적용 안 됨

 

np완전문제 파트

 

4가지 구분하여 설명할 수 있어야 함

그 안에 reduction부분 정리

나머지부분은 다 npc문제들이 어떤 게 있는지 ~ 각각의 문제를 푸는 알고리즘 다 파악하지 x

 

✅ [1] 반드시 외워야 할 4가지 문제 구분

       구분                                         정의포함                                            관계                                  핵심 키워드

  

P	다항시간 안에 해를 구할 수 있는 문제	P ⊆ NP	O(n), O(n²), O(n³) 등
NP	다항시간 안에 해를 검증할 수 있는 문제	P ⊆ NP, NPC ⊆ NP	정답만 주면 빠르게 확인 가능
NP-Complete (NPC)	NP 안에서 가장 어려운 문제 집합 NP ∩ NP-Hard - 가장중요	NPC ⊆ NP, NPC ⊆ NP-Hard	서로 다항시간 변환(reduction) 가능. 서로 변환되는 특성 -> 하나를 다항시간 내에 풀 수 있으면 나머지도 가능! NP에서 P가 될 수 있다. 검증+변환
NP-Hard	모든 NP문제로부터 다항시간에 변환 가능한 문제	NPC ⊆ NP-Hard, NP-Hard ⊈ NP	검증조차 다항시간 안에 안 될 수 있음(변환만 가능) A로 다 풀 수 있다? -> 문제 A는 얘네를 다 커버할 수 있을 정도로 어려운 문제

🔸 기억할 문장

NP-완전 문제는 “NP 문제”이면서 동시에 “NP-Hard”한 문제이다.
P ⊆ NP ⊆ NP-Hard, 그러나 P = NP 인지는 아직 모름! (시험 출제포인트)
Nondeterministic Polynomial time 스펠링 암기

---

✅ [2] 반드시 이해하고 설명할 수 있어야 할 Reduction 개념

🔹 개념 정리

• 다항시간 변환(Polynomial-Time Reduction)
  → 문제 A를 B로 변환해서 B로 해결하면 A도 해결 가능 (A ≤p B)
  • 추이 (transitive) 관계

🔹 3단계 구조

1. 문제 A의 입력을 문제 B의 입력 형식으로 변환
2. 문제 B의 알고리즘을 다항시간 안에 수행
3. 결과를 문제 A의 해로 해석하여 반환

🔸 핵심 문장

하나의 NPC 문제만 다항시간에 풀 수 있게 되면, 모든 NPC 문제도 다항시간에 해결 가능하다.

 

---

✅ [3] 외워야 할 NPC 문제 리스트 (정의 말고 이름만 암기)

문제마다 알고리즘 외우지 말고,
**“NPC 문제 이름과 종류”**만 외워두면 충분해!

• 📌 논리 / 집합 / 조합
  • 부울 만족 문제(SAT)
    여러 부울 식이 주어졌을 때, 모두를 참으로 만들 수 있는 변수 할당이 존재하는지 판단
  • 3절 만족 문제(3-SAT)
    각 부울 식이 3개의 변수로만 구성된 SAT 문제. SAT보다 구조가 제한적이지만 여전히 NP-완전
  • 부분집합 합(Subset Sum)
    주어진 숫자들 중에서 합이 K가 되는 부분집합이 존재하는지 묻는 문제
    → 전체 부분집합 탐색 또는 DP 활용
  • 집합 분할(Partition)
    숫자 집합을 합이 같은 두 집합으로 나눌 수 있는지 확인
    → 전체 합/2로 만들 수 있는 부분집합이 있는지 확인
  • 집합 덮기(Set Cover)
    전체 집합을 덮을 수 있는 최소한의 부분집합들을 찾는 문제
    → Greedy 방식: 가장 많이 덮는 집합부터 선택

  ---

  📌 그래프 기반
  • 정점 커버(Vertex Cover)
    모든 간선을 커버하기 위해, 간선의 양 끝점 중 하나 이상 포함하는 최소 정점 집합 찾기
    → Greedy 근사 알고리즘 존재 (2-approx)
  • 독립 집합(Independent Set)
    서로 연결되지 않은 정점들로 구성된 최대 크기의 집합을 찾는 문제
    → Vertex Cover의 여집합 성질 사용 가능
  • 클리크(Clique)
    그래프 내에서 모든 정점이 서로 연결된 완전 부분그래프 중 최대 크기를 찾는 문제
  • 그래프 색칠하기(Graph Coloring)
    인접한 정점끼리는 다른 색으로 칠하면서, 필요한 색의 수를 최소화
    → 채널 할당 등 실생활 응용 多
  • 해밀토니안 사이클(Hamiltonian Cycle)
    모든 정점을 한 번씩만 방문하고 원래 위치로 돌아오는 경로가 존재하는지
    → DFS + 방문체크 방식으로 탐색
  • 최장 경로(Longest Path)
    시작점 → 도착점까지 가장 긴 단순 경로 찾기 (반복 X)
    → 일반 그래프에서는 매우 어려움 (DAG일 때는 DP 가능)

  ---

  📌 경로 최적화
  • 외판원 순회 문제(Traveling Salesman Problem, TSP)
    모든 도시를 한 번씩 방문하고 최단 거리로 순회 후 시작점으로 돌아오는 경로
    → MST 기반 근사 알고리즘 (2-approx)

  ---

  📌 자원 / 스케줄링
  • 0-1 배낭 문제(Knapsack)
    정해진 무게 한도 내에서 최대 가치를 얻는 물건 조합 찾기
    → DP or 이익/무게 비율 기반 근사
  • 통 채우기(Bin Packing)
    각 물건을 최소 개수의 통에 나누어 담기 (통 크기 제한 있음)
    → First-Fit, Best-Fit 등의 휴리스틱 사용
  • 작업 스케줄링(Job Scheduling)
    여러 작업을 여러 기계에 배치하여 전체 종료 시간이 가장 짧도록
    → 가장 덜 바쁜 기계에 먼저 넣는 Greedy 활용 가능

---

✅ 요약 – 이것만 외우면 NP 파트 끝

항목외워야 할 것

4가지 분류	P, NP, NP-Complete, NP-Hard 정의+포함관계
Reduction 개념	변환 흐름(입력 변환 → 해 구하기 → 해 변환), 추이 성질
문제 이름	대표 NPC 문제 이름만 외우기, 알고리즘 X

 

 

CH08. 근사알고리즘

• 교재에 나와있는 근사알고리즘- stepbystep으로 풀고 적용할 수 있어야 함. (3-4문제 나옴)
• 과정구하지 않고 최적해 찾으라 하면 직관적으로 찾아내기(ex. 이런 게 해밀토니언 사이클이 뭔지 알고 있어야 이게 해밀토니언 사이클이다~말할 수 있음)
  • 실제로 최적해 정확히 찾고자 한다면 지수복잡도, 다항시간 이상의 복잡도 - 다항시간보다 복잡도가 더 높은 알고리즘은 주어진 입력 너무 커서 해결 불가 - 이왕이면 다항시간안에 해결할 수 있는 근사알고리즘 봤던 것
• 문제들에 따라 근사알고리즘 나옴 푸는 과정에 따라 stepbystep으로 보일 수 있어야 함
• EX appox_MST이용 → MST조차도 찾으라고 할 수도 있는데 MST는 찾는 과정 보이지 않고 바로 찾으면 됨
  • 짧은 쪽 먼저 연결하면서 cycle없이. 이거고, 이거에 따라 경로 이렇게 구성 → 그렇게 했을 때 근사 알고리즘으로 취해진 결과는 ~이다

*근사비율= 근사해/최적해

✅ 1. 여행자 문제 (TSP)

📌 문제

• 모든 도시를 한 번씩만 방문하고 시작 도시로 돌아오는 최소 경로 찾기

📌 근사 알고리즘: Approx_MST_TSP

(삼각 부등식 만족, 대칭 거리 조건 전제)

📌 Step-by-step

1. MST 찾기 (Prim 또는 Kruskal)
2. MST 기반 DFS 순회로 방문 순서 얻기
3. 중복된 정점 제거, 단 마지막 시작 도시는 남겨두기

예: 1 2 4 3 4 5 4 6 7 6 4 2 1 → 1 2 4 3 5 6 7 1

📌 근사 비율

• ≤ 2.0
• 이유: MST 간선이 두 번씩 사용됨 + 삼각 부등식 이용하여 길이 줄임

---

✅ 2. 정점 커버 문제 (Vertex Cover)

📌 문제

• 모든 간선을 커버하는 최소 수의 정점 집합 찾기

📌 근사 알고리즘: Approx_Matching_VC

(극대 매칭 기반)

📌 Step-by-step

1. 극대 매칭 M 찾기: 겹치지 않는 간선들 선택
2. M에 속한 모든 간선의 양 끝점을 정점 커버로 선택

예: 간선 6개 선택 → 정점 12개가 커버 집합

📌 근사 비율

• ≤ 2.0
• 이유: 최적해는 적어도 하나의 끝점 필요 → 근사해는 각 간선당 2개 선택

---

✅ 3. 통 채우기 문제 (Bin Packing)

📌 문제

• 주어진 물건들을 가장 적은 수의 통에 나눠 담기

📌 근사 알고리즘

• First Fit (FF)
• Next Fit (NF)
• Best Fit (BF)
• Worst Fit (WF)

📌 Step-by-step (FF 예시)

1. 왼쪽부터 통들을 보며, 처음으로 들어갈 수 있는 통에 삽입
2. 들어갈 통이 없으면 새 통 생성
3. 반복

📌 근사 비율

• FF, BF, WF: ≤ 2.0
• NF: ≤ 2.0, 성능은 조금 떨어짐

---

✅ 4. 작업 스케줄링 문제 (Job Scheduling)

📌 문제

• n개의 작업을 m개의 기계에 배정하여 전체 작업이 가장 빨리 끝나게

📌 근사 알고리즘: Approx_JobScheduling

📌 Step-by-step

1. 각 기계의 작업 종료 시간 배열 L[j] = 0 초기화
2. 작업 i를 가장 빨리 끝나는 기계에 배정
3. 해당 기계의 종료 시간 갱신: L[j] += ti
4. 반복 후 max(L) 리턴

📌 근사 비율

• ≤ 2.0
• 이유: 하나의 작업이 다른 기계보다 늦게 배정되더라도 전체 평균 종료 시간 대비 2배 이내

---

✅ 5. 클러스터링 문제 (k-Center Clustering)

📌 문제

• n개의 점을 k개의 그룹으로 나누고, 최대 그룹 직경이 최소가 되도록 센터 선택

📌 근사 알고리즘: Approx_k_Clusters

(가장 멀리 떨어진 점을 센터로)

📌 Step-by-step

1. 임의의 점을 첫 번째 센터로 선택
2. 매 반복마다 기존 센터들과 가장 멀리 떨어진 점을 다음 센터로 선택
3. k개의 센터 정한 뒤, 각 점을 가장 가까운 센터 그룹에 배정

📌 근사 비율

• ≤ 2.0
• 이유: 최적 그룹 직경을 d라 할 때, 근사해 그룹 직경은 최대 2d

---

🟨 마무리 요약표

           문제유형                             알고리즘 이름                                         핵심 방식                    근사 비율

  

여행자 문제	Approx_MST_TSP	MST + DFS + 중복 제거	≤ 2.0
정점 커버	Approx_Matching_VC	극대 매칭 간선의 양 끝점 선택	≤ 2.0
통 채우기	FF / NF / BF / WF	조건에 맞는 통에 삽입	≤ 2.0
작업 스케줄링	Approx_JobScheduling	가장 빨리 끝나는 기계에 배정	≤ 2.0
클러스터링	Approx_k_Clusters	기존 센터와 가장 먼 점 선택

 

 

CH09. 해 탐색 알고리즘

• 4가지중 2가지는 안 함 백트래킹과 분기한정만! 각각 한문제씩, 하나는 한 문제에 대해 둘 다 풀어라!(그리 오래 걸리진 않을 것임)
  • 과정에 있어서는 상태공간트리를 다 작성하여 과정 보여야 함
  • 주어진 문제 해결 위해 백트래킹으로 해결하세요!하면 백트래킹기법에서 사용하는 promising함수에 대해 정의하기. 가지치기 기준 어케 잡을건지, promision function을 뭘로 썼는지, promising에 있어서 어떤 기준을 갖고 값을 뭘 썼는지 명시.
  • 굳이 수식으로 적지 않아도 말로 표현할 수 있으면 됨
    • 어떠한 경우에 가지를 더 쳐서 만들어갈거다~로 말할 수 있으면됨
• 기본적으로 backtracking 분기한정기법 알고리즘단계가 어떤 검사를 하고 들어가는지에 대한 구성은 머릿속에 들어가 있어야 함
• 분기한정- promising함수, bound값 유의- 어떤 기준으로 bound값 정해 계산할건지 명시
• 상태공간트리의 일부 동그라미, 네모들을 만들어주면 안에 내용 채워넣을 수 있게 할거임-없으면 그려서 하기

 

✅ 공통 암기 포인트 (Backtracking & Branch and Bound)

• 상태공간트리: 해를 찾는 과정 전체를 트리 구조로 구성
• DFS / BFS / Best-First 탐색 방식 구분
• Promising 함수: 이 노드가 해를 포함할 가능성이 있는지 판별
  • "이 노드(지금 상황)가 앞으로 더 내려가서 '좋은 해(해답)'가 나올 가능성이 있냐?"
• 가지치기 (pruning): promising하지 않으면 탐색 중단
• Bound (한정값): 분기한정에서는 해의 하한(또는 상한)을 계산해서 가지치기 기준으로 사용

---

✅ 백트래킹 (Backtracking) – DFS 기반

항목설명

탐색방식	DFS (깊이우선탐색), 순환함수 사용
사용문제	TSP, N-Queens, Sum-of-Subsets, Graph Coloring
핵심요소	promising 함수 정의 + 상태공간트리 구성 + 가지치기
주요전략	다음 단계에서 유망한 해인지 미리 확인하고 진행
시간복잡도	최악의 경우 지수시간, 하지만 가지치기로 줄어듦

 

---

📌 예시 암기: TSP 백트래킹

• 입력: 현재 tour
• 조건: 모든 정점 방문 & 시작점으로 복귀
• promising 조건: 현재 tour의 거리 < bestSolution의 거리
• Step-by-step:
  1. tour 확장
  2. newTour 생성
  3. promising하면 재귀 호출
  4. 완전한 해면 best 갱신

---

📌 예시 암기: N-Queens

• 각 퀸은 서로 같은 행/열/대각선에 있으면 안 됨
• promising 함수: 같은 열/대각선 체크
• 상태공간트리: 행 하나씩 내려가며 열 선택
• 최대 노드 수: 완전탐색 시 nnn^nnn, 백트래킹 시 훨씬 감소

---

📌 예시 암기: Sum-of-Subsets

• 목표: 부분 집합의 합 = W
• promising 조건: 현재까지의 합 + 남은 아이템 최대합 ≥ W
• 상태공간트리 구성: 각 아이템 선택/비선택 분기

---

✅ 분기한정 (Branch and Bound) – Best-First 기반

항목설명

탐색방식	Best-First Search (우선순위 큐 사용)
사용문제	TSP, 0/1 Knapsack
핵심요소	bound 계산 → 우선순위 큐에서 가장 유망한 노드부터 탐색
가지치기 조건	bound ≥ bestValue → 탐색 중단
자료구조	priority queue (heap 기반)

 

---

📌 예시 암기: TSP 분기한정

• Bound 계산:
  • 현재까지 경로 비용 + 앞으로 방문할 정점들의 최소 2간선 평균값의 합 ÷ 2
  • (edge 중복 고려: 왕복이므로)
• Step-by-step:
  1. 초기 상태 [A] → 모든 점의 최소 간선 2개 합 ÷ 2 = 초기 bound
  2. [A,B], [A,C], ... 자식 상태 생성
  3. 가장 낮은 bound부터 확장
  4. 완전한 해면 bestValue 갱신

---

📌 예시 암기: 0/1 Knapsack

• 우선순위: 단위 무게당 가치 큰 순으로 정렬
• bound 계산:
  • 현재 가치 + 남은 용량에 대해 분할 가능한 아이템의 최대 기댓값
• 탐색 방식: Best-First + bound 비교 가지치기
• 해는 capacity 초과 X하며 value 최대인 경우

---

✅ 시험 출제 포인트 요약

항목내용

백트래킹	TSP, N-Queens, Subset Sum 중 1문제 또는 함께 출제
분기한정	TSP 또는 0/1 Knapsack 중심
상태공간트리	그림 그릴 수 있어야 함 (동그라미 or 네모 안에 값 표시)
promising	말로 설명 가능해야 함: "이 조건을 넘기면 가지치기"
bound	분기한정에서는 정확히 어떻게 계산하는지 외워야 함
비교문제	한 문제를 백트래킹/분기한정 두 가지로 모두 푸는 문제 가능성 높음

 

 

✅ 백트래킹 vs 분기한정 비교표

항목                                                백트래킹 (Backtracking)                             분기한정 (Branch and Bound)

목표	해가 존재하는가? / 최적해 찾기	항상 최적해(최댓값/최솟값) 찾기
탐색 순서	DFS (깊이우선탐색)	Best-First / BFS (우선순위 큐 or 큐)
상태공간트리	O (부분 해 하나씩 늘리며 탐색)	O (해당 노드의 bound로 우선순위 정함)
가지치기 기준	promising 함수 (가능성 없으면 prune)	bound 값 (최적해보다 못하면 prune)
자료구조	스택(암시적) / 재귀	우선순위 큐(PQ) 또는 큐
탐색 순서 기준	자식 노드를 순서대로 깊게	bound 값이 가장 좋은 것부터
적용 예시	N-Queens, TSP, Sum of Subsets	TSP, 0/1 Knapsack, Job Scheduling
실행 흐름	일단 깊이 가면서 유망하지 않으면 중단	우선순위 높은 가지부터 확장
복잡도 줄이는 핵심	promising 함수로 pruning	bound 계산으로 pruning

 

 

---

✅ 예시 비교: TSP 문제

백트래킹분기한정

탐색 방식	DFS 순환함수로 모든 순열 탐색 (유망하지 않으면 중단)	현재 경로 + 예상 경로 비용(bound) 계산해서 가장 저렴한 것부터 탐색
가지치기	현재 거리 + 예상 거리 > best → stop	bound ≥ 현재 best → stop

 

---

✅ 누가 더 효율적?

• 보통 분기한정이 더 효율적
  → bound 계산 덕분에 훨씬 더 많은 부분을 가지치기 가능

---

✅ 같이 쓰일 수 있어?

그치! 같이 쓰는 경우도 많아.

• 예를 들어 TSP 문제에서:
  • 탐색 방식은 DFS처럼 백트래킹으로
  • 가지치기는 bound 값 계산으로 (분기한정 방식)

→ 이렇게 혼합형 전략도 쓰임! 💡

---

✅ 핵심 차이 요약

백트래킹: 깊이우선 탐색하며 유망하지 않으면 가지치기
분기한정: bound 기준으로 가장 좋은 걸 먼저 탐색 (우선순위 큐 사용)
→ 둘 다 최적해 찾지만 탐색 방식과 pruning 방식이 다름!

 

✅ 💯 교수님이 낼 확률 높은 문제

1️⃣ TSP (Traveling Salesman Problem) 🛣

도시들을 한 번씩 방문하고 다시 시작점으로 돌아오는 최소 거리 경로 찾기

• 백트래킹: DFS 순환으로 경로 생성 → 거리 < best면 계속, 아니면 가지치기
• 분기한정: bound = 현재 경로 거리 + 예상 경로 거리(남은 점들 최소 간선 평균)

📌 시험 예상 포맷

“다음 TSP 문제를 백트래킹과 분기한정 기법으로 해결되는 상태공간트리 형태로 설명하고, 각 경우의 가지치기 기준과 탐색 순서를 서술하시오.”

---

2️⃣ 0/1 Knapsack 문제 🎒

제한된 무게 안에서 물건을 담아 최대 가치를 얻는 문제

• 백트래킹: 각 아이템 포함/제외로 트리 분기
  → 무게 초과 or 기대 가치 < best → 가지치기
• 분기한정: bound = 현재 가치 + (남은 무게에 대해 기대할 수 있는 최대 추가 가치)

📌 시험 예상 포맷

“다음 0/1 배낭 문제에서 백트래킹과 분기한정 기법을 모두 사용하여 최적해를 탐색하는 과정을 상태공간트리로 나타내고, 가지치기 조건을 각각 설명하시오.”

---

3️⃣ 가능성 낮지만 언급은 됐던 예외

• Sum-of-Subsets 문제
  → 값이 정확히 W가 되는 부분집합 찾기
  → 보통은 백트래킹만 출제, 분기한정은 덜 일반적

---

✅ 정리: 어떤 문제든 구조는 같아!

비교 항목백트래킹 방식분기한정 방식

탐색	DFS	Best-First (우선순위 큐)
promising	무게 초과 X + 기대 가치 가능성 O	bound < best → 가지치기
상태공간트리	깊이 따라 분기	bound 값 기준으로 선택적 확장
리프 노드	완전한 경로 / 배낭 꽉 찼을 때	최적해면 best 갱신