지수 시간(Exponential Time) 복잡도

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

n = 10일 때:
- O(n^2) = 100 연산
- O(2^n) = 1,024 연산

n = 20일 때:
- O(n^2) = 400 연산
- O(2^n) = 1,048,576 연산

n = 50일 때:
- O(n^2) = 2,500 연산
- O(2^n) = 1,125,899,906,842,624 연산

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def cyk_parsing(grammar, sentence):
    """
    CYK 알고리즘을 사용한 구문 분석
    grammar: CNF(Chomsky Normal Form) 형태의 문법
    sentence: 공백으로 구분된 단어 문자열
    """
    words = sentence.split()
    n = len(words)
    
    # 동적 프로그래밍 테이블 초기화
    table = [[set() for _ in range(n+1)] for _ in range(n+1)]
    
    # 기저 사례: 각 단어에 해당하는 비단말 기호 채우기
    for i in range(n):
        for rule in grammar:
            if rule[0] == words[i]:
                table[i][1].add(rule[1])
    
    # 상향식으로 파싱 테이블 채우기
    for length in range(2, n+1):
        for start in range(n-length+1):
            for partition in range(1, length):
                for rule in grammar:
                    if len(rule) == 3:  # 이진 규칙 (A -> BC)
                        B, C = rule[1], rule[2]
                        if B in table[start][partition] and C in table[start+partition][length-partition]:
                            table[start][length].add(rule[0])
    
    # 전체 문장이 시작 기호로부터 유도 가능한지 확인
    return 'S' in table[0][n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

def ford_fulkerson(graph, source, sink):
    """
    Ford-Fulkerson 알고리즘을 사용한 최대 흐름 계산
    graph: 용량 그래프 (인접 리스트 형태)
    source: 소스 노드
    sink: 싱크 노드
    """
    # 잔여 그래프 초기화
    residual_graph = {u: {v: capacity for v, capacity in neighbors.items()}
                     for u, neighbors in graph.items()}
    
    def find_path(current, path, visited, min_capacity):
        """BFS를 사용하여 소스에서 싱크까지의 경로 찾기"""
        if current == sink:
            return path, min_capacity
        
        visited.add(current)
        
        for neighbor, capacity in residual_graph[current].items():
            if neighbor not in visited and capacity > 0:
                new_min_capacity = min(min_capacity, capacity)
                result = find_path(neighbor, path + [neighbor], visited, new_min_capacity)
                
                if result[0]:  # 경로를 찾았으면
                    return result
        
        return [], 0  # 경로를 찾지 못함
    
    max_flow = 0
    
    while True:
        path, path_capacity = find_path(source, [source], set(), float('inf'))
        
        if not path:  # 더 이상 경로가 없으면 종료
            break
        
        max_flow += path_capacity
        
        # 잔여 그래프 업데이트
        for i in range(len(path) - 1):
            u, v = path[i], path[i+1]
            residual_graph[u][v] -= path_capacity
            if v not in residual_graph:
                residual_graph[v] = {}
            if u not in residual_graph[v]:
                residual_graph[v][u] = 0
            residual_graph[v][u] += path_capacity
    
    return max_flow

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

class Ray:
    def __init__(self, origin, direction):
        self.origin = origin
        self.direction = direction.normalize()

class Sphere:
    def __init__(self, center, radius, color):
        self.center = center
        self.radius = radius
        self.color = color
    
    def intersect(self, ray):
        """광선과 구의 교차점 찾기"""
        oc = ray.origin - self.center
        a = ray.direction.dot(ray.direction)
        b = 2.0 * oc.dot(ray.direction)
        c = oc.dot(oc) - self.radius * self.radius
        discriminant = b * b - 4 * a * c
        
        if discriminant < 0:
            return None  # 교차점 없음
        
        t = (-b - math.sqrt(discriminant)) / (2.0 * a)
        if t <= 0:
            return None  # 광선 뒤에 있음
        
        return t  # 교차점까지의 거리

def trace_ray(ray, objects, depth=0, max_depth=3):
    """재귀적 광선 추적"""
    if depth > max_depth:
        return Color(0, 0, 0)  # 최대 재귀 깊이 도달
    
    closest_t = float('inf')
    closest_object = None
    
    # 가장 가까운 교차점 찾기
    for obj in objects:
        t = obj.intersect(ray)
        if t and t < closest_t:
            closest_t = t
            closest_object = obj
    
    if not closest_object:
        return Color(0, 0, 0)  # 배경색
    
    # 교차점 계산
    hit_point = ray.origin + ray.direction * closest_t
    normal = (hit_point - closest_object.center).normalize()
    
    # 반사 광선 계산
    reflect_dir = ray.direction - normal * 2 * ray.direction.dot(normal)
    reflect_ray = Ray(hit_point + normal * 0.001, reflect_dir)  # 표면 오차 방지
    
    # 재귀적으로 반사 색상 계산
    reflect_color = trace_ray(reflect_ray, objects, depth + 1, max_depth)
    
    # 최종 색상 계산 (단순화된 버전)
    return closest_object.color * 0.8 + reflect_color * 0.2