curiosity killed the cat

참고하면 좋은 이전 글: [알고리즘] 다이나믹 프로그래밍 (개념) + LeetCode 509 플로이드 워셜 알고리즘 (Floyd-Warshall algorithm)은 directed graph (유향 그래프: 간선에 방향성이 있는 그래프)에서 노드 i에서 노드 j로 가는 최단 경로를 찾는 알고리리즘이다. 최단 경로를 찾는다는 점에서는 다익스트라 알고리즘과 비슷하지만, 다익스트라 알고리즘은 한 노드에서 출발해서 다른 노드까지 가는 최단 경로를 찾는 방면, 플로이드 워셜 알고리즘은 모든 쌍 i,j에 대해서 최단 거리를 찾는다. 플로이드 와셜 알고리즘을 사용하기 위해서 다음 조건을 만족해야 한다: 간선의 가중치(편의상 '거리'라고도 표현하겠습니다)는 양수일 수도 있고 음수일 수도 있다 Negative cycl..

크루스칼 알고리즘은 (connected, undirected, edge 에 weight가 있는) 그래프에서 최단 신장 트리 (minimal spanning tree)를 구하는 알고리즘이다. 신장 트리란 그래프의 모든 노드들을 (사이클이 없이) 연결하는 트리다 노드가 N개 있으면 N-1 간선(edge)으로 이뤄진다 하나의 그래프에 여러개의 신장 트리가 있을 수 있다 최단 신장 트리는 트리의 edge weight들을 모두 더했을 때 최소가 되는 신장 트리다 크루스칼 알고리즘은 이전 글에서 설명한 유니온 파인드 알고리즘을 기반으로 구성된다. 우선 간선들을 오름차순으로 정렬을 한다. 그리고 가장 edge weight가 작은 간선들을 차례차례 트리에 추가하고, 신장 트리가 완성되면 끝난다. 알고리즘의 시간 복잡도..

다이나믹 프로그래밍이란 어떠한 문제를 소문제들로 나누고, 소문제들을 풀어서 결과 값을 저장하고, 원래 문제를 풀 때 소문제의 결괏값을 사용하는 방법론을 말한다. 다이나믹 프로그래밍으로 풀 수 있는 대표적인 문제가 피보나치 수열을 계산하는 문제다 (풀이를 이해하는 것도 쉬운 편이다; https://leetcode.com/problems/fibonacci-number/). 피보나치 수열 \( F_0 = 0, F_1 = 1, F_{n}=F_{n-1}+F_{n-2}\)로 정의되는 수열이다 (0, 1, 1, 2, 3, 5, 8, 13...). 우선 약간 무식하게 제귀함수로 풀어보자: def fib(n): if n int: if n int: self.Fib[0] = 0 self.Fib[1] = 1 for i in ..

배열에서 어떤 구간의 시작점과 끝점을 정하고, 시작점과 끝점을 기준으로 어떠한 문제를 푸는 방법을 투 포인터라고 부른다. 문제를 보면서 이해하는 것이 쉽다. 예제) Longest Palindromic Substring - LeetCode 가장 긴 팰린드롬 부분 문자열을 출력하는 문제. 팰린드롬은 앞으로 읽어도 뒤로 읽어도 같은 문자열을 말한다. 예를 들어 "aba"를 거꾸로 읽어도 "aba"이기 때문에 팰린드롬에 해당한다. 여기서는 가장 긴 팰린드롬 부분 문자열을 찾는 것이 문제이기 때문에 "babad"라는 문자열이 있을 때 "bab", 또는 "aba"를 찾는 문제다 (둘중 하나만 찾으면 된다). "cbbd" 같은 경우 답은 "bb"가 된다. 풀이) 팰린드롬은 좌우 대칭이기 때문에, 팰린드롬의 중심점을 ..

