# [08-04] NP-완전 (NP-Complete)
NP-완전은 NP 클래스 중에서 가장 어려운 문제들의 집합으로, 하나만 효율적으로 풀면 모든 NP 문제를 풀 수 있습니다.
🎯 NP-완전이란 무엇인가
NP-완전의 정의
NP-완전(NP-Complete)은 NP의 "가장 어려운" 문제들입니다.
쉬운 비유:
학교 시험으로 비유:
일반 문제 (NP):
- 수학 문제, 영어 문제, 과학 문제
- 각자 어려움이 다름
- 일부는 쉬울 수도
가장 어려운 문제 (NP-완전):
- 모든 과목 중 가장 어려운 문제들
- 이것만 풀 수 있으면 다른 문제도 풀 수 있음
- 예: 수학 올림피아드 문제
핵심:
NP-완전 문제 하나만 빠르게 풀면
→ 모든 NP 문제를 빠르게 풀 수 있음!왜 중요한가?
NP-완전 문제를 다항 시간에 풀 수 있으면 P = NP를 증명하는 것입니다. 이는 100만 달러 상금이 걸린 문제이며, 컴퓨터 과학의 가장 큰 미스터리입니다.
하지만 대부분의 학자들은 P ≠ NP라고 추측합니다. 즉, NP-완전 문제는 효율적으로 풀 수 없다고 생각합니다.
형식적 정의
문제 L이 NP-완전이려면:
조건 1: L ∈ NP
L은 NP에 속해야 함
→ 답을 다항 시간에 검증 가능
조건 2: NP의 모든 문제를 L로 다항 시간에 환원 가능
→ L은 NP에서 가장 어려운 문제
즉:
NP-완전 = (NP에 속함) AND (가장 어려움)🔄 환원(Reduction)이란?
환원의 개념
환원은 한 문제를 다른 문제로 "변환"하는 것입니다.
실생활 비유:
학교에서 집까지 가는 문제를 생각해봅시다. 이 어려운 문제를 "버스 정류장까지 가는 문제"로 바꿀 수 있습니다. 왜냐하면:
- 버스 정류장까지만 가면
- 거기서 버스를 타고 집에 갈 수 있으니까
즉, 어려운 문제를 이미 아는 문제로 변환하여 해결하는 것입니다.
프로그래밍 예시:
# 어려운 문제: 정렬되어 있는지 확인
def is_sorted_hard(arr):
"""어떻게 확인하지? 모르겠음..."""
pass
# 쉬운 문제: 정렬하기 (이미 안다고 가정)
def sort_array(arr):
"""정렬하는 방법은 알고 있음!"""
return sorted(arr)
# 환원: 어려운 문제를 쉬운 문제로 변환!
def is_sorted_easy(arr):
"""
환원을 사용한 해결
1. 어려운 문제: "정렬되어 있나?"
2. 쉬운 문제로 변환: "정렬해보자"
3. 쉬운 문제 풀기: sorted() 사용
4. 비교: 원본 == 정렬된 것?
"""
# 배열을 정렬 (쉬운 문제 풀기)
sorted_arr = sort_array(arr)
# 원본과 비교
return arr == sorted_arr
# 사용
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 3, 2, 4, 5]
print(f"{arr1} 정렬됨? {is_sorted_easy(arr1)}") # True
print(f"{arr2} 정렬됨? {is_sorted_easy(arr2)}") # False이것이 환원입니다. 모르는 문제를 아는 문제로 바꿔서 푸는 것!
다항 시간 환원
기호: A ≤ₚ B
읽기: "A는 B로 다항 시간 환원된다"
의미: "B를 풀 수 있으면 A도 풀 수 있다"
방법:
1. A의 입력을 B의 입력으로 변환 (다항 시간)
2. B를 풀어서 답 얻기
3. B의 답을 A의 답으로 변환 (다항 시간)👑 첫 번째 NP-완전: SAT (Satisfiability, 충족 가능성)
SAT 문제란?
SAT (Boolean Satisfiability)는 역사상 첫 번째로 증명된 NP-완전 문제입니다.
문제:
논리식을 참(True)으로 만드는 변수 할당이 존재하는가?
예를 들어:
(x₁ OR NOT x₂) AND (x₂ OR x₃) AND (NOT x₁ OR NOT x₃)질문: x₁, x₂, x₃에 True/False를 할당해서 전체 식을 True로 만들 수 있는가?
용어 설명:
변수 (Variable): x₁, x₂, x₃ 같은 것 (True 또는 False)
리터럴 (Literal): 변수: x₁ (긍정), 변수의 부정: NOT x₁ (부정)
절 (Clause): 리터럴들을 OR로 연결 예: (x₁ OR NOT x₂)
CNF (Conjunctive Normal Form): 절들을 AND로 연결 예: (절1) AND (절2) AND (절3)SAT 검증하기
def sat_verifier(formula, assignment):
"""
SAT 문제 검증자
문제: 논리식을 만족하는 할당이 있는가?
검증: 주어진 할당이 식을 만족하는가?
시간복잡도: O(n) - n은 절의 개수 → 다항 시간! NP에 속함!
formula: 논리식 (CNF 형태)
[[1, -2], [2, 3], [-1, -3]]
양수 = 변수, 음수 = NOT 변수
예: [1, -2] = (x₁ OR NOT x₂)
assignment: 변수 할당
{1: True, 2: False, 3: False}
예: x₁=True, x₂=False, x₃=False
Returns: True if 할당이 식을 만족
"""
# 각 절(clause)을 하나씩 확인
for clause in formula: # clause: 예를 들어 [1, -2] = (x₁ OR NOT x₂)
clause_satisfied = False # 이 절이 만족되었는가?
# 절 안의 각 리터럴 확인
for literal in clause: # literal: 양수면 변수, 음수면 NOT 변수
var = abs(literal) # 변수 번호 추출 (절댓값)
is_positive = literal > 0 # 긍정인가 부정인가?
value = assignment.get(var, False) # 이 변수의 값 가져오기
# 리터럴의 값 계산
if is_positive:
literal_value = value # 긍정 리터럴
else:
literal_value = not value # 부정 리터럴
# OR 연산: 하나라도 True면 절 만족!
if literal_value:
clause_satisfied = True
break
# 이 절이 만족 안 되면 전체 식이 False!
if not clause_satisfied:
return False
# 모든 절이 만족되면 전체 식이 True!
return True
# ===== 사용 예시 =====
# 논리식: (x₁ OR NOT x₂) AND (x₂ OR x₃) AND (NOT x₁ OR NOT x₃)
formula = [
[1, -2], # (x₁ OR NOT x₂)
[2, 3], # (x₂ OR x₃)
[-1, -3] # (NOT x₁ OR NOT x₃)
]
# 누군가 "이게 답이야!"라고 제시
assignment = {1: True, 2: True, 3: False}
# 검증
is_valid = sat_verifier(formula, assignment)
print(f"검증 결과: {is_valid}") # True검증 과정:
할당 {x₁=True, x₂=True, x₃=False}에 대해:
절 1: (x₁ OR NOT x₂)
- x₁ = True → True
- 절 만족! (OR이므로 하나만 True면 됨)
절 2: (x₂ OR x₃)
- x₂ = True → True
- 절 만족!
절 3: (NOT x₁ OR NOT x₃)
- NOT x₁ = False
- NOT x₃ = True → True
- 절 만족!
모든 절이 만족되므로 전체 식이 True입니다!
📋 대표적인 NP-완전 문제
1. 외판원 문제 (TSP - 결정 버전)
def tsp_decision_verifier(cities, distances, path, max_distance):
"""
외판원 결정 문제 검증자
문제: max_distance 이하로 모든 도시를 방문할 수 있는가?
검증: 주어진 경로가 조건을 만족하는가?
시간: O(n) → NP에 속함 → NP-완전!
cities: 도시 리스트
distances: 거리 행렬 distances[i][j] = i에서 j까지 거리
path: 제시된 경로 (도시 인덱스 리스트)
max_distance: 최대 허용 거리
Returns: True if 경로가 조건 만족
"""
# 1. 모든 도시를 포함하는가?
if set(path) != set(range(len(cities))):
return False
# 2. 중복 없는가?
if len(path) != len(set(path)):
return False
# 3. 총 거리 계산
total_distance = 0
for i in range(len(path)):
from_city = path[i]
to_city = path[(i + 1) % len(path)] # % len(path): path의 마지막 인덱스에 도달했을 때, 다음 인덱스를 0으로 되돌려주는 역할
# 즉, "마지막 도시에서 다시 첫 번째 도시로 연결"하여 순환 경로(Cycle)를 완성
total_distance += distances[from_city][to_city] # distances라는 2차원 배열에서 두 도시 사이의 거리를 찾아 누적 합산
# 4. 제한 이하인가?
return total_distance <= max_distance
# ===== 사용 예시 =====
cities = ['서울', '부산', '대구', '광주']
distances = [
[ 0, 400, 300, 250],
[ 400, 0, 150, 300],
[ 300, 150, 0, 200],
[ 250, 300, 200, 0]
]
# 제시된 경로
proposed_path = [0, 2, 1, 3] # 서울 → 대구 → 부산 → 광주 → 서울
# 검증
result = tsp_decision_verifier(cities, distances, proposed_path, 1000)
print(f"1000km 이하 경로? {result}")2. 부분집합 합 (Subset Sum)
def subset_sum_verifier(numbers, target, subset_indices):
"""
부분집합 합 검증자
문제: 합이 정확히 target인 부분집합이 있는가?
검증: 주어진 부분집합의 합이 target인가?
시간: O(n) → NP에 속함 → NP-완전!
"""
# 인덱스 유효성 확인
for idx in subset_indices:
if idx < 0 or idx >= len(numbers):
return False
# 합 계산
total = sum(numbers[i] for i in subset_indices)
# 목표와 비교
return total == target
# 사용 예시
numbers = [3, 34, 4, 12, 5, 2]
target = 9
proposed = [0, 2, 5] # numbers[0] = 3, [2] = 4, [5] = 2
result = subset_sum_verifier(numbers, target, proposed)
print(f"합이 {target}? {result}") # 3 + 4 + 2 = 9 → True3. 그래프 색칠
def graph_coloring_verifier(graph, coloring, k):
"""
그래프 k-색칠 검증자
문제: k개 색으로 그래프를 칠할 수 있는가?
(인접한 정점은 다른 색)
검증: 주어진 색칠이 유효한가?
시간: O(V + E) → NP에 속함 → NP-완전!
"""
# 1. 모든 정점이 색칠되었는가?
vertices = set(graph.keys())
if set(coloring.keys()) != vertices:
return False
# 2. k개 이하 색만 사용했는가?
colors_used = set(coloring.values())
if len(colors_used) > k:
return False
# 3. 인접한 정점이 다른 색인가?
for vertex in graph:
vertex_color = coloring[vertex]
for neighbor in graph[vertex]:
neighbor_color = coloring[neighbor]
# 같은 색이면 유효하지 않음!
if vertex_color == neighbor_color:
return False
return True
# 사용 예시
graph = {
'A': ['B', 'C'],
'B': ['A', 'C', 'D'],
'C': ['A', 'B', 'D'],
'D': ['B', 'C']
}
proposed_coloring = {
'A': '빨강',
'B': '파랑',
'C': '초록',
'D': '빨강'
}
result = graph_coloring_verifier(graph, proposed_coloring, 3)
print(f"3색 색칠 가능? {result}") # True💡 실무 팁
NP-완전 문제 인식하기
패턴 1: 조합 문제
"모든 ~를 선택/방문/배치하는 방법"
예:
- 모든 도시를 방문하는 경로
- 모든 정점을 연결하는 트리
- 모든 과목을 배정하는 시간표
→ 조합 폭발 가능성
→ NP-완전일 가능성 높음패턴 2: "존재하는가?" 형태
"~를 만족하는 방법이 존재하는가?"
예:
- k개 색으로 칠할 수 있는가?
- 목표 합을 만들 수 있는가?
- 모든 조건을 만족하는 할당이 있는가?
→ NP-완전 문제의 전형적 형태패턴 3: 알려진 NP-완전과 유사
def check_if_npc_like(problem_description):
"""
문제가 NP-완전과 유사한지 확인
체크리스트:
1. 외판원 문제와 비슷한가?
2. 배낭 문제와 비슷한가?
3. 그래프 색칠과 비슷한가?
4. 부분집합 선택 문제인가?
"""
keywords = {
'TSP형': ['경로', '순회', '방문', '최단'],
'배낭형': ['선택', '용량', '제한', '최대화'],
'색칠형': ['할당', '충돌', '인접', '다른'],
'부분집합형': ['합', '목표', '조합', '선택']
}
# 각 패턴 확인
for pattern_type, words in keywords.items():
if any(word in problem_description for word in words):
print(f"주의: {pattern_type} 문제 패턴 감지!")
print("→ NP-완전일 가능성 있음")
print("→ 작은 입력으로 테스트 권장")
return True
return False실무 대응 전략
전략 1: 입력 크기 확인
문제를 받으면 가장 먼저 입력 크기를 확인하세요.
def choose_strategy(problem_type, n):
"""
입력 크기에 따른 전략 선택
problem_type: 문제 유형 (예: 'TSP', 'knapsack')
n: 입력 크기
Returns: 권장 전략
"""
if n <= 15:
return "정확한 알고리즘 (브루트포스 가능)"
elif n <= 30:
return "동적 계획법 시도 (문제에 따라)"
elif n <= 1000:
return "휴리스틱 또는 근사 알고리즘"
else:
return "그리디 휴리스틱 (빠른 근사해)"
# 예시
print(choose_strategy('TSP', 10)) # 정확한 알고리즘
print(choose_strategy('TSP', 100)) # 휴리스틱
print(choose_strategy('TSP', 10000)) # 그리디 휴리스틱전략 2: 근사 알고리즘 사용
정확한 답 대신 "충분히 좋은" 답을 빠르게 구하기:
근사 비율:
- 2-근사: 최적해의 2배 이내 보장
- 1.5-근사: 최적해의 1.5배 이내 보장
예: TSP 2-근사 알고리즘
1. 최소 신장 트리(MST) 구하기 - O(E log V)
2. MST를 순회로 변환
3. 결과: 최적해의 2배 이내 보장
장점: 다항 시간 + 품질 보장
단점: 최적해는 아님전략 3: 제약 조건 완화
원래 문제: 너무 어려움
→ 일부 제약 완화
→ 쉬운 문제로 변환
예: 외판원 문제
- 완화: 도시를 여러 번 방문 허용
- 결과: 최소 신장 트리로 해결 가능 (다항 시간)
- 활용: 하한(lower bound) 계산에 사용전략 4: 작은 부분 문제로 분할
def divide_and_conquer_npc(large_problem):
"""
큰 NP-완전 문제를 작은 부분으로 나누기
전략:
1. 지리적/논리적으로 분할
2. 각 부분 독립적으로 해결
3. 결과 병합
예: 1000개 도시 TSP
→ 10개 지역으로 나누기 (각 100개 도시)
→ 각 지역 내 TSP 해결
→ 지역 간 연결
주의: 최적해 보장 안 됨
장점: 현실적 시간 내 해결
"""
pass실무 체크리스트
새로운 문제를 만났을 때:
□ 1단계: 문제 분류
- 결정 문제인가? 최적화 문제인가?
- 조합 문제인가?
- 검증은 쉬운가?
□ 2단계: NP-완전 의심
- 알려진 NP-완전 문제와 유사한가?
- 작은 입력도 오래 걸리는가?
- 지수적 복잡도가 의심되는가?
□ 3단계: 입력 크기 확인
- n ≤ 20: 정확한 알고리즘 시도
- 20 < n ≤ 1000: 근사/휴리스틱
- n > 1000: 빠른 휴리스틱
□ 4단계: 전략 선택
- 정확도 중요: 작은 입력만 처리
- 속도 중요: 근사 알고리즘
- 둘 다 중요: 제약 완화 또는 분할
□ 5단계: 검증
- 결과의 품질 측정
- 최적해와 비교 (가능하면)
- 실무 요구사항 만족 확인실제 사례
사례 1: 물류 최적화
문제: 100개 거점을 방문하는 최단 경로 → TSP (NP-완전)
해결:
1. 입력 크기 (n=100): 정확한 해는 불가능
2. 전략: 2-opt 휴리스틱
- 초기 경로 생성 (그리디)
- 반복적으로 개선
- 시간: 몇 초 이내
3. 결과: 최적해의 5% 이내 (실무 충분)
교훈: 완벽한 해보다 빠른 "좋은 해"가 실무적사례 2: 시간표 작성
문제: 과목-교수-시간 할당 (제약 많음) → 그래프 색칠 변형 (NP-완전)
해결:
1. 제약 조건 우선순위 분류
- 필수 제약: 반드시 만족
- 선호 제약: 가능하면 만족
2. 단계적 접근
- 필수 제약만 고려 (백트래킹)
- 선호 제약 추가 (그리디)
3. 결과: 완벽하지 않지만 실용적
교훈: 제약 완화로 다항 시간 해결 가능🎯 핵심 정리
NP-완전이란?
정의:
1. NP에 속함 → 답을 다항 시간에 검증 가능
2. NP 중 가장 어려움 → 모든 NP 문제를 이것으로 환원 가능
의미: "NP에서 가장 어려운 문제들"환원(Reduction)
A ≤ₚ B: "A를 B로 다항 시간에 변환 가능"
의미:
- B를 풀 수 있으면 A도 풀 수 있음
- B가 쉬우면 A도 쉬움
- A가 어려우면 B도 어려움
용도:
- 문제 난이도 비교
- NP-완전 증명대표 문제들
NP-완전 문제:
- SAT: 첫 번째 NP-완전 (Cook-Levin 정리)
- 외판원 (결정): max 거리 이하 경로?
- 부분집합 합: 목표 합 만들기?
- 그래프 색칠: k개 색으로 칠하기?
- 클리크: k개 완전 그래프?
- 해밀턴 경로: 모든 정점 한 번씩?왜 중요한가?
하나만 풀면:
NP-완전 문제 하나를 다항 시간에 풀면
→ 모든 NP 문제를 다항 시간에 풀 수 있음
→ P = NP 증명!
→ 100만 달러 상금
하지만:
대부분 학자들은 불가능하다고 생각
→ P ≠ NP
→ 효율적 알고리즘 없음
→ 근사/휴리스틱 사용🔗 다음 글에서는
[08-05] NP-난해 (NP-Hard)
- NP-난해의 정의: NP-완전보다 더 일반적인 개념
- NP-완전과의 차이: NP에 속할 필요 없음
- 결정 vs 최적화: 왜 최적화 문제는 NP-난해인가
- 대표 예시: 외판원 최적화, 배낭 최적화, 정지 문제
이전 글: [08-03] 클래스 NP
다음 글: [08-05] NP-난해
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자