# [08-01] 결정 문제 (Decision Problems)
결정 문제는 답이 Yes 또는 No인 문제로, 계산 복잡도 이론의 기본 단위입니다.
🎯 계산 복잡도 이론이란?
섹션 개요
알고리즘 분석에서는 주어진 알고리즘의 효율성을 측정했습니다.
알고리즘 분석:
"이 알고리즘이 얼마나 빠른가?"
예:
- 병합 정렬: O(n log n)
- 버블 정렬: O(n²)
→ 병합 정렬이 더 빠르다!계산 복잡도 이론에서는 문제 자체의 난이도를 분석합니다.
복잡도 이론:
"이 문제를 효율적으로 풀 수 있는가?"
예:
- 정렬 문제: 효율적 알고리즘 존재 (O(n log n))
- 외판원 문제: 효율적 알고리즘이 없을 수도 있음
→ 문제의 본질적 어려움!핵심 질문들
이번 섹션에서 다룰 근본적 질문:
질문 1: 어떤 문제들을 효율적으로 풀 수 있는가?
→ P 클래스
질문 2: 답은 빠르게 확인할 수 있지만 찾기는 어려운 문제는?
→ NP 클래스
질문 3: 가장 어려운 문제들은 무엇인가?
→ NP-완전
질문 4: 컴퓨터가 절대 풀 수 없는 문제도 있는가?
→ 계산 불가능성왜 중요한가?
실무적 중요성:
새로운 문제를 만났을 때:
시나리오 1: 문제가 P에 속함
→ "효율적인 알고리즘이 존재한다"
→ 열심히 찾으면 된다!
→ 예: 정렬, 최단 경로
시나리오 2: 문제가 NP-완전
→ "효율적인 알고리즘이 없을 가능성 높음"
→ 근사 알고리즘 사용
→ 또는 작은 입력만 처리
→ 예: 외판원, 배낭
시나리오 3: 문제가 계산 불가능
→ "컴퓨터로 절대 풀 수 없음"
→ 다른 접근 필요
→ 예: 정지 문제이론적 중요성:
P vs NP 문제:
- 클레이 수학연구소의 7대 난제
- 해결하면 100만 달러 상금
- 컴퓨터 과학 최대의 미스터리
의미:
"빠르게 확인할 수 있으면
빠르게 찾을 수도 있는가?"
영향:
- 암호학: 해결되면 현재 암호 체계 붕괴
- 최적화: 많은 문제가 쉬워짐
- 수학: 자동 증명 가능이번 섹션 구성
08-01. 결정 문제 (Decision Problems)
↓ 문제를 Yes/No로 표현
08-02. 클래스 P
↓ 효율적으로 풀 수 있는 문제들
08-03. 클래스 NP
↓ 효율적으로 검증할 수 있는 문제들
08-04. NP-완전 (NP-Complete)
↓ 가장 어려운 NP 문제들
08-05. NP-난해 (NP-Hard)
↓ NP-완전만큼 또는 더 어려운 문제들
08-06. 다항 시간 환원 (Polynomial-time Reduction)
↓ 문제들을 비교하는 방법
08-07. 계산 불가능성 (Undecidability)
↓ 풀 수 없는 문제들
08-08. 정지 문제 (Halting Problem)
↓ 대표적인 불가능 문제
08-09. 기타 복잡도 클래스
↓ co-NP, PSPACE, EXPTIME 등🎯 결정 문제란 무엇인가
결정 문제의 정의
결정 문제(Decision Problem)는 답이 Yes 또는 No인 문제입니다.
실생활 비유:
일반 질문 vs 결정 문제:
일반 질문:
"이 배열을 정렬하면?"
→ 답: [1, 2, 3, 4, 5]
→ 답이 배열 (복잡)
결정 문제:
"이 배열이 정렬되어 있나?"
→ 답: Yes 또는 No
→ 답이 단순!
일반 질문:
"서울에서 부산까지 최단 경로는?"
→ 답: 특정 경로
→ 답이 경로 (복잡)
결정 문제:
"서울에서 부산까지 300km 이내 경로가 있나?"
→ 답: Yes 또는 No
→ 답이 단순!왜 Yes/No로 제한할까?
이유 1: 이론적 분석이 쉬움
- 답의 형태가 단순
- 수학적 모델링 용이
- 복잡도 비교 명확
이유 2: 충분히 강력함
- 모든 문제를 결정 문제로 변환 가능
- 결정 문제 풀면 원래 문제도 풀 수 있음
- (나중에 증명)
이유 3: 본질에 집중
- 문제의 핵심 어려움 파악
- 불필요한 복잡성 제거형식적 정의
결정 문제:
- 입력: 문자열 w
- 질문: w가 조건 C를 만족하는가?
- 출력: Yes 또는 No
수학적:
L = {w | w는 조건 C를 만족}
L은 "언어(Language)"라고 부름
결정 문제 = 언어 인식 문제예시:
# 결정 문제 1: 짝수 판별
def is_even(n):
"""
결정 문제: n이 짝수인가?
입력: 정수 n
출력: Yes (True) 또는 No (False)
언어 표현:
L_even = {0, 2, 4, 6, 8, ...}
= {n | n % 2 == 0}
"""
return n % 2 == 0
# 테스트
print(is_even(4)) # True (Yes)
print(is_even(7)) # False (No)
# 결정 문제 2: 정렬 여부
def is_sorted(arr):
"""
결정 문제: 배열이 정렬되어 있는가?
입력: 배열
출력: Yes (True) 또는 No (False)
언어 표현:
L_sorted = {모든 정렬된 배열}
"""
for i in range(len(arr) - 1):
if arr[i] > arr[i + 1]:
return False # No
return True # Yes
# 테스트
print(is_sorted([1, 2, 3, 4])) # True
print(is_sorted([1, 3, 2, 4])) # False🔄 최적화 문제 vs 결정 문제
문제 변환
대부분의 실무 문제는 최적화 문제입니다. 하지만 이를 결정 문제로 변환할 수 있습니다.
변환 패턴:
최적화 문제:
"최소/최대 값은?"
↓ 변환
결정 문제:
"값이 k 이하/이상인가?"예시 1: 최단 경로
# 최적화 문제: 최단 경로 찾기
def shortest_path(graph, start, end):
"""
최적화 문제
질문: start에서 end까지의 최단 거리는?
답: 숫자 (예: 42km)
복잡: 경로를 찾아야 함
"""
# 다익스트라 알고리즘 등 사용
# ...
return distance
# 결정 문제: 경로 존재 여부
def has_path_within(graph, start, end, max_distance):
"""
결정 문제
질문: start에서 end까지 max_distance 이하의 경로가 있는가?
답: Yes 또는 No
단순: 존재 여부만 확인
"""
shortest = shortest_path(graph, start, end)
return shortest <= max_distance # Yes or No
# 사용 예시
graph = {
'A': [('B', 10), ('C', 30)],
'B': [('D', 20)],
'C': [('D', 5)],
'D': []
}
# 최적화 문제
distance = shortest_path(graph, 'A', 'D')
print(f"최단 거리: {distance}km") # 30km
# 결정 문제
result = has_path_within(graph, 'A', 'D', 25)
print(f"25km 이내 경로 있나? {result}") # No
result = has_path_within(graph, 'A', 'D', 35)
print(f"35km 이내 경로 있나? {result}") # Yes예시 2: 외판원 문제 (TSP)
# 최적화 문제: 최단 순회 찾기
def tsp_optimization(cities, distances):
"""
최적화 TSP (Traveling Salesman Problem)
질문: 모든 도시를 방문하는 최단 경로는?
답: 경로와 거리
매우 어려움!
"""
# 모든 순열 확인하거나 휴리스틱 사용
best_tour = None
best_distance = float('inf')
# ... 복잡한 알고리즘 ...
return best_tour, best_distance
# 결정 문제: 제한된 순회 존재 여부
def tsp_decision(cities, distances, max_distance):
"""
결정 TSP
질문: 총 거리가 max_distance 이하인 순회가 있는가?
답: Yes 또는 No
여전히 어렵지만 형태는 단순!
"""
tour, distance = tsp_optimization(cities, distances)
return distance <= max_distance # Yes or No
# 사용 예시
cities = ['서울', '부산', '대구', '광주']
distances = [
[0, 400, 300, 250],
[400, 0, 150, 300],
[300, 150, 0, 200],
[250, 300, 200, 0]
]
# 최적화 문제
tour, distance = tsp_optimization(cities, distances)
print(f"최단 순회: {tour}, 거리: {distance}km")
# 결정 문제
result = tsp_decision(cities, distances, 1000)
print(f"1000km 이내 순회 있나? {result}") # Yes or No왜 결정 문제가 충분한가?
핵심 정리:
정리:
최적화 문제를 풀 수 있으면 → 결정 문제도 풀 수 있다
증명:
최적값을 알면 → "값이 k 이하인가?"에 답할 수 있음
역방향도 가능:
결정 문제를 여러 번 풀면 → 최적값을 찾을 수 있다 (이진 탐색)이진 탐색으로 최적값 찾기:
def find_shortest_path_value(graph, start, end):
"""
결정 문제를 여러 번 풀어서 최적값 찾기
전략:
1. 가능한 거리 범위 설정
2. 이진 탐색으로 최소 거리 찾기
3. 결정 문제만 사용!
"""
# 1. 범위 설정
low = 0
high = 10000 # 충분히 큰 값
# 2. 이진 탐색
result = high
while low <= high:
mid = (low + high) // 2
# 결정 문제: mid 이하 경로 있나?
if has_path_within(graph, start, end, mid):
result = mid # 가능! 더 작은 값 시도
high = mid - 1
else:
low = mid + 1 # 불가능! 더 큰 값 필요
return result
# 사용
graph = {
'A': [('B', 10), ('C', 30)],
'B': [('D', 20)],
'C': [('D', 5)],
'D': []
}
min_distance = find_shortest_path_value(graph, 'A', 'D')
print(f"최단 거리: {min_distance}") # 30
# 결정 문제만으로 최적값을 찾았다!
# 이진 탐색 횟수: O(log max_distance)결론:
결정 문제가 어려우면 → 최적화 문제도 어렵다
결정 문제가 쉬우면 → 최적화 문제도 쉽다
따라서:
결정 문제의 복잡도 = 원래 문제의 복잡도📚 형식 언어로서의 문제
언어의 개념
형식 언어(Formal Language)는 문자열의 집합입니다.
알파벳:
Σ = {0, 1} (또는 다른 기호들)
문자열:
w = "0110" (알파벳의 기호들을 나열)
언어:
L = {모든 짝수 개의 0을 가진 문자열}
= {"", "00", "11", "0011", "1100", ...}결정 문제 = 언어 인식:
문제: 주어진 문자열 w가 언어 L에 속하는가?
답: Yes (w ∈ L) 또는 No (w ∉ L)
예:
L = {짝수를 표현하는 이진 문자열}
w = "100" (이진수 4)
→ 4는 짝수 → Yes예시: 소수 판별
def is_prime_language(n):
"""
소수 판별을 언어 문제로
언어 정의:
L_prime = {2, 3, 5, 7, 11, 13, ...}
= {모든 소수}
결정 문제:
입력 n이 L_prime에 속하는가?
"""
if n < 2:
return False # 1 이하는 소수 아님
# 소수 판별
for i in range(2, int(n ** 0.5) + 1): # int(n ** 0.5): 소수(Prime Number) 판별을 할 때 사용(sqrt{n})
if n % i == 0:
return False # 약수 발견, 소수 아님
return True # 소수!
# 언어 관점에서 보기
print("2 ∈ L_prime?", is_prime_language(2)) # True
print("4 ∈ L_prime?", is_prime_language(4)) # False
print("17 ∈ L_prime?", is_prime_language(17)) # True
# 언어:
L_prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, ...}왜 언어로 표현하는가?
수학적 엄밀성:
언어 표현:
- 집합론 사용
- 명확한 정의
- 증명 가능
예:
L₁ = {정렬된 배열}
L₂ = {소수}
L₁ ∩ L₂ = ? (집합 연산 가능)튜링 기계와 연결:
튜링 기계:
- 입력 문자열 받음
- Yes/No 출력
언어:
- 튜링 기계가 Yes라고 하는 문자열들
- L = {w | 튜링 기계 M이 w를 수락}
결정 문제 = 언어 = 튜링 기계
→ 세 가지가 같은 개념!💡 실무 팁
문제를 결정 문제로 변환하기
# 패턴 1: 존재 문제
# "~를 찾아라" → "~가 존재하는가?"
# 최적화: 해밀턴 경로 찾기
def find_hamiltonian_path(graph):
"""모든 정점을 한 번씩 방문하는 경로 찾기"""
# ...
# 결정: 해밀턴 경로 존재 여부
def has_hamiltonian_path(graph):
"""해밀턴 경로가 존재하는가?"""
# ...
return True # or False
# 패턴 2: 제한 조건 추가
# "최소/최대는?" → "k 이하/이상인가?"
# 최적화: 최소 색칠 수
def min_coloring(graph):
"""그래프를 칠하는데 필요한 최소 색 개수"""
# ...
# 결정: k색으로 칠할 수 있는가?
def can_color_with_k(graph, k):
"""k개 색으로 그래프를 칠할 수 있는가?"""
# ...
return True # or False실무에서 결정 문제 활용
# 타당성 검사 (Feasibility Check)
def is_schedule_feasible(tasks, deadline):
"""
주어진 마감일 내에 모든 작업 완료 가능한가?
실무 활용:
- 프로젝트 계획 검증
- 리소스 할당 확인
- 납기일 체크
"""
total_time = sum(task.duration for task in tasks)
return total_time <= deadline # Yes or No
# 제약 만족 (Constraint Satisfaction)
def satisfies_constraints(assignment, constraints):
"""
주어진 할당이 모든 제약을 만족하는가?
실무 활용:
- 시간표 작성
- 자원 배치
- 규칙 검증
"""
for constraint in constraints:
if not constraint.check(assignment):
return False # 제약 위반
return True # 모든 제약 만족🎯 핵심 정리
결정 문제
정의:
- 답이 Yes 또는 No인 문제
- 형식: "조건 C를 만족하는가?"
- 언어: L = {조건 C를 만족하는 입력들}
특징:
- 이론적 분석 용이
- 모든 문제를 변환 가능
- 본질에 집중최적화 vs 결정
최적화 문제:
"최소/최대 값은?"
→ 복잡한 답
결정 문제:
"값이 k 이하/이상인가?"
→ Yes/No
관계:
최적화 ≡ 결정
(이진 탐색으로 변환 가능)언어 표현
결정 문제 = 언어 인식
- L = {조건 만족하는 문자열}
- 문제: w ∈ L인가?
- 튜링 기계와 연결실무 활용
타당성 검사:
- 가능한가?
- 만족하는가?
제약 조건:
- 규칙 준수?
- 한계 내?🔗 다음 글에서는
[08-02] 클래스 P (Polynomial Time)
- P 클래스의 엄밀한 정의: 다항 시간 튜링 기계로 풀 수 있는 문제들
- 다항 시간의 의미: 왜 O(n^k)를 "효율적"이라고 하는가
- P 클래스 예시: 정렬, 최단 경로, 최대 유량 등
- P의 성질: 닫힘 성질과 안정성
이전 섹션: [07-06] 상각 분석
다음 글: [08-02] 클래스 P
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자