[알고리즘] 추가 학습 자료 및 연습 문제

추가 학습 자료

1. 온라인 강의 및 코스
   • Coursera: "Algorithms, Part I & II" by Princeton University
     • Part I
     • Part II
   • edX: "Algorithm Design and Analysis" by MIT
     • Course Link
   • Udacity: "Data Structures and Algorithms" Nanodegree Program
     • Course Link
2. 추천 서적
   • "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
   • "Algorithm Design Manual" by Steven S. Skiena
   • "Data Structures and Algorithm Analysis in Python" by Mark Allen Weiss
3. 인터넷 리소스
   • GeeksforGeeks: Comprehensive algorithms and data structures tutorials
     • Website Link
   • LeetCode: Algorithm practice problems and competitions
     • Website Link
   • HackerRank: Coding practice and interview preparation
     • Website Link
   • CodeSignal: Coding challenges and skill assessments
     • Website Link
4. 블로그 및 기사
   • "Big-O Algorithm Complexity Cheat Sheet" by David Konsumer
     • Blog Link
   • Khan Academy: Tutorials on algorithms and data structures
     • Website Link

연습 문제

1. 탐색 알고리즘 연습 문제

• 문제 1: 이진 탐색 트리
  • 주어진 정수 배열을 이진 탐색 트리에 삽입하고, 주어진 값의 존재 여부를 확인하는 함수를 작성하세요.

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 search(root, key):
    if root is None or root.val == key:
        return root is not None
    if root.val < key:
        return search(root.right, key)
    return search(root.left, key)

# 예제 실행
root = None
keys = [20, 8, 22, 4, 12, 10, 14]
for key in keys:
    root = insert(root, key)
print("12 존재 여부:", search(root, 12))  # True
print("25 존재 여부:", search(root, 25))  # False

 

2. 정렬 알고리즘 연습 문제

• 문제 2: 병합 정렬
  • 주어진 정수 배열을 병합 정렬 알고리즘을 사용하여 정렬하세요.

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]

 

3. 그리디 알고리즘 연습 문제

• 문제 3: 활동 선택 문제
  • 활동 선택 문제를 해결하는 그리디 알고리즘을 구현하세요. 주어진 활동들의 시작 시간과 종료 시간을 고려하여 최대한 많은 활동을 선택하세요.

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)]

 

4. 동적 프로그래밍 연습 문제

• 문제 4: 배낭 문제
  • 주어진 무게와 가치의 배열 및 배낭의 최대 무게를 고려하여 최대 가치를 구하는 동적 프로그래밍 알고리즘을 구현하세요.

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

 

5. 최단 경로 알고리즘 연습 문제

• 문제 5: 다익스트라 알고리즘
  • 다익스트라 알고리즘을 사용하여 주어진 그래프에서 특정 시작점으로부터 다른 모든 정점까지의 최단 경로를 구하세요.

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}

 

6. 최소 스패닝 트리 연습 문제

• 문제 6: 프림 알고리즘
  • 프림 알고리즘을 사용하여 주어진 그래프의 최소 스패닝 트리를 구하세요.

import heapq

def prim_mst(graph, start):
    mst = []
    visited = set()
    min_heap = [(0, start)]
    
    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if u in visited:
            continue
        visited.add(u)
        mst.append((u, weight))
        
        for v, w in graph[u].items():
            if v not in visited:
                heapq.heappush(min_heap, (w, v))
    
    return mst

# 예제 실행
graph = {
    0: {1: 10, 2: 6, 3: 5},
    1: {0: 10, 3: 15},
    2: {0: 6, 3: 4},
    3: {0: 5, 1: 15, 2: 4}
}
print("프림 알고리즘에 의한 최소 스패닝 트리:", prim_mst(graph, 0))  # [(0, 0), (3, 5), (2, 4), (1, 10)]

 

이 자료들은 추가 학습과 연습을 통해 알고리즘과 데이터 구조에 대한 이해를 더욱 깊게 하는 데 도움이 될 것입니다. 필요한 경우 더 많은 자료와 연습 문제를 제공할 수 있으니 말씀해 주세요!