개요취직해서 지금 당장 좋은 점 중 하나는 취직 전까지는 내가 하고 싶은 공부를 할 수 있다는 것이기도 하다.사실 옛날부터 세그트리에 대한 궁금증이 있었는데, 코테의 당락을 결정하지는 않을 알고리즘이라 미뤄두었던 기억이 나서 이번에 알아두려고 한다. 세그먼트 트리는 '여러 개의 데이터가 연속적으로 존재할 때, 특정 범위의 데이터의 합/곱/최대값/최소값 등을 구하는 방법'중 하나이다. 수열을 저장하는 배열 A가 존재한다고 가정했을 때, 다음과 같은 케이스를 생각해보자. (A) 구간 l, r (l 이 경우 시간복잡도는 O(N)이다. 누적합, 구간합을 구해놓은 후 특정 구간의 합은 O(1)에 도출할 수 있기 때문이다. (B) 구간 l, r (l 이전 케이스와 다르게, 한번 구해놓은 누적합을 재사용할 수..
개요 따로 알고리즘 포스팅을 하는건 union-find 이후 1년만이다 사실 코테에 나올 확률이 매우 드문 알고리즘이라고 생각해 본인이 코테 대비만 한다면 굳이 알 필요는 없을 것 같지만.. 개인적인 호기심으로 작년 말부터 정리해야겠다 생각은 했는데, 그동안 놓았던 ps를 다시 감을 잡고 돌아오는데 시간이 많이 걸렸다. 위키를 보면 Travelling Salesman Problem(이하 TSP)를 다음과 같이 설명하고 있다."Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to th..
개요 참고 문제: BOJ 11053, BOJ 12015, BOJ 14003, BOJ2568LIS 개념: https://eckrin.tistory.com/30 O(N^2)의 LIS 풀이: https://www.acmicpc.net/source/37212239O(NlogN)의 LIS 풀이: https://www.acmicpc.net/source/75537735 for(int i=0; i 반복문만을 사용하는 LIS의 경우, O(N^2)의 시간복잡도를 가진다. 여기서 12015번 문제의 경우는 N이 백만으로, O(N^2)의 시간복잡도를 가지는 일반적인 LIS를 사용하면 무조건 TLE가 날 것을 예상할 수 있다. int end = 0;for(int i=0; idp[end-1]) { // dp 최대길이 갱신 ..
유니온 파인드 알고리즘 유니온 파인드 알고리즘은 그래프상에서 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 다음과 같이 노드들이 존재할 경우, 유니온 파인드 알고리즘을 위해서는 노드를 나타내는 일차원 정수배열을 이용한다. 이 배열의 값은 노드가 속한 그래프의 정보이자, 대표 노드의 정보를 나타낸다. 당연히 배열의 초기값은 자기 자신으로 세팅한다. 연결된 노드가 없을 경우 자기 자신이 부모노드가 되기 때문이다. 초기화 처음에는 노드들 사이에 관계가 존재하지 않으므로 모든 노드는 자기 자신의 인덱스를 값으로 갖도록 초기화해준다. int[] parent = {1,2,3,4,5,6,7,8}; Union 두 노드가 같은 그룹에 속하도록 합쳐주는 함수이다. 가장 먼저 생각할 수 있는 방법은 한 노드의 값..
부분 배열의 합을 구하기 위해서 다양한 방법을 사용할 수 있다. 1차원 누적합 다음과 같은 배열이 있다고 하자. int[] arr = {1,2,3,4,5}; 두 번째부터 다섯 번째 원소까지의 합을 구하기 위해서는, for문을 이용해서 직접 구해줄 수 있다. for(i=1...5) rst+=arr[i] 그런데 만약 arr이 충분히 크다면, dp를 이용하여 누적합을 저장해두고 갖다 쓸 수 있다. 두번째~다섯번째 원소합 = (첫번째~다섯번째 원소 누적합) - (첫번째~첫번째 원소 누적합) var s5=0, s1=0 for(i=0...4까지) s5+=arr[i] for(i=0...0까지) s1+=arr[i] var arr[1]부터 arr[5]까지 합 = s5-s1 일반화하면 다음과 같은 식이 나온다. 따라서 누..
플로이드 알고리즘 플로이드 알고리즘은 시간복잡도 조건에 여유가 있는경우(O^3) 사용할 수 있는 알고리즘으로, 한 시작점에서 다른 정점까지의 최단 거리를 구하는 다익스트라 알고리즘과 다르게 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구하는 알고리즘이다. 위 가중치 그래프에서, A에서 E로 가기 위한 방법은 (1) A에서 E로 직접 가는 방법과, (2) 중간에 C를 거져가는 방법 총 2가지 방법이 존재한다. 따라서 두 정점 쌍의 최단 거리를 구하기 위해서는 두 정점 사이에 존재하는 경유점을 거쳐가는 방법들을 탐색하며 그 방법들 중에 최소값을 구하면 된다. len[A][E] = Min(len[A][E], len[A][C] + len[C][E]) N개의 노드에 대한 플로이드 알고리즘은 O(N^3)의 시간복..
개요다익스트라(Dijkstra) 알고리즘은 BFS와 Dynamic Programming을 활용한 최단경로 검색 알고리즘이다. 다익스트라 알고리즘은 가중치가 존재하는 그래프의 하나의 정점에서 다른 정점들로 가는 최단 경로를 알려준다. 만약에 가중치가 존재하지 않는다면 단순 BFS를 통해서 최단 경로를 구할 수 있지만, 가중치가 존재한다면 Dijkstra를 사용할 수 있다. 다익스트라는 일반적으로 인접 행렬(O(N^2))이나 우선순위 큐(O(ElogV), E:edge, V:vertex)를 사용하여 구현한다. 시작 전에 간단하게 설명하면, 다익스트라 알고리즘은 방문하지 않은 노드들 중에서 시작점으로부터 최소거리를 갖는 노드를 선택하여 노드들의 거리를 갱신하는 것을 반복하는 알고리즘이다. 일단 시작 노..
예전에 풀고 정리했었는데 까먹어서 다시 정리해봄. 분명히 이해하고 넘어갔는데 왜 지금 보니깐 이해가 안되지?? BOJ 12865) 평범한 배낭 물건을 쪼개어 가져갈 수 있는 fraction knapsack문제에서는 무게당 가치(v/w)가 높은 순으로 가져가면 된다. 하지만 위와 같은 0-1 knapsack 문제는 greedy한 방법으로는 풀 수 없다. for(int i = 1; i
LCS(Longest Common Subsequence, 최장 공통 부분수열) 최장 공통 부분수열이란, 존재하는 두 문자열 사이에 공통으로 존재하는 부분수열 중에 가장 길이가 긴 부분수열을 의미한다. 즉, ACAYKP와 CAPCAK라는 두 문자열이 존재한다면, ACAK(ACAYKP, CAPCAK)가 두 문자열의 LCS가 된다. 부분수열이기 때문에 수열이 연속될 필요는 없다. 수열이 반드시 연속된 문자여야 할 경우 최장 공통 문자열(LCS, Longest Common Substring)이라고 한다. LCS의 풀이는, 먼저 비교 문자열들의 길이에 따라 2차원 배열을 생성한다. 문자열 A("ACAYKP")와 문자열 B("CAPCAK")를 비교하는 상황이라고 하자. LCS[i][j]의 값은 문자열 A의 i번째 ..
유클리드 호제법? 두 양의 정수, 혹은 두 다항식의 최대공약수(gcd)를 구하는 방법을 말한다. gcd, lcm관련 문제를 풀 때 거의 필수적으로 사용된다고 느껴질 정도로 많이 사용되는 것 같다. 두 양의 정수 a,b(a>b)에 대하여 a = bq+r (0
DFS 스택(재귀)을 이용한 DFS에 대하여 알아보자. 코드의 편하게 작성하기 위해서 DFS는 스택을 따로 만들지 않고 재귀적으로 구현하기도 하는데, 이는 재귀적으로 함수호출이 이루어지는 로컬공간 자체가 스택의 구조를 갖고 있기 때문에 동일한 원리라고 할 수 있다. //백트래킹 void dfs(int root) { if(종료조건) return; for(i: root에 방문하지 않은 자식노드) { dfs(i); } 재귀를 이용한 DFS는 간단하게 종료조건이 나오기 전까지 계속 재귀호출을 이어가다가, 종료조건이 나오면 return하는 방식의 DFS이다. 스택을 사용한 DFS도 원리는 동일하다. 다만 상태공간트리에서 leaf노드를 나타낼 때 재귀를 이용한 구현에서는 return문을 사용했다면, 스택을 이용한 ..
그리디(=욕심쟁이, 탐욕) 알고리즘 그리디 알고리즘은 각 단계에서 가장 최선의 선택을 한 후, 선택한 답이 전체적으로도 최선의 방법이기를 '바라는' 알고리즘이다. 최선의 방법이기를 바란다는 말에서 알 수 있듯이 부분적(local)으로만 최선의 해답이고 전역적(global)으로는 최선의 방법이 아닌 경우에 그리디 알고리즘을 적용하게 되면 최선의 해답을 얻을 수 없다. 즉, 그리디 알고리즘을 사용한다고 해서 무조건 최선의 해답을 보장할 수 없다. 따라서 그리디 알고리즘을 사용했을 때 최적의 해답을 주는지가 검증되어야 한다. vs DP 그리디 알고리즘은 동적 프로그래밍과 다르게 지난 선택이나 앞으로의 선택을 고려하지 않는다. 그러므로 탐욕 알고리즘을 적용하려면 앞의 선택이 이후 선택에 영향을 주지 않고 부분적..