PS/Algorithm
저수지 샘플링 Reservoir Sampling
어떤 array에서 random한 i번째 element를 뽑고 싶다고 하자. 일반적으로 전체 배열의 size를 알아내고 rand () % size를 한 후 해당 index를 가져오는 방식을 택할 것이다. 그러나 모종의 이유로 전체 배열 size를 알 수 없는 상황에서도 무작위 추출을 할 수 있다. 예를 들어 array가 아니라 singly linked list여서 끝을 모르고, 단 1번 순회해야 한다는 조건이라면? 1번의 순회로 size를 알아내도 index에 접근하는 데 O(n)이 걸리기 때문에 해결할 수 없다. 이런 상황에서 Reservoir sampling을 사용한다. Reservoir Sampling 정의 Reservoir sampling은 어떤 배열을 1번에 1개의 element만 보며 순회할 ..
Two Pointer, Sliding Window, Meet in the Middle ***TODO
two pointer 특 : 그냥 포인터 2개 움직이면 됨 sliding window 특 : 크기 고정한 two-pointer임. 주의할 점은 배열의 indexding. meet in the middle 특 : div&conquer인데 1번만 하는 경우임. 주어진 n으로 Brute-Force는 불가능 해 보이지만, n/2로 Brute-Force는 가능해 보일 때 사용하는 기법. 보통 n이 30~50정도일 때 쓸 수 있다. 앞 절반, 뒤 절반으로 나누고 앞 절반으로 뒤 절반을 탐색하면 된다. 그 절반을 정렬해도 $log2^{n/2} = log(n/2)$이기 때문에 $O(2^{n/2} * n/2)$에 풀린다.
누적 합 Prefix Sum
어떤 배열 arr에 대해 prefix sum 배열을 만들어 배열의 index i부터 index j까지의 합을 O(1)으로 풀 수 있는 알고리즘. 배열의 크기가 $O(n^{k})$일 때 초기화는 $O(n^{k})$, 구간 합을 구할 때는 O(1)의 시간이 걸린다. 특정 구간의 합을 구하는 것이기 때문에 해당 구간의 값이 변화하지 않는 것을 통해, 특정 구간 안에 원소가 있는지 없는지도 쉽게 계산할 수 있다.(2차원도 적용 가능) range sum을 구할 때 index를 주의하도록 하자. 1. 1차원 Prefix Sum : 초기화 $O(n)$, 쿼리당 O(1) range sum을 구할 때, start가 0이면 -1로 out of bound가 되어버리므로 start가 0일 때만 예외 처리를 해 주자. // r..
동적 계획법 Dynamic Programming (+ LIS)
DP의 정의는 '복잡한 문제를 간단한 문제로 나누어 풀고, 이 subproblem으로 원 문제를 푸는 것'이다. 어떻게 보면 divide-and-conquer과 유사하지만, DP의 경우 subproblem이 중복되기 때문에 좀 더 빠른 시간으로 풀 수 있다. 그렇기 때문에 필자는 DP의 핵심이 memoization과 recursion relation(점화식)의 2가지라 생각한다. memoization으로 이미 계산 한 값이라면 그 값을 return하고, recursion relation으로 계산한 값을 이용해 다음 값을 빠르게 구할 수 있다. 예제 : 냅색 if j - cost[i] >= 0 then dp[i][j] = max(dp[i][j], dp[i-1][j-cost[i]] + value[i]) el..
좌표 압축
값의 대소 관계만 필요하다면 수를 바꾸어 사용할 수 있다. 예를 들어 [0, 1, 5, 6, 11] 이런 좌표라면 [0, 1, 2, 3, 4]로 바꿀 수 있고, [0, 100, 150, 50, 175, 50, 50] 이런 좌표라면 [0, 2, 3, 1, 4, 1, 1]로 바꿀 수 있다. 방법은 크게 2가지가 있다. vector의 unique 값을 지우고 lower_bound로 해당 값을 찾는 방법 set으로 중복을 지우고 map으로 압축된 좌표를 mapping하는 방법 1. vector의 unique 값을 지우고 lower_bound로 찾는 방법 : O(nlogn) void gridCompress(vector &arr){ vector temp(arr.size()); for(int i = 0; i
정렬 ***TODO
stable sort는 정렬을 했을 때 중복된 값들의 순서가 변하지 않는 sort. 변한다면 unstable이다. 아래 정렬들은 stable. Bubble Sort, Insertion Sort Counting Sort Merget Sort in-place sort는 추가적인 메모리가 거의 들지 않는 sort. 아래 정렬들은 in-place. Bubble Sort, Selection Sort, Insertion Sort Quick Sort, Heap Sort Implenentation of Sort Bubble Sort : $O(n^{2})$ - Stable and In-Place Sort array의 값 2개를 비교해서 비교함수를 만족하지 않는다면 swap하는 방식 for(int i = 0; iN>>IN..
그래프 알고리즘 - (7) BST의 간단한 구현과 Tree traversal
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다. 1. Tree 앞선 글에서 설명했듯 Tree는 directed acyclic graph이다. 그 중 대표적인 binary search tree의 몇몇 method의 구현과, 그 순회를 살펴볼 것이다. struct node{ node *left, *right, *parent; int x; }; // root node 초기화 node* initRoot(){ node *root = new node; root->parent=root; root->left = root->right = NULL; root->num=rootnum; } void insertNode(node *root, int value){ node *paren..
그래프 알고리즘 - (6) 위상 정렬 Topological sort
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다. 1. DAG란? Definition DAG는 directed acyclic graph이다. cycle이 없는 directed graph라는 말이다. Property DAG는 적어도 하나의 sink와 하나의 source가 있다. sink는 나가는 edge가 없는 vertex, source는 들어오는 edge가 없는 vertex이다. cycle이 없다 -> source가 있다, 이며 source가 없다 -> cycle이 있다, 라는 말이 된다. 2. 위상정렬 Topological Sort Definition 모든 directed edge (u, v)에 대해 u가 항상 v보다 더 빨리 오게 vertex를 정렬하는 방식..
그래프 알고리즘 - (5) Minimum Spanning Tree(Kruskal, Prim)
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다. 1. Minimum Spanning Tree 정의 MST는 모든 vertex를 포함하면서 weight를 최소화한 tree이다. 이는 greedy하게 구할 수 있으며, Kruskal과 Prim 2가지 방법으로 구할 수 있다. 2. Kruskal Algorithm Cut Property MST T에 속해있는 edge들의 부분집합 X에 대해, X가 속해있는 영역 S와 나머지 영역 V\S로 나눈다. e가 S와 V\S를 weight가 가장 작은 edge라고 하자. 그러면 X ∪ {e}는 MST의 부분집합이 된다. proof) e가 MST T의 일부라면 X ∪ {e}는 T의 subset인 것은 자명하다. 그렇지 않고 T가 ..
그래프 알고리즘 - (4) Union-find(disjoint set)
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다. 1. Disjoint Set과 Union-Find Disjoint Set disjoint set은 서로 중복되지 않은 부분 집합들로 이루어진 자료구조, "서로소 집합"이라고 이해하면 될 것 같다. Union-Find union-find는 disjoint set의 표현 및 연산에 사용하는 알고리즘이다. 보통 Directed Tree를 이용해 구현하며, tree의 root는 해당 set의 대표값으로 생각하면 된다. 아래 예시에서는 {1, 2, 3, 4,}, {5, 6, 7, 8}, {9}가 각각의 set이며, 첫 번째 set의 대표값은 4, 두 번째 set의 대표값은 5, 세 번째 set의 대표값은 9이며 이 값들을..
그래프 알고리즘 - (3) Dijkstra, Bellman-Ford, Floyd-Warshall
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다. 세 알고리즘 모두 '최단 거리'를 알아내는 알고리즘이다. 다만 어디서부터 어디까지 알아내는가가 다를 뿐이다. 1. dijkstra : O((|V| + |E|) * log|V|) 한 vertex에서 다른 모든 vertex까지의 최단거리를 알아내는 알고리즘이다. BFS와 유사한 알고리즘으로, BFS는 queue를 사용하지만 dijkstra는 priority queue(heap)을 사용한다. 다만 dijkstra는 weight가 음수인 경우에는 풀리지 않는다! procedure dijkstra(G, s) for all vertex u in V do dist(u) = INF prev(u) = null end for di..
그래프 알고리즘 - (2) 넓이 우선 탐색 & 깊이 우선 탐색 BFS & DFS
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다. 1. DFS DFS는 어떤 vertex s로부터 reachable한 vertex를 뽑아내는 과정이다. 요점은 아래 2가지이다. - visited인 vertex는 다시 가지 않는다 - 현재 explore 중인 vertex와 연결된 vertex를 바로 탐색한다 pseudo code procedure DFS(G) for all vertex v in V do visited[v] = false end for for visited[v] == false do explore(v) end for procedure explore(w) visited[w] = true for each edge (w, u) in E do if visi..
그래프 알고리즘 - (1) Graph의 기본
이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다. 1. graph란? graph G = (V, E)로 이루어지는 자료 구조 중 하나이다. V는 vertex(node)의 set, E는 edge의 set이다. graph G를 (V, E)로 표현할 수 있다. 2. graph의 종류 Undirected Graph G = (V, E) 중 edge set E의 모든 edge는 node가 연결되었다는 것만을 의미하는 것이다. 방향은 신경쓰지 않는다는 의미이며, 따라서 vertex 1과 vertex 2를 잇는 edge를 (1, 2)로 표현하든 (2, 1)로 표현하든 같은 말이다. Directed Graph G = (V, E) 중 edge set E의 모든 edge가 어떤 no..
PS에서 Master Theorem
Master Theorem은 알고리즘의 동작 시간을 대략의 수행시간을 big O notation으로 계산하는 방법이다. 일반적으로 divide-and-conquer와 같은 recursion에서 자주 사용하며, 입력이 n개인 task를 문제를 입력이 n/b개인 a개의subtask로 나눴을 때, 그 subtask를 f(n)만에 해결할 수 있다면 아래 식과 같이 표현한다. $T(n) = aT(\frac{n}{b}) + f(n)$ (단, a >= 1, b > 1, p >= 0) Master Theorem은 T(n)에 관한 점화식을 푼다. 그러나 대부분의 PS에서 f(n)은 $\Theta(n^{k}log^{p}n)$으로 정의되니, 이 식에서 답을 도출해 볼 것이다. 1. if $log_{b}a < k (\Left..
이진탐색 Binary Search, Lower/Upper Bound, Parametric Search
이진 탐색 : O(logn) 개념 Binary search는 정렬된 array에서 어떤 값 k를 찾는 방법이다. 이 또한 divide and conquer를 사용하는 방식으로, 재귀방정식을 세우면 아래와 같다. $T\left(n\right)\ =\ T\left(\frac{n}{2}\right)\ +\ c$ 따라서 시간복잡도는 O(logn). 다른 방식으로, 처음 n개를 탐색할 때, 중앙값을 보고 탐색할 부분을 절반으로 나눈다. 다음 n/2개를 탐색할 때, 중앙값을 보고 탐색할 부분을 절반으로 나눈다. ... 마지막 것이 탐색된다. 즉, n개의 input이 있을 때 탐색은 logn번 진행한다. 반복문으로 탐색 : O(logn) int search(vector& v, int input){ int star..
순열, 조합, 중복순열, 중복조합 - 코드
순열 서로 다른 n개의 원소에서 r개를 뽑을 때, "중복을 허용하지 않고", "뽑는 순서를 고려하는" 것 1. DFS로 탐색 : O(nPr) 다만 이 경우는 중복이 있는 경우는 못 잡는다! // nPr의 경우 // arr : 순열할 원소, size n // visited[i] : arr[i]가 방문되었는지 여부, 초기값 false, size n // result : 순열 결과, size r void permutation(int depth, int r, vector& arr, vector& visited, vector& result){ if(depth == r){ for(int i : result){ cout
순열, 조합, 중복순열, 중복조합 - 개념
기본적으로 위 4개 개념은 다음과 같은 명제에서 시작한다. 서로 다른 공 n개가 든 상자에서 r개를 뽑는 경우의 수 이제 어떻게 뽑느냐가 결정을 하는데, 뽑는 순서를 고려한다면 순열, 그렇지 않다면 조합이다. 또한, 중복을 허용하는 것과 그렇지 않은 것으로 나눈다. 그래서 2 * 2, 총 4개의 개념이 있는 것이다. 이 때, 중복을 허용한다는 것은 공을 뽑고, 다시 복원한다고 생각하면 될 것이다. 순열 - "중복을 허용하지 않고", "뽑는 순서를 고려함" 조합 - "중복을 허용하지 않고", "뽑는 순서를 고려하지 않음" 중복순열 - "중복을 허용하고", "뽑는 순서를 고려함" 중복조합 - "중복을 허용하고", "뽑는 순서를 고려하지 않음" 순열 개념 서로 다른 n개의 원소에서 r개를 뽑을 때, "중복을 ..
sort 시 seg fault발생 - strict weak ordering
지난주에 programmers lv1 실패율 문제를 풀다가 seg fault가 났었다. 내가 알던 seg fault는 잘못된 memory에 접근하는 경우에 생겼기 때문에 vector의 index를 잘못 참조하지 않는지 확인했지만 아무리 봐도 그런 경우가 없었다. 그래서 이것저것 디버깅을 해 보다가 sort 함수를 빼면 seg fault가 안 나는 것을 확인했고, 그러다가 결국 정렬 함수에 문제가 있다는 것을 알게 되었다. 아래는 내가 쓴 코드다. #include #include #include #include using namespace std; typedef pair pid; bool comp(pair& a, pair& b){ if(a.second > b.second) return true; else{..
빠른 거듭제곱 Fast Exponentiation (+ 피보나치 수)
빠른 거듭제곱 : O(log(exp)) a^b을 구할 때, simple하게는 a를 b번 곱하면 된다. 그러나 b가 너무 커져버릴 경우에는 시간 안에 연산을 끝내지 못할 수도 있다. 이 때 사용하는 게 빠른 거듭제곱 알고리즘이다. divide and conquer 방식을 사용하는 것으로, $a^{b}$에서 b가 홀수라면 $a^{b} = a^{\tfrac{b}{2}} \times a^{\tfrac{b}{2}} \times a$ b가 짝수라면 $a^{b} = a^{\tfrac{b}{2}} \times a^{\tfrac{b}{2}}$ 를 반복해, b가 0이 될 때까지 반복하는 알고리즘이다. top case부터 b=0인 base case까지 귀납적으로 보이면 되고, $\tfrac{b}{2} + \tfrac{b}{..
행렬곱 알고리즘
1. 일반적인 행렬곱 : $O(n^{3})$ vector solution(vector arr1, vector arr2) { int row1 = arr1.size(), col1 = arr1[0].size(); // = row2 int col2 = arr2[0].size(); vector answer(row1, vector(col2, 0)); for(int i =0; i
약수, 소인수분해, 최대공약수/최소공배수 알고리즘
약수 1. Simplest Version : $O(n)$ set getFactorNumber(int n){ set v; for(int i = 1; i
2020/07/08 공부 - dynamic programming
오늘은 LIS 쪽 문제를 풀었다. 먼저 11053번. LIS의 제일 기본이 되는 문젠데, 이 문제는 n square로 풀어도 되지만 어차피 DP를 배우니까 nlogn으로 풀었다. 다른 DP 문제와 동일하게, 일단 memoization을 위해 몇 가지 array를 만든다. 내 코드에서는 DP는 각 index별로 최대 length를 저장하는 곳, LIS_array에는 LIS를 저장하는 곳으로 두었다. DP[i]에는 input vector의 index i까지 LIS를 저장해 두었다고 가정하고, 새 index i+1을 볼 때는 2가지 경우의 수가 있다. 먼저 input[i+1]이 지금까지의 LIS_array의 마지막 항보다 큰 경우는 바로 LIS_array vector의 마지막에 추가하면 된다. 반면 마지막 항..
2020/07/07 공부 - dynamic programming
어제에 이어서 DP 공부를 했다. 작년 이맘쯤에 객체지향 프로그래밍 첫 과제로 BFS와 LIS가 나왔었는데, 당시 BFS는 이해했는데 LIS는 이해를 잘 못했었다. 그 해 여름방학 관심 생겨서 공부했을 때도 다른 DP는 점화식으로 어떻게 풀었는데 LIS와 냅색은 잘 이해하지 못했었던 기억이 있다. 각설하고, 오늘은 문제를 몇 개 풀었다. 먼저 1463번. 1로 만드는 데 몇 번의 연산이 필요하냐는 문제이다. DP의 정석으로, 필요한 것은 미리 계산해 두고, 점화식에서 이 미리 계산해둔 것들을 불러오는 방식을 취한다. void solve() { int N; cin >> N; vector make_one(N+1); make_one[0] = 0; make_one[1] = 0; if (N >= 2)make_on..
2020/07/06 공부 - dynamic programming
backtrack을 끝내고 이제 DP를 해볼 차례다. DP는 원래 n square의 시간복잡도가 걸리는 일을 2가지 방법을 이용해 n에 linear하게 수행할 수 있도록 해주는 기법 중 하나이다. 이 2가지 방법은 첫째, 현재의 state로 미래의 state를 계산해 주는 점화식 둘째, 이미 계산했던 값이라면 계산했던 값을 사용하는 memoization 두 가지를 사용한다. 대표적으로 DP를 사용해서 시간을 줄일 수 있는 것이 조합이다. nCr에서 파스칼의 삼각형 특징을 이용해서 복잡한 계산을 조금 간단하게 줄일 수 있는데, 순열 점화식 $_nC_0=_nC_n=1$ $_nC_r=_{n-1}C_{r-1}+_{n-1}C_r$ 에서 2번째 점화식의 우항 부분이 계산되어 있다면 이를 저장해둔 후, 필요할 때 불..
2020/07/06 공부 - backtracking
오늘은 backtrack 마지막 문제, 스타트와 링크를 풀었다. 총 N명의 사람 중 N/2명을 고르는 것이므로 $_nC_{n/2}$ 만큼의 경우의 수를 봐 주어야 한다. 총 1부터 8까지 사람이 있으면 1 2 3 4 1 2 3 5 1 2 3 6 1 2 3 7 1 2 3 8 1 2 4 5 1 2 4 6 1 2 4 7 ... 2 3 4 5 2 3 4 6 ... 대충 이런식으로 조합 경우의 수가 정해지기 때문에, 제일 최근에 탐색한 사람 다음 사람부터 DFS를 실행했다. 그리고 N이 짝수인 것은 보장되었기 때문에 depth가 N/2가 되면 점수 계산을 진행한다. 조금 더 깔끔한 코드도 존재할 수 있겠지만 아직 그 정도의 실력이 안 되는 것 같다. 전체적인 구조는 다른 backtrack 문제들과 동일하다. de..
2020/07/04 공부 - backtracking
오늘은 저번에 이어 backtrack의 다른 예제를 풀었다. 백준 2580번 스도쿠이다. 내가 알고 있는 CSP와 굉장히 유사한 문제이기 때문에 backtrack으로 푸는 것이 좋다. 숫자를 채워 넣을 때 lookahead 등의 heuristics를 쓸 수도 있지만 귀찮아서 순서대로 채워 넣었다. 먼저 backtrack의 pseudo code는 다음과 같았다. 이 pseudo code를 따라가면 코드를 완성할 수 있다. DFS(list, depth, N) { if (depth == N) return; else { if (bounding_function() == true) DFS(list, depth + 1, N) else return; } } DFS(list, 0, N) 스도쿠에서 boundnig fun..
2020/07/02 공부 - backtracking
방학 때 공부해서 ACM-ICPC에 나가려 팀을 모았는데, 어쩌다 팀이 터졌다. 그래서 카카오 코페나 SCPC같은 것들만 조금 해 보려 한다. 글에 한글과 영어를 많이 혼용하는데, 영어 수업을 듣다보니 이게 더 편해졌다. 이번 학기 AI 수업을 들으면서 배웠던 backtracking을 조금 복습했다. backtracking은 CSP를 풀기 위해 나온 알고리즘이다. '순서'가 중요하지 않기 때문에, 내 맘대로 순서를 설정해도 되기 때문에 재귀를 이용한 DFS로 구현한다.(queue로 구현해도 되는데 재귀는 알아서 stack이 만들어지는 반면 queue는 내가 직접 만들어 줘야 해서 귀찮다. 시간복잡도에 유의미한 차이가 있는 것도 아니고) 또 brute-force와 비슷한데, 특정 조건을 만족하지 않으면 다..