# [08-02] 클래스 P (Polynomial Time)
P 클래스는 다항 시간에 해결할 수 있는 결정 문제들의 집합으로, "효율적으로 풀 수 있는 문제"를 의미합니다.
🎯 P 클래스란 무엇인가
P의 정의
P (Polynomial Time)는 다항 시간에 해결할 수 있는 결정 문제들의 집합입니다.
알고리즘이 문제를 해결하는 데 걸리는 시간 T(n)이 입력 크기에 대한 다항식 함수(n^k)보다 크지 않은 계산 복잡도를 의미 (단, k는 상수)
직관적 이해:
P = "효율적으로 풀 수 있는 문제들"
특징:
- 답을 빠르게 계산할 수 있음
- 입력이 커져도 현실적 시간
- 실용적으로 사용 가능
예:
- 정렬: 가능! (O(n log n))
- 최단 경로: 가능! (O(E log V))
- 최대공약수: 가능! (O(log n))실생활 비유:
도서관에서 책 찾기:
P에 속하는 방법:
- 컴퓨터 검색 시스템 사용
- 분류 번호로 찾기
→ 빠르게 찾을 수 있음!
P에 속하지 않는 방법:
- 모든 책장을 다 뒤지기
- 모든 책을 하나씩 확인
→ 너무 오래 걸림형식적 정의
수학적 정의:
P = {L | L은 다항 시간 튜링 기계로 결정 가능}
풀어서:
P는 다음 조건을 만족하는 언어 L의 집합:
- 어떤 튜링 기계 M이 존재하여
- 입력 w에 대해
- O(n^k) 시간 내에 (k는 상수)
- "w ∈ L인가?"를 판단할 수 있다다항 시간이란:
다항식 형태의 시간복잡도:
T(n) = a_k × n^k + a_{k-1} × n^{k-1} + ... + a_1 × n + a_0
예:
O(1) 상수
O(log n) 로그 (다항보다 빠름, P에 포함)
O(n) 선형 ✓
O(n log n) 준선형 ✓
O(n²) 제곱 ✓
O(n³) 삼차 ✓
O(n^100) 100차 ✓ (느리지만 다항!)
O(2^n) 지수 ✗ (다항 아님!)
O(n!) 팩토리얼 ✗ (다항 아님!)
P에 속하려면:
어떤 k에 대해 O(n^k)이면 됨
(k가 크든 작든 상관없음)⏱️ 왜 다항 시간을 "효율적"이라고 하는가?
다항 vs 지수
성장률 비교:
import math
def compare_growth(n):
"""
다항 시간 vs 지수 시간 비교
n이 커질수록 차이가 극명해짐
"""
polynomial = n ** 3 # O(n³) - 다항
exponential = 2 ** n # O(2^n) - 지수
print(f"n={n:3d}: 다항={polynomial:15,d}, 지수={exponential:15,d}")
if exponential < 10**15: # 출력 가능한 범위
ratio = exponential / polynomial if polynomial > 0 else 0
print(f" 지수가 다항의 {ratio:,.0f}배")
# 비교
print("다항 시간 vs 지수 시간\n")
for n in [10, 20, 30, 40, 50]:
compare_growth(n)
print()
# 출력 예상:
# n= 10: 다항= 1,000, 지수= 1,024
# 지수가 다항의 1배
#
# n= 20: 다항= 8,000, 지수= 1,048,576
# 지수가 다항의 131배
#
# n= 30: 다항= 27,000, 지수= 1,073,741,824
# 지수가 다항의 39,768배
#
# n= 40: 다항= 64,000, 지수= 1,099,511,627,776
# 지수가 다항의 17,179,869,184배
#
# n= 50: 다항= 125,000, 지수= (천문학적 숫자)실제 시간 비교:
입력 크기 n=50 일 때
(1초에 10억 연산 가정)
다항 시간 알고리즘:
- O(n): 50 / 10^9 = 0.00000005초
- O(n²): 2,500 / 10^9 = 0.0000025초
- O(n³): 125,000 / 10^9 = 0.000125초
- O(n^10): 약 0.1초
→ 모두 1초 이내! 실용적!
지수 시간 알고리즘:
- O(2^n): 2^50 / 10^9 = 1,125,899초
= 약 13일!
- O(3^n): 3^50 / 10^9 = 약 2,000년!
→ 불가능!
결론:
다항은 느려 보여도 현실적
지수는 빠르게 불가능해짐다항 시간의 좋은 성질
1. 합성에 닫혀 있음:
알고리즘 A: O(n²)
알고리즘 B: O(n³)
A 다음에 B 실행:
총 시간 = O(n²) + O(n³) = O(n³)
→ 여전히 다항!
A를 n번 실행:
총 시간 = n × O(n²) = O(n³)
→ 여전히 다항!
중첩 실행:
A의 각 단계에서 B 호출:
총 시간 = O(n²) × O(n³) = O(n^5)
→ 여전히 다항!2. 하드웨어 독립적:
컴퓨터 A: 1초에 10억 연산
컴퓨터 B: 1초에 1조 연산 (1000배 빠름)
O(n²) 알고리즘:
- 컴퓨터 A: 1,000초
- 컴퓨터 B: 1초
→ 둘 다 현실적!
O(2^n) 알고리즘 (n=50):
- 컴퓨터 A: 13일
- 컴퓨터 B: 19분
→ 여전히 오래 걸림
다항 시간:
하드웨어 개선으로 해결 가능!
지수 시간:
하드웨어 개선으로도 한계3. 안정성:
입력 증가에 대한 민감도:
다항 O(n²):
n → 2n이면
시간 → 4배
지수 O(2^n):
n → 2n이면
시간 → (2^n)² = 2^(2n)
→ 제곱배!
예: n=20 → n=40
- 다항: 4배 (400 → 1,600)
- 지수: 1,048,576배!📊 P 클래스 예시
예시 1: 정렬 문제
def is_sortable_in_poly_time(arr):
"""
결정 문제: 배열을 다항 시간에 정렬할 수 있는가?
답: 항상 Yes!
이유: 병합 정렬이 O(n log n)
O(n log n) < O(n²) (다항)
따라서 정렬 문제 ∈ P
"""
return True # 항상 가능!
def merge_sort(arr):
"""
병합 정렬 - P 클래스 알고리즘
시간복잡도: O(n log n)
- 다항 시간!
- P에 속함
arr: 정렬할 배열
Returns: 정렬된 배열
"""
# 기저 사례: 크기 1 이하면 이미 정렬됨
if len(arr) <= 1:
return arr
# 분할: 중간 지점 찾기
mid = len(arr) // 2
# 재귀: 왼쪽과 오른쪽 각각 정렬
left = merge_sort(arr[:mid]) # O(n log n)
right = merge_sort(arr[mid:]) # O(n log n)
# 병합: 정렬된 두 배열 합치기
return merge(left, right) # O(n)
def merge(left, right):
"""
두 정렬된 배열을 하나로 병합
시간복잡도: O(n)
- n = len(left) + len(right)
"""
result = []
i = j = 0
# 양쪽 배열을 순회하며 작은 것부터 추가
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 남은 원소들 추가
result.extend(left[i:]) # .extend(left[i:]): 요소만 깔끔하게 추가, .append(left[i:]): 리스트 안에 리스트가 들어감
result.extend(right[j:])
return result
# 사용 예시
arr = [5, 2, 8, 1, 9, 3]
sorted_arr = merge_sort(arr)
print(f"정렬 결과: {sorted_arr}")
# 시간 측정
import time
import random
n = 100000
large_arr = [random.randint(1, 1000000) for _ in range(n)]
start = time.time()
merge_sort(large_arr.copy())
elapsed = time.time() - start
print(f"\nn={n:,} 정렬 시간: {elapsed:.4f}초")
print("다항 시간이므로 P에 속함!")예시 2: 최단 경로 (다익스트라)
import heapq
def shortest_path_decision(graph, start, end, max_distance):
"""
결정 문제: start에서 end까지 max_distance 이하 경로가 있는가?
해결: 다익스트라 알고리즘 사용
시간복잡도: O((V + E) log V)
- V: 정점 수, E: 간선 수
- 다항 시간!
따라서 최단 경로 문제 ∈ P
graph: 그래프 {정점: [(이웃, 가중치), ...]}
start: 시작 정점
end: 도착 정점
max_distance: 최대 허용 거리
Returns: True if 경로 있음, False otherwise
"""
# 다익스트라 알고리즘으로 최단 거리 계산
distances = dijkstra(graph, start)
# end까지 거리가 max_distance 이하인가?
if end not in distances:
return False # 경로 없음
return distances[end] <= max_distance
def dijkstra(graph, start):
"""
다익스트라 알고리즘
시간복잡도: O((V + E) log V)
- 우선순위 큐 사용
- 각 정점: log V 시간
- 각 간선: log V 시간
- 총: (V + E) log V
공간복잡도: O(V)
"""
# 초기화
distances = {vertex: float('inf') for vertex in graph}
distances[start] = 0
# 우선순위 큐: (거리, 정점)
pq = [(0, start)]
visited = set()
while pq:
# 가장 가까운 미방문 정점 선택
current_dist, current = heapq.heappop(pq)
# 이미 방문했으면 스킵
if current in visited:
continue
visited.add(current)
# 이웃 정점들 확인
for neighbor, weight in graph.get(current, []):
distance = current_dist + weight
# 더 짧은 경로 발견
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
# 사용 예시
graph = {
'A': [('B', 4), ('C', 2)],
'B': [('C', 1), ('D', 5)],
'C': [('D', 8), ('E', 10)],
'D': [('E', 2)],
'E': []
}
# 결정 문제: A에서 E까지 15 이하 경로?
result = shortest_path_decision(graph, 'A', 'E', 15)
print(f"A→E 15 이하 경로? {result}") # True (A→C→D→E = 12)
# 실제 최단 거리들
distances = dijkstra(graph, 'A')
print(f"\nA로부터의 최단 거리: {distances}")
# 다항 시간이므로 P에 속함!
print("\n최단 경로 문제 ∈ P")예시 3: 최대공약수
def gcd_decision(a, b, k):
"""
결정 문제: gcd(a, b) = k인가?
해결: 유클리드 알고리즘 사용
시간복잡도: O(log min(a, b))
- 로그는 다항보다 빠름!
따라서 GCD 문제 ∈ P
a, b: 두 정수
k: 확인할 값
Returns: True if gcd(a, b) = k
"""
return gcd(a, b) == k
def gcd(a, b):
"""
유클리드 알고리즘
시간복잡도: O(log min(a, b))
원리: gcd(a, b) = gcd(b, a % b)
왜 빠른가?
- 매 단계마다 숫자가 절반 이하로 줄어듦
- 최대 log₂(min(a, b)) 단계
예:
gcd(48, 18)
= gcd(18, 12) # 48 % 18 = 12
= gcd(12, 6) # 18 % 12 = 6
= gcd(6, 0) # 12 % 6 = 0
= 6
3번 만에 완료!
"""
while b != 0:
a, b = b, a % b
return a
# 사용 예시
print("GCD 계산:")
print(f"gcd(48, 18) = {gcd(48, 18)}")
print(f"gcd(100, 35) = {gcd(100, 35)}")
# 결정 문제
print(f"\ngcd(48, 18) = 6? {gcd_decision(48, 18, 6)}")
print(f"gcd(48, 18) = 3? {gcd_decision(48, 18, 3)}")
# 큰 수도 빠르게 계산
import time
a = 123456789012345
b = 987654321098765
start = time.time()
result = gcd(a, b)
elapsed = time.time() - start
print(f"\ngcd({a}, {b})")
print(f"= {result}")
print(f"계산 시간: {elapsed:.6f}초")
print("로그 시간이므로 P에 속함!")예시 4: 연결성 확인
def is_connected_decision(graph):
"""
결정 문제: 그래프가 연결되어 있는가?
해결: BFS 또는 DFS 사용
시간복잡도: O(V + E)
- 다항 시간!
따라서 연결성 문제 ∈ P
graph: 그래프 {정점: [이웃들]}
Returns: True if 모든 정점이 연결됨
"""
if not graph:
return True
# 임의의 시작 정점
start = next(iter(graph))
# BFS로 도달 가능한 정점들 찾기
visited = bfs(graph, start)
# 모든 정점을 방문했는가?
return len(visited) == len(graph)
def bfs(graph, start):
"""
너비 우선 탐색 (BFS)
시간복잡도: O(V + E)
- 각 정점: 1번 방문
- 각 간선: 1번 확인
graph: 그래프
start: 시작 정점
Returns: 방문한 정점들의 집합
"""
from collections import deque
visited = set()
queue = deque([start])
visited.add(start)
while queue:
# 큐에서 정점 꺼내기
current = queue.popleft()
# 이웃들 확인
for neighbor in graph.get(current, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visited
# 사용 예시
# 연결된 그래프
connected_graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
# 연결 안 된 그래프
disconnected_graph = {
'A': ['B'],
'B': ['A'],
'C': ['D'],
'D': ['C']
}
print("연결성 확인:")
print(f"그래프 1 연결됨? {is_connected_decision(connected_graph)}")
print(f"그래프 2 연결됨? {is_connected_decision(disconnected_graph)}")
# 방문한 정점들 확인
print(f"\n그래프 1에서 A부터 도달 가능: {bfs(connected_graph, 'A')}")
print(f"그래프 2에서 A부터 도달 가능: {bfs(disconnected_graph, 'A')}")
print("\nBFS는 O(V+E) 시간이므로 P에 속함!")🔒 P의 성질
닫힘 성질 (Closure Properties)
P는 다양한 연산에 대해 닫혀 있습니다.
1. 합집합 (Union):
L₁ ∈ P, L₂ ∈ P이면
L₁ ∪ L₂ ∈ P
증명:
- L₁ 판단: O(n^k₁)
- L₂ 판단: O(n^k₂)
- 합집합 판단: 둘 중 하나만 Yes면 Yes
→ max(O(n^k₁), O(n^k₂)) = O(n^max(k₁,k₂))
→ 여전히 다항!
코드:
```python
def union_decision(w, L1_decider, L2_decider):
"""
L₁ ∪ L₂ 판단
w ∈ L₁ ∪ L₂ ⟺ w ∈ L₁ OR w ∈ L₂
"""
return L1_decider(w) or L2_decider(w)
# 시간: O(n^k₁) + O(n^k₂) = O(n^max(k₁,k₂))2. 교집합 (Intersection):
L₁ ∈ P, L₂ ∈ P이면
L₁ ∩ L₂ ∈ P
증명:
- 교집합 판단: 둘 다 Yes여야 Yes
→ O(n^k₁) + O(n^k₂) = O(n^max(k₁,k₂))
→ 여전히 다항!
코드:
```python
def intersection_decision(w, L1_decider, L2_decider):
"""
L₁ ∩ L₂ 판단
w ∈ L₁ ∩ L₂ ⟺ w ∈ L₁ AND w ∈ L₂
"""
return L1_decider(w) and L2_decider(w)
# 시간: O(n^k₁) + O(n^k₂)3. 여집합 (Complement):
L ∈ P이면
L̄ (여집합) ∈ P
증명:
- L 판단: O(n^k)
- 여집합 판단: L의 반대
→ O(n^k)
→ 여전히 다항!
코드:
```python
def complement_decision(w, L_decider):
"""
L̄ 판단
w ∈ L̄ ⟺ w ∉ L
"""
return not L_decider(w)
# 시간: O(n^k)4. 연결 (Concatenation):
L₁ ∈ P, L₂ ∈ P이면
L₁ · L₂ ∈ P
L₁ · L₂ = {xy | x ∈ L₁, y ∈ L₂}
증명:
- 입력 w를 모든 가능한 위치에서 분할
- 각 분할에 대해 L₁, L₂ 판단
- 분할 개수: O(n)
- 각 판단: O(n^k₁) + O(n^k₂)
- 총: O(n) × O(n^max(k₁,k₂)) = O(n^(max(k₁,k₂)+1))
- 여전히 다항!
코드:
```python
def concatenation_decision(w, L1_decider, L2_decider):
"""
L₁ · L₂ 판단
w ∈ L₁ · L₂ ⟺ ∃i: w[:i] ∈ L₁ AND w[i:] ∈ L₂
"""
# 모든 분할 시도
for i in range(len(w) + 1):
left = w[:i]
right = w[i:]
# 왼쪽은 L₁에, 오른쪽은 L₂에?
if L1_decider(left) and L2_decider(right):
return True
return False
# 시간: O(n) × (O(n^k₁) + O(n^k₂))P = co-P
어떤 문제 L이 P에 속한다면, 그 문제의 여집합(반대 질문)인 L̄도 항상 P에 속한다는 의미로 P 클래스에서는 이 관계가 항상 성립합니다.
- co-P는 P의 여집합 (Complementary)을 의미
중요한 성질:
정리: P = co-P
의미: L ∈ P이면 L̄ ∈ P
즉: "예"라고 판단하는 것과 "아니오"라고 판단하는 것이 P에서는 똑같이 쉬움!
이유: 답을 뒤집으면 됨!예시:
# L: 짝수 집합
def is_even(n):
"""L: 짝수인가?"""
return n % 2 == 0
# P에 속함
# L̄: 홀수 집합
def is_odd(n):
"""L̄: 홀수인가? (짝수가 아닌가?)"""
return not is_even(n)
# 여전히 P에 속함!
# 둘 다 같은 시간
# → P = co-P🎯 P의 중요성
실무적 의미
문제가 P에 속한다 = "효율적으로 풀 수 있다"
결과:
1. 알고리즘 존재
- 다항 시간 알고리즘이 있음
- 찾으면 됨!
2. 확장 가능
- 입력이 커져도 OK
- 실용적 사용 가능
3. 최적화 가능
- 더 나은 알고리즘 찾기
- 상수 계수 개선
예:
정렬 ∈ P
→ 병합 정렬, 퀵 정렬 등
→ 큰 데이터도 정렬 가능
→ 실무에서 널리 사용이론적 의미
P는 복잡도 이론의 기준점
P의 역할:
1. "쉬운 문제"의 정의
2. NP와 비교 대상
3. P vs NP 문제의 한 축
질문:
"모든 NP 문제가 P인가?"
→ P = NP?
→ 최대 미스터리!💡 실무 팁
문제가 P에 속하는지 확인하기
def check_if_in_P(problem_name):
"""
문제가 P에 속하는지 확인하는 사고 과정
"""
print(f"문제: {problem_name}")
# 1단계: 다항 시간 알고리즘이 알려져 있나?
known_P_problems = {
'정렬': '병합 정렬 O(n log n)',
'최단 경로': '다익스트라 O((V+E) log V)',
'최대 유량': '에드몬즈-카프 O(VE²)',
'최대공약수': '유클리드 O(log n)',
'소수 판별': 'AKS O((log n)^6)',
'이진 탐색': 'O(log n)',
'연결성': 'BFS/DFS O(V+E)'
}
if problem_name in known_P_problems:
algo = known_P_problems[problem_name]
print(f"✓ P에 속함!")
print(f" 알고리즘: {algo}")
return True
# 2단계: 비슷한 문제가 P인가?
print("? 알려진 P 문제와 비교 필요")
print(" - 환원 가능한가?")
print(" - 유사한 기법 적용 가능한가?")
# 3단계: NP-완전으로 알려졌나?
known_NPC = {
'외판원', '배낭', '그래프 색칠',
'해밀턴 경로', '부분집합 합'
}
if problem_name in known_NPC:
print("✗ NP-완전!")
print(" P에 속할 가능성 낮음")
return False
print("? 추가 연구 필요")
return None
# 예시
check_if_in_P('정렬')
print()
check_if_in_P('외판원')🎯 핵심 정리
P 클래스
정의: P = 다항 시간에 해결 가능한 결정 문제들
형식: P = {L | L은 O(n^k) 튜링 기계로 결정 가능}
의미: "효율적으로 풀 수 있는 문제"다항 시간
포함:
O(1), O(log n), O(n), O(n log n),
O(n²), O(n³), ..., O(n^k)
제외:
O(2^n), O(n!), O(n^n)
이유:
다항은 현실적
지수는 빠르게 불가능P의 성질
닫힘 성질:
- 합집합 ✓
- 교집합 ✓
- 여집합 ✓
- 연결 ✓
특수 성질:
- P = co-P
- 합성에 안정적
- 하드웨어 독립적대표 예시
P에 속하는 문제:
- 정렬: O(n log n)
- 최단 경로: O((V+E) log V)
- 최대공약수: O(log n)
- 연결성: O(V+E)
- 소수 판별: O((log n)^6)🔗 다음 글에서는
[08-03] 클래스 NP (Nondeterministic Polynomial Time)
- NP 클래스의 정의: 다항 시간에 검증할 수 있는 문제들
- 비결정적 튜링 기계: "운이 좋으면" 빠르게 푸는 기계
- 증명자와 검증자: 답을 제시하는 사람과 확인하는 사람
- P와 NP의 관계: P ⊆ NP는 확실, P = NP는 미지수
이전 글: [08-01] 결정 문제
다음 글: [08-03] 클래스 NP
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자