[알고리즘] Week 9: 고급 기하 알고리즘 - 개요와 예제

Day 1: 고급 기하 알고리즘 개요

• 강의 내용:
  • 기하 알고리즘의 정의 및 중요성
    • 기하 알고리즘이란 무엇인가?
    • 기하 알고리즘의 응용 분야 (컴퓨터 그래픽스, 로봇 공학, GIS 등)
  • 기하 알고리즘의 기본 개념
    • 점, 선분, 다각형 등의 기본 요소
    • 벡터와 교차 곱 (Cross Product), 내적 (Dot Product)
• 실습:
  • 기본 기하 연산 예제 (점, 선분, 벡터 등)

import math

# 두 점 사이의 거리 계산
def distance(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

# 벡터의 내적 계산
def dot_product(v1, v2):
    return v1[0] * v2[0] + v1[1] * v2[1]

# 벡터의 교차 곱 계산
def cross_product(v1, v2):
    return v1[0] * v2[1] - v1[1] * v2[0]

# 예제 실행
p1 = (1, 2)
p2 = (4, 6)
v1 = (1, 0)
v2 = (0, 1)

print("두 점 사이의 거리:", distance(p1, p2))  # 5.0
print("벡터의 내적:", dot_product(v1, v2))  # 0
print("벡터의 교차 곱:", cross_product(v1, v2))  # 1

 

Day 2: 선분 교차 판정 (Line Segment Intersection)

• 강의 내용:
  • 선분 교차 판정의 개념
    • 선분 교차 판정이란 무엇인가?
    • 두 선분이 교차하는지 판정하는 방법
  • 기본 선분 교차 판정 알고리즘
    • 두 선분의 교차 여부를 결정하는 수학적 방법
  • 시간 복잡도 분석
    • 시간 복잡도: O(1)
• 실습:
  • 파이썬을 사용한 선분 교차 판정 구현 및 예제

# 선분 교차 판정 구현
def on_segment(p, q, r):
    if q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1]):
        return True
    return False

def orientation(p, q, r):
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0
    return 1 if val > 0 else 2

def do_intersect(p1, q1, p2, q2):
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    if o1 != o2 and o3 != o4:
        return True

    if o1 == 0 and on_segment(p1, p2, q1):
        return True

    if o2 == 0 and on_segment(p1, q2, q1):
        return True

    if o3 == 0 and on_segment(p2, p1, q2):
        return True

    if o4 == 0 and on_segment(p2, q1, q2):
        return True

    return False

# 예제 실행
p1 = (1, 1)
q1 = (10, 1)
p2 = (1, 2)
q2 = (10, 2)
print("선분 교차 여부:", do_intersect(p1, q1, p2, q2))  # False

p1 = (10, 0)
q1 = (0, 10)
p2 = (0, 0)
q2 = (10, 10)
print("선분 교차 여부:", do_intersect(p1, q1, p2, q2))  # True

 

Day 3: 볼록 껍질 (Convex Hull)

