curiosity killed the cat

Segment tree를 이해하기 위해서 구간 합을 구하는 문제를 생각해 보자: list = [1,2,3,4,5,6,7,8,9,10] (0번째 값 = 1, 1번째 값 = 2,...) l번째 index에서 r번째 index까지 구간 합을 구하는 문제 이 문제는 여러 가지 방법으로 풀 수 있는데 우선 다음과 같은 방법들을 생각해 보자: 무식하게 list[l] + ... + list[r] 를 더해서 구하는 방법 예전에 배웠던 prefix sum을 사용하는 방법 ([알고리즘] 구간 합 (+LeetCode 1314)) 2번 같은 경우 효율적이라서 이 문제를 푸는데 적합하다. 이제 주어진 list에 대해서 다양한 구간의 합을 구하는 도중, list의 특정 값을 업데이트를 하고 싶다고 하자. 예를 들어서 2번째 값인..

참고하면 좋은 이전 글: [알고리즘] 다이나믹 프로그래밍 (개념) + 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가 작은 간선들을 차례차례 트리에 추가하고, 신장 트리가 완성되면 끝난다. 알고리즘의 시간 복잡도..

집합이 있을 때 어떤 원소가 어떤 부분집합에 속하는지 알아내는 알고리즘이 파인드, 두개의 부분집합끼리 합집합을 해주는 알고리즘이 유니온 (union)이다. 대표적으로 다음 글에 다룰 크루스칼 알고리즘에서 사용된다: [알고리즘] 크루스칼 알고리즘 (+LeetCode 1584). 사실 트리, 집합 등 다양한 상황에서 사용할 수 있는데, 여기서는 트리 구조에서 설명해보겠다 (다른 상황에도 별로 다르지 않다). 그림으로 보면 이해하기 쉬울 것이다: 여기서 같은 색으로 칠해진 원소들은 같은 부분집합이다. 그리고 같은 부분집합의 원소들은 (연결된) 트리를 이루고 있다. 가장 위에 그림에서는 원소 1이 빨강 부분집합에만 해당되지만 1과 2를 연결한다면 검정에도 속하게 된다. 이 때 1이 빨강 부분집합에 해당하는 것을..

이전 글: [알고리즘] 다이나믹 프로그래밍 (개념) + LeetCode 509 [알고리즘] 다이나믹 프로그래밍 (문제편 1: 배낭 문제) 이번 포스트에서는 외판원 순회 문제 (traveling salesmen problem i.e. TSP)를 다이나믹 프로그래밍을 사용해서 풀어보자. 문제: N개의 도시들이 있다. 어떤 도시에서 출발해서 모든 도시를 한번씩만 방문하고, 출발한 도시로 다시 돌아오는 최소 비용을 구해라. 여기서 도시 i에서 도시 j로 가는 비용 W(i,j)는 도시 j에서 도시 i로 가는 비용 W(j,i)와 다를 수 있다. 문제에 대한 자세한 내용은 사이트 참고: https://www.acmicpc.net/problem/2098 예) N=4 cost=[[0, 10, 15, 20], [5, 0,..

다이나믹 프로그래밍 개념은 이전 포스트에서 다뤘다 ([알고리즘] 다이나믹 프로그래밍 (개념) + LeetCode 509) 이번 포스트에서는 대표 문제인 배낭 문제 (Knapsack problem)을 풀어보자 1. 배낭 문제 도둑이 보석가게에 배낭을 매고 침입했는데, 배낭에 최대한 담을 수 있는 무게는 W다 (초과하면 찢어진다고 하자). 보석들의 무게외 값은 미리 알고 있다고 가정하자. 배낭에 담을 수 있는 보석의 최대 가격은? (편의상 무게는 모두 양의 정수 값을 갖는다고 가정하자.) 풀이: W: 최대 담을 수 있는 무게 (양의 정수) jewelry = [(p1,w1), (p2,w2),...,(pn,wn)]: 1번에서 n번째 보석들의 값 p와 무게 w (w는 양의 정수) 우선 단순무식한 풀이를 생각해보..

다이나믹 프로그래밍이란 어떠한 문제를 소문제들로 나누고, 소문제들을 풀어서 결과 값을 저장하고, 원래 문제를 풀 때 소문제의 결괏값을 사용하는 방법론을 말한다. 다이나믹 프로그래밍으로 풀 수 있는 대표적인 문제가 피보나치 수열을 계산하는 문제다 (풀이를 이해하는 것도 쉬운 편이다; 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 ..