[알고리즘] Week 12: 종합 실습 및 프로젝트

Day 1: 종합 실습 - 탐색 알고리즘

• 강의 내용:
  • 이진 탐색 트리 (Binary Search Tree)
    • 삽입, 삭제, 탐색 연습
  • 깊이 우선 탐색 (DFS)와 너비 우선 탐색 (BFS)
    • 그래프 탐색 알고리즘 복습 및 연습
• 실습:
  • 이진 탐색 트리 및 그래프 탐색 알고리즘 구현 및 문제 풀이

# 이진 탐색 트리의 삽입, 삭제, 탐색 연습
class BSTNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def insert(root, key):
    if root is None:
        return BSTNode(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val, end=' ')
        inorder(root.right)

# 예제 실행
root = None
keys = [20, 8, 22, 4, 12, 10, 14]
for key in keys:
    root = insert(root, key)
inorder(root)  # 4 8 10 12 14 20 22

 

Day 2: 종합 실습 - 정렬 알고리즘

• 강의 내용:
  • 병합 정렬 (Merge Sort)
    • 병합 정렬 복습 및 연습
  • 퀵 정렬 (Quick Sort)
    • 퀵 정렬 복습 및 연습
• 실습:
  • 병합 정렬 및 퀵 정렬 알고리즘 구현 및 문제 풀이

# 병합 정렬 복습 및 연습
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

# 예제 실행
data = [38, 27, 43, 3, 9, 82, 10]
merge_sort(data)
print("병합 정렬 결과:", data)  # [3, 9, 10, 27, 38, 43, 82]

 

Day 3: 종합 실습 - 그리디 알고리즘

• 강의 내용:
  • 활동 선택 문제 (Activity Selection Problem)
    • 활동 선택 문제 복습 및 연습
  • 최소 신장 트리 (MST)
    • 크루스칼 알고리즘 및 프림 알고리즘 복습 및 연습
• 실습:
  • 활동 선택 문제 및 MST 알고리즘 구현 및 문제 풀이

# 활동 선택 문제 복습 및 연습
def activity_selection(activities):
    activities.sort(key=lambda x: x[1])
    selected_activities = [activities[0]]
    for i in range(1, len(activities)):
        if activities[i][0] >= selected_activities[-1][1]:
            selected_activities.append(activities[i])
    return selected_activities

# 예제 실행
activities = [(1, 3), (2, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
print("선택된 활동:", activity_selection(activities))  # [(1, 3), (3, 5), (5, 7), (8, 9)]

 

Day 4: 종합 실습 - 동적 프로그래밍

• 강의 내용:
  • 피보나치 수열 (Fibonacci Sequence)
    • 피보나치 수열 복습 및 연습
  • 배낭 문제 (Knapsack Problem)
    • 배낭 문제 복습 및 연습
• 실습:
  • 피보나치 수열 및 배낭 문제 알고리즘 구현 및 문제 풀이

# 배낭 문제 복습 및 연습
def knapsack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]

    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i - 1] <= w:
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]

    return K[n][W]

# 예제 실행
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print("최대 가치:", knapsack(W, wt, val, n))  # 220

 

Day 5: 종합 실습 - 최단 경로 알고리즘