알고리즘 (1차원) 구간 합 (prefix sum)은 숫자 배열이 \( [x_1,x_2,...,x_n] \)이 있을 때 다음과 같이 구간의 합을 구해서 새로운 숫자 배열 \([y_1,y_2,...,y_n]\)을 만들어서 사용하는 방법이다. 여기서 y들은 다음과 같이 정의된다: \(y_1=x_1\) \(y_2=x_1+x_2\) \(y_3=x_1+x_2+x_3\) \(y_n=x_1+x_2+x_3+...+x_n\) 실제로 계산할 때는 \(y_0=0\)으로 두고 다음과 같이 계산하는 것이 편하다 \(y_i = x_i+y_{i-1}, \quad i=1,2...,n\) \( y_0=0, y_1=x_1+0=x_1, y_2=y_1+x_2=x_2+x_1,...\)인 것을 확인할 수 있다. 이렇게 계산하는 과정의 계산 복..

이진 탐색은 정렬된 배열에서 특정 원소를 찾는 알고리즘이다. 동작 원리는 간단하다. 편의상 오른쪽 원소가 크거나 같다고 가정하자. 배열의 중간에 위치한 값이 찾고자 하는 값보다 큰지 작은지 비교. 중간에 있는 값이 더 크면 찾고있는 원소는 중간값의 왼쪽에 있을 것이다. 중간값의 왼쪽에 있는 원소로 배열을 만들어서 다시 1번을 시행한다. 중간에 있는 값이 더 작으면 중간값의 오른쪽에 있는 원소들로 다시 1번을 시행한다. Pseudo code로 정리하면 다음과 같다 (pseudo code는 모두 위키피디아에서 가져왔다): # A = [A0, A1, A2, ..., An-1] # A0 int: len_nums = len(nums) L=0 R=len_nums-1 min_val = L while L < R: m ..

다익스트라 (Dijkstra) 알고리즘은 weighted graph에서 최단 경로를 찾는 알고리즘이다. weight가 양수일 때만 사용 가능하다. 여러 버전이 있는데 우선 위키피디아에 가장 먼저 뜨는 알고리즘을 살펴보자. weighted graph와 출발 노드(node)가 주어졌다고 하자. 처음에는 현제 노드가 출발 노드와 같고, 출발 노드에서 다른 모든 노드까지 거리를 무한대로 초기화한다. 단 출발 노드에서 출발 노드까지 거리는 0으로 설정한다. 다익스트라 알고리즘은 다음과 같다: 방문하지 않은 노드 중 시작점과 거리가 가장 짧은 노드를 현재 노드로 설정 인근 노드까지 출발 점에서부터 거리를 계산한다 이렇게 계산한 거리가 이전에 구했던 출발점부터의 거리보다 더 작다면 새로 계산한 값으로 업데이트한다 참..

BFS (너비 우선 탐색) 와 비슷하게 tree/graph 구조에서 조건을 만족하는 node를 찾을 때 사용하는 알고리즘이다 (2023.03.05 - [분류 전체보기] - [알고리즘] 너비 우선 탐색 (+LeetCode 733)). DFS (Depth First Search, 깊이 우선 탐색) 는 말 그대로 깊이부터 탐색하는 알고리즘. 위에 tree를 보면 이해하기 쉽다. 우선 1번 노드부터 출발해서 다음과 같은 순서로 탐색을 한다: 1 -> 2 -> 5 -> 6 -> 3 -> 4 -> 7 보다시피 깊이 방향으로 먼저 끝까지 탐색을 하는 방식으로 탐색을 하기 때문에 깊이 우선 탐색이다. 이러한 알고리즘은 recursive (재귀) 하게 구현할 수도 있고 stack을 사용해서 구현할 수도 있다. 우선 re..

BFS (breadth first search, 너비 우선 탐색)는 tree 혹은 graph 형태의 data structure에서 일종의 조건을 만족하는 node를 찾는 알고리즘. Tree: Tree는 node(동그라미)와 edge(선)로 이뤄져 있다. Root node (1번 동그라미)에서부터 edge들로 가지를 쳐가는 형태로 데이터가 정렬되어 있다. 각 node는 여러 개의 child node (그림에서 더 밑쪽에 있는 node)와 연결될 수 있지만 단 한 개의 parent node와 연결될 수 있다. Graph: 비슷하게 node, edge로 이뤄져 있다 두node간 edge로 연결되어 있을 수 있다. Parent, child node 개념이 없다. BFS는 말 그대로 너비 우선 탐색하는 방식인데,..