• 강의 내용:
  • 볼록 껍질의 개념
    • 볼록 껍질이란 무엇인가?
    • 2D 평면에서의 볼록 껍질
  • 볼록 껍질 알고리즘
    • 그레이엄 스캔 (Graham's Scan) 알고리즘
    • 자비스의 행진 (Jarvis's March) 알고리즘
  • 시간 복잡도 분석
    • 그레이엄 스캔: O(n log n)
    • 자비스의 행진: O(nh) (h는 볼록 껍질의 점의 수)
• 실습:
  • 파이썬을 사용한 그레이엄 스캔 구현 및 예제

# 그레이엄 스캔 알고리즘 구현
def graham_scan(points):
    points = sorted(points)
    lower = []
    for p in points:
        while len(lower) >= 2 and cross_product((lower[-1][0] - lower[-2][0], lower[-1][1] - lower[-2][1]), (p[0] - lower[-1][0], p[1] - lower[-1][1])) <= 0:
            lower.pop()
        lower.append(p)

    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross_product((upper[-1][0] - upper[-2][0], upper[-1][1] - upper[-2][1]), (p[0] - upper[-1][0], p[1] - upper[-1][1])) <= 0:
            upper.pop()
        upper.append(p)

    return lower[:-1] + upper[:-1]

# 예제 실행
points = [(0, 0), (1, 1), (2, 2), (3, 3), (0, 3), (3, 0), (1, 2), (2, 1)]
hull = graham_scan(points)
print("볼록 껍질의 점들:", hull)  # [(0, 0), (3, 0), (3, 3), (0, 3)]

 

Day 4: 최근접 쌍 문제 (Closest Pair Problem)

• 강의 내용:
  • 최근접 쌍 문제의 개념
    • 최근접 쌍 문제란 무엇인가?
    • 2D 평면에서의 최근접 쌍
  • 최근접 쌍 알고리즘
    • 분할 정복 알고리즘
  • 시간 복잡도 분석
    • 분할 정복: O(n log n)
• 실습:
  • 파이썬을 사용한 최근접 쌍 알고리즘 구현 및 예제

# 최근접 쌍 알고리즘 구현
def closest_pair(points):
    def dist(p1, p2):
        return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

    def brute_force(points):
        min_dist = float('inf')
        pair = (None, None)
        for i in range(len(points)):
            for j in range(i + 1, len(points)):
                if dist(points[i], points[j]) < min_dist:
                    min_dist = dist(points[i], points[j])
                    pair = (points[i], points[j])
        return pair, min_dist

    def closest_split_pair(px, py, delta, best_pair):
        ln_x = len(px)
        mx_x = px[ln_x // 2][0]
        s_y = [x for x in py if mx_x - delta <= x[0] <= mx_x + delta]
        best = delta
        ln_y = len(s_y)
        for i in range(ln_y - 1):
            for j in range(i + 1, min(i + 7, ln_y)):
                p, q = s_y[i], s_y[j]
                if dist(p, q) < best:
                    best_pair = p, q
                    best = dist(p, q)
        return best_pair, best

    def closest_pair_rec(px, py):
        if len(px) <= 3:
            return brute_force(px)
        mid = len(px) // 2
        Qx = px[:mid]
        Rx = px[mid:]
        midpoint = px[mid][0]
        Qy = list(filter(lambda x: x[0] <= midpoint, py))
        Ry = list(filter(lambda x: x[0] > midpoint, py))
        (p1, q1), dist1 = closest_pair_rec(Qx, Qy)
        (p2, q2), dist2 = closest_pair_rec(Rx, Ry)
        if dist1 <= dist2:
            d = dist1
            mn = (p1, q1)
        else:
            d = dist2
            mn = (p2, q2)
        (p3, q3), dist3 = closest_split_pair(px, py, d, mn)
        if d <= dist3:
            return mn, d
        else:
            return (p3, q3), dist3

    px = sorted(points, key=lambda x: x[0])
    py = sorted(points, key=lambda x: x[1])
    return closest_pair_rec(px, py)

# 예제 실행
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
pair, min_dist = closest_pair(points)
print("최근접 쌍:", pair)
print("최소 거리:", min_dist)

 

Day 5: 고급 기하 알고리즘 종합 연습

• 강의 내용:
  • 종합 연습 문제 풀이
    • 선분 교차 판정, 볼록 껍질, 최근접 쌍 문제 해결
  • 고급 기하 알고리즘의 응용
    • 다양한 실생활 문제에서의 응용 사례
• 실습:
  • 종합 연습 문제 해결 및 결과 분석

### 종합 연습 문제 예시
1. 주어진 선분들이 교차하는지 판정하세요.
2. 주어진 점들로부터 볼록 껍질을 찾으세요.
3. 주어진 점들로부터 최근접 쌍을 찾으세요.

 

Day 6: 프로젝트 준비

• 강의 내용:
  • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 주제 및 요구사항 확정
    • 프로젝트 설계 및 계획 수립
  • 프로젝트 구현 준비
    • 데이터 구조 및 알고리즘 설계
    • 프로젝트 팀 구성 및 역할 분담
• 실습:
  • 프로젝트 주제 및 요구사항 분석
  • 프로젝트 설계 및 계획 수립

### 프로젝트 주제 예시
1. 대규모 기하 데이터 분석 도구 개발
2. 실시간 지도 데이터 처리 시스템

### 프로젝트 요구사항 예시
1. 대규모 기하 데이터 분석 도구:
   - 대규모 기하 데이터셋 입력 및 저장
   - 고급 기하 알고리즘을 통한 데이터 분석
   - 분석 결과 출력 및 성능 분석

### 프로젝트 설계 및 계획 예시
1. 데이터 입력 모듈 구현
2. 고급 기하 알고리즘 구현 (선분 교차 판정, 볼록 껍질, 최근접 쌍 등)
3. 데이터 출력 및 성능 분석 모듈 구현

 

이 강의는 파이썬의 고급 기하 알고리즘, 특히 선분 교차 판정, 볼록 껍질, 최근접 쌍 문제의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!