[알고리즘] Week 3: 기하학적 동적 프로그래밍과 문자열 관련 동적 프로그래밍

Day 1: 기하학적 동적 프로그래밍 소개

• 강의 내용:
  • 기하학적 동적 프로그래밍의 개념
    • 기하학적 문제를 해결하기 위한 동적 프로그래밍의 응용
    • 기하학적 문제의 특성 및 응용 사례
  • 기하학적 동적 프로그래밍의 기본 원리
    • 문제 분할 및 점진적 접근
  • 시간 복잡도 분석
    • 기하학적 동적 프로그래밍의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 간단한 기하학적 동적 프로그래밍 예제

# 예제: 다각형의 최소 삼각분할 (Minimum Triangulation of Polygon)
def min_triangulation(points):
    n = len(points)
    dp = [[0] * n for _ in range(n)]

    def cost(i, j, k):
        return abs(points[i][0] * points[j][1] + points[j][0] * points[k][1] + points[k][0] * points[i][1]
                   - points[i][1] * points[j][0] - points[j][1] * points[k][0] - points[k][1] * points[i][0])

    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            dp[i][j] = float('inf')
            for k in range(i + 1, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cost(i, j, k))

    return dp[0][n - 1]

# 예제 실행
points = [(0, 0), (1, 0), (1, 1), (0, 1)]
print("다각형의 최소 삼각분할 비용:", min_triangulation(points))  # Output: 2.0

 

Day 2: 기하학적 동적 프로그래밍 심화

• 강의 내용:
  • 기하학적 문제의 심화 예제
    • 점집합에서의 최대 비독립 집합 (Maximum Independent Set)
  • 기하학적 동적 프로그래밍의 고급 기법
    • 분할 정복을 통한 효율성 향상
    • 문제의 특성에 따른 최적화 기법
  • 시간 복잡도 분석
    • 고급 기법의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 기하학적 동적 프로그래밍 심화 예제

# 예제: 점집합에서의 최대 비독립 집합 (Maximum Independent Set of Points)
def max_independent_set(points):
    points.sort(key=lambda x: x[1])
    n = len(points)
    dp = [0] * n

    for i in range(n):
        dp[i] = 1
        for j in range(i):
            if points[j][0] < points[i][0] and points[j][1] < points[i][1]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

# 예제 실행
points = [(0, 1), (1, 2), (2, 3), (3, 0), (4, 5)]
print("점집합에서의 최대 비독립 집합 크기:", max_independent_set(points))  # Output: 4

 

Day 3: 문자열 관련 동적 프로그래밍 소개

• 강의 내용:
  • 문자열 관련 동적 프로그래밍의 개념
    • 문자열 문제를 해결하기 위한 동적 프로그래밍의 응용
    • 문자열 문제의 특성 및 응용 사례
  • 문자열 관련 동적 프로그래밍의 기본 원리
    • 문제 분할 및 점진적 접근
  • 시간 복잡도 분석
    • 문자열 관련 동적 프로그래밍의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 간단한 문자열 동적 프로그래밍 예제

# 예제: 최장 공통 부분 수열 (Longest Common Subsequence, LCS)
def lcs(X, Y):
    m = len(X)
    n = len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

# 예제 실행
X = "AGGTAB"
Y = "GXTXAYB"
print("최장 공통 부분 수열의 길이:", lcs(X, Y))  # Output: 4

 

Day 4: 문자열 관련 동적 프로그래밍 심화

• 강의 내용:
  • 문자열 문제의 심화 예제
    • 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS)
  • 문자열 관련 동적 프로그래밍의 고급 기법
    • 메모이제이션 및 반복적 접근
    • 문제의 특성에 따른 최적화 기법
  • 시간 복잡도 분석
    • 고급 기법의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 문자열 동적 프로그래밍 심화 예제

# 예제: 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS)
def lis(arr):
    n = len(arr)
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j] and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1

    return max(dp)

# 예제 실행
arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print("최장 증가 부분 수열의 길이:", lis(arr))  # Output: 6

 

Day 5: 고급 동적 프로그래밍 종합 연습

• 강의 내용:
  • 종합 연습 문제 풀이
    • 기하학적 동적 프로그래밍 및 문자열 관련 동적 프로그래밍 문제 해결
  • 고급 동적 프로그래밍의 응용
    • 다양한 실생활 문제에서의 응용 사례
• 실습:
  • 종합 연습 문제 해결 및 결과 분석

### 종합 연습 문제 예시
1. 주어진 다각형에서 최소 삼각분할을 찾으세요.
2. 주어진 점집합에서 최대 비독립 집합을 찾으세요.
3. 주어진 두 문자열의 최장 공통 부분 수열을 찾으세요.
4. 주어진 배열의 최장 증가 부분 수열을 찾으세요.

 

Day 6: 프로젝트 준비

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

### 프로젝트 주제 예시
1. 대규모 기하학적 문제 해결 시스템 개발
2. 실시간 문자열 분석 시스템

### 프로젝트 요구사항 예시
1. 대규모 기하학적 문제 해결 시스템:
   - 대규모 기하학적 데이터셋 입력 및 저장
   - 동적 프로그래밍을 통한 문제 해결
   - 최적화 결과 출력 및 성능 분석

2. 실시간 문자열 분석 시스템:
   - 문자열 데이터 입력 및 저장
   - 동적 프로그래밍을 통한 문자열 분석
   - 분석 결과 출력 및 성능 분석

### 프로젝트 설계 및 계획 예시
1. 데이터 입력 모듈 구현
2. 동적 프로그래밍 알고리즘 구현 (기하학적 및 문자열 관련)
3. 데이터 출력 및 성능 분석 모듈 구현

 

이 강의는 파이썬의 고급 동적 프로그래밍, 특히 기하학적 동적 프로그래밍과 문자열 관련 동적 프로그래밍의 기본 개념과 구현을 익히는 것을 목표로합니다.