소피it블로그

자료 출처: https://youtu.be/acqm9mM1P6o 동빈북을 사두고 생각보다 어려워서 많이 못 봤는데, 이 강의 시리즈를 보다보니 이해가 쉽게 가고 재밌어서 대강 쭉 봤다. 요즘 블로그에 정리하는 내용들도 강의 요약본이나 마찬가지인데, 어려운 알고리즘들은 계속 읽어보며 완전히 이해가 될 때까지 못 넘기겠어서 하나하나 코멘트를 다는 중. 투머치이긴 하지만 내가 이해하기 위한 것이기 때문에 그냥 적으려 한다. 1. 최단 경로 알고리즘 개요 한 지점에서 다른 한 지점까지 한 지점에서 다른 모든 지점까지: 다익스트라 알고리즘 모든 지점에서 다른 모든 지점까지: 플로이드 워셜 알고리즘 이 때 각 지점은 노드로, 지점 간을 연결하는 도로는 간선으로 표현한다. 2. 다익스트라 최단 경로 알고리즘 특정 노..

자료 출처: https://youtu.be/5Lu34WIx2Us 이전까지는 다이나믹 프로그래밍이 뭔지 아예 모르고 이름만 많이 들어봤었는데, 이 강의 덕에 개념이 잡혔다. 문제를 아주 많이 풀어봐야 할 것 같다. 1. 다이나믹 프로그래밍 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법으로, 이미 계산된 결과는 별도의 메모리 영역에 저장한다. 조건 최적 부분 구조 (Optimal Substructure): 큰 문제를 작은 문제로 나눌 수 있는 경우. 즉, 작은 문제의 답을 모아 큰 문제를 해결할 수 있음 중복되는 부분 문제 (Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결해야 함 다이나믹 프로그..

자료 출처: https://youtu.be/i5yHkP1jQmo 1. 트리 계층적인 구조를 표현할 때 사용할 수 있는 자료구조로, 다음과 같은 요소를 갖는다. 트리의 크기가 n일 때 전체 간선의 수는 n-1 개이다. 루트 노드 (root node) 단말 노드 (leaf node) 크기 (size): 트리에 포함된 모든 노드의 개수 깊이 (depth): 루트 노드부터의 거리 높이 (height): 깊이 중 최댓값 차수 (degree): 각 노드의 자식방향의 간선의 개수 2. 이진 탐색 트리 (Binary Search Tree) 이진 탐색을 쉽게 할 수 있게 해주는 트리로, 다음을 만족한다. 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 데이터의 조회 과정은 다음과 같다. 루트 노드부터 방문하여 탐색을..

자료 출처: https://youtu.be/AjFlp951nz0 1. 우선순위 큐 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 단순히 리스트를 이용하여 구현하는 방식: 삽입시 O(1), 삭제시 O(N)의 시간복잡도 힙(heap) 자료구조를 이용하여 구현하는 방식: 삽입, 삭제시 각각 O(logN)의 시간복잡도 2. 힙 (Heap) 완전 이진 트리의 일종인 자료구조로, 항상 루트 노드를 먼저 제거한다. 최소 힙 (Min Heap) 루트 노드가 가장 작은 값을 가짐 값이 작은 데이터가 우선적으로 제거됨 따라서 최소 힙에 넣었다 빼면 오름차순으로 정렬됨(작은 데이터부터 제거되므로) 최대 힙 (Max Heap) 루트 노드가 가장 큰 값을 가짐 값이 큰 데이터가 우선적으로 제거됨 따라서 최대 힙에 ..

자료 출처: https://youtu.be/94RC-DsGMLo 1. 이진탐색이란? 정렬되어 있는 리스트(배열)에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방식으로 동작하는 알고리즘 시작점, 끝점, 중간점을 이용한다. 시간 복잡도: O(logN) 재귀 또는 반복문을 이용하여 구현할 수 있다. 이하는 재귀를 이용하여 푸는 법. # 재귀 방식으로 구현 def binary_search(arr, target, start, end): if start > end: return None mid = (start + end) // 2 if arr[mid] == target: return mid elif arr[mid] < target: return binary_search(arr, target, mid + 1, ..

1. BFS: Breadth-First Search 너비 우선 탐색 BFS에서는 큐를 활용한다. 너비 우선 탐색이라는 개념과 FIFO의 특징을 생각해 보면 쉽게 이해할 수 있다. 큐를 사용하여 큐에 먼저 들어간 노드들을 먼저 팝해주는 것. from collections import deque def bfs(graph, node, visited): queue = deque([node]) # 첫 번째 노드로 큐를 만들어줌 visited[node] = True # 해당 노드 방문 기록 while queue: # 큐에 요소가 남아있는 동안 n = queue.popleft() # 큐의 앞에서 요소 빼줌 print(n, end = " ") # 해당 요소 출력 for i in graph[n]: # 해당 요소의 자식 ..