• 강의 내용:
  • 다익스트라 알고리즘 (Dijkstra's Algorithm)
    • 다익스트라 알고리즘 복습 및 연습
  • 벨만-포드 알고리즘 (Bellman-Ford Algorithm)
    • 벨만-포드 알고리즘 복습 및 연습
• 실습:
  • 다익스트라 알고리즘 및 벨만-포드 알고리즘 구현 및 문제 풀이

# 다익스트라 알고리즘 복습 및 연습
import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 예제 실행
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print("다익스트라 알고리즘 결과:", dijkstra(graph, 'A'))  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

 

Day 6: 종합 실습 - 최소 스패닝 트리

• 강의 내용:
  • 크루스칼 알고리즘 (Kruskal's Algorithm)
    • 크루스칼 알고리즘 복습 및 연습
  • 프림 알고리즘 (Prim's Algorithm)
    • 프림 알고리즘 복습 및 연습
• 실습:
  • 크루스칼 알고리즘 및 프림 알고리즘 구현 및 문제 풀이

# 크루스칼 알고리즘 복습 및 연습
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        root_x = self.find(parent, x)
        root_y = self.find(parent, y)
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

    def kruskal_mst(self):
        result = []
        i = e = 0
        self.graph = sorted(self.graph, key=lambda item: item[2])
        parent = []
        rank = []

        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        while e < self.V - 1:
            u, v, w = self.graph[i]
            i += 1
            x = self.find(parent, u)
            y = self.find(parent, v)

            if x != y:
                e += 1
                result.append([u, v, w])
                self.union(parent, rank, x, y)

        return result

# 예제 실행
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
print("크루스칼 알고리즘에 의한 최소 스패닝 트리:", g.kruskal_mst())  # [(2, 3, 4), (0, 3, 5), (0, 1, 10)]

 

Day 7: 최종 프로젝트 준비

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

### 최종 프로젝트 주제 예시
1. 소셜 네트워크 분석 도구
2. 웹 크롤러 개발
3. 네비게이션 시스템 개발

### 프로젝트 요구사항 예시
1. 소셜 네트워크 분석 도구:
   - 소셜 네트워크 데이터 입력 및 저장
   - 그래프 탐색 알고리즘을 통한 사용자 연결 분석
   - 분석 결과 출력 및 시각화

### 프로젝트 설계 및 계획 예시
1. 데이터 입력 모듈 구현
2. 그래프 탐색 알고리즘 구현 (예: BFS, DFS 등)
3. 데이터 출력 및 시각화 모듈 구현

 

Day 8-9: 프로젝트 구현

• 강의 내용:
  • 프로젝트 구현
    • 데이터 입력 모듈 구현
    • 알고리즘 구현 (탐색, 정렬, 최단 경로 등)
    • 데이터 출력 및 시각화 모듈 구현
  • 중간 점검 및 피드백
    • 프로젝트 중간 점검
    • 피드백 반영 및 수정
• 실습:
  • 프로젝트 구현 진행

# 예제: 소셜 네트워크 분석 도구의 데이터 입력 및 탐색 알고리즘 구현

# 소셜 네트워크 데이터 입력 모듈
class SocialNetwork:
    def __init__(self):
        self.graph = {}

    def add_user(self, user):
        if user not in self.graph:
            self.graph[user] = []

    def add_connection(self, user1, user2):
        if user1 in self.graph and user2 in self.graph:
            self.graph[user1].append(user2)
            self.graph[user2].append(user1)

# 탐색 알고리즘 구현 (BFS 사용)
def bfs(graph, start):
    visited = set()
    queue = [start]
    result = []

    while queue:
        user = queue.pop(0)
        if user not in visited:
            visited.add(user)
            result.append(user)
            queue.extend(set(graph[user]) - visited)

    return result

# 예제 실행
sn = SocialNetwork()
sn.add_user('Alice')
sn.add_user('Bob')
sn.add_user('Charlie')
sn.add_connection('Alice', 'Bob')
sn.add_connection('Bob', 'Charlie')
print("소셜 네트워크 분석 결과 (BFS):", bfs(sn.graph, 'Alice'))  # ['Alice', 'Bob', 'Charlie']

 

Day 10-11: 프로젝트 마무리 및 발표 준비

• 강의 내용:
  • 프로젝트 마무리
    • 최종 구현 완료
    • 코드 최적화 및 문서화
  • 발표 준비
    • 프로젝트 발표 자료 준비
    • 발표 연습 및 피드백 반영
• 실습:
  • 프로젝트 구현 마무리
  • 발표 자료 준비 및 발표 연습

### 프로젝트 발표 자료 예시
1. 프로젝트 개요
2. 프로젝트 목표 및 배경
3. 구현 내용 및 방법
4. 주요 기능 시연
5. 성과 및 배운 점

 

Day 12: 최종 프로젝트 발표

• 강의 내용:
  • 최종 프로젝트 발표
    • 프로젝트 발표 및 시연
    • 질의응답 및 피드백
• 실습:
  • 프로젝트 발표 및 시연
  • 피드백 수렴 및 개선점 논의

### 발표 세션
1. 프로젝트 발표 (10분)
2. 시연 및 데모 (10분)
3. 질의응답 (10분)
4. 피드백 및 개선점 논의 (10분)

 

이 강의는 파이썬의 다양한 알고리즘과 데이터 구조를 종합적으로 복습하고 실습하며, 최종 프로젝트를 통해 실무 적용 능력을 기르는 것을 목표로 합니다. 각 강의는 이론과 실습을 포함하며, 프로젝트를 통해 배운 내용을 종합적으로 활용합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!