🔗 Algorithm/Tip

[Python] 다이나믹 프로그래밍 (DP)

다이나믹 프로그래밍의 핵심은 점화식과 memoization 이다. DP는 주로 bottom-up 방식을 사용하지만, top-down으로도 구현 가능하다. top-down은 재귀+memoization을 통해 구현한다. 대표적인 DP문제로, 피보나치 수열이 있다. https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 📍 피보나치 수의 점화식은 f(n) = f(n-1) + f(n-2) (n>=2) 📌 Bottom-Up ..

[Python] 최소힙(MIN heap) / 최대힙(MAX heap)

힙은 자료구조 트리를 사용하여 구현한다. 트리 중에서도 완전 이진트리이다. 최대 트리는 항상 부모가 자식보다 값이 크다. 최소 트리는 항상 부모가 자식보다 값이 작다. (자식끼리는 상관X) python으로 어떻게 구현할 것인가? 고민할 필요 없이 module을 쓰도록 하겠다. 최소(Min) heap python은 기본적으로 최소 heap을 구현할 수 있는 모듈을 제공한다. import heapq heap으로 선언하는 것은 아니고, 일반적인 배열을 heap으로 만들 수 있다. 예를 들어 정렬되지 않은 arr 배열을 heapify로 정렬할 수 있다. heapify(정렬할리스트) import heapq arr = [1,5,3,6,2] heapq.heapify(arr) print(arr) # [1,2,3,6,5..

[Algorithm] LCA 알고리즘

LCA는 "Lowest Common Ancestor" 가장 가까운 공통 조상을 찾는 알고리즘이다. 백준 3584번을 풀면서 이해해보장 www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 해당 트리에서 3번과 2번의 가장 가까운 공통 조상은 10번이라는 것을 바로 알 수 있다. 그렇다면 a와b가 주어졌을 때 알고리즘으로 최소 공통 조상을 찾아보자. Rule 📌 a의 조상을 모두 찾아 리스트로 만든다. 📌 b의 조..

[Algorithm] Dijkstra 다익스트라 최단 경로 알고리즘

다익스트라 알고리즘은 A에서 B까지의 최단 경로를 찾고자 할 때 사용한다. 먼저, 알고리즘을 직관적으로 살펴보자 다음과 같은 그래프에서 A->C로 가고자 할 때 최단 경로를 구해보자. 우선 출발지로부터 인접한 노드들과의 거리를 갱신한다. (빨간색) 그 다음 노드로 이동한다. 해당 노드에서 인접한 노드들 중에 방문하지 않은 노드들 과의 거리를 갱신한다. 다음과 같이 D의 거리가 5에서 3으로 갱신 되었다. (최단 거리) C가 5에서 4로 갱신되었다. 현재 방문한 노드가 도착지라면 알고리즘을 종료한다. 그림처럼 A->C의 최단경로는 4가 된다. 위와 같이 동작하는 알고리즘이 다익스트라 알고리즘이다. 📌 Rule 1. 출발 노드로부터 인접한 노드들 사이의 거리를 갱신한다. 2. 다음 노드로 방문하여 인접 노드..

[Algorithm] 너비 우선 탐색 BFS / 깊이 우선 탐색 DFS

개인적으로 어려워 하는 알고리즘,, 알고리즘 BFS는 FIFO를 원칙으로 하는 Queue로 구현한다. 탐색을 시작하는 첫 노드(root)를 queue에 넣고 탐색을 시작한다. A. queue에서 노드를 꺼낸다. B. 꺼낸 노드와 연결된 노드 중 방문하지 않은 노드를 방문하고 queue에 넣는다. queue에 노드가 없어질 때 까지 AB반복 구현 def bfs(graph, root): visit = list() queue = [root] #AB반복 while queue: temp = queue.pop(0) if temp not in visit: print(temp) visit.append(temp) queue.extend(graph[temp]) 알고리즘 DFS는 LIFO를 원칙으로 하는 Stack으로 구현..