개요 따로 알고리즘 포스팅을 하는건 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 return..
유니온 파인드 알고리즘 유니온 파인드 알고리즘은 그래프상에서 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 다음과 같이 노드들이 존재할 경우, 유니온 파인드 알고리즘을 위해서는 노드를 나타내는 일차원 정수배열을 이용한다. 이 배열의 값은 노드가 속한 그래프의 정보이자, 대표 노드의 정보를 나타낸다. 당연히 배열의 초기값은 자기 자신으로 세팅한다. 연결된 노드가 없을 경우 자기 자신이 부모노드가 되기 때문이다. 초기화 처음에는 노드들 사이에 관계가 존재하지 않으므로 모든 노드는 자기 자신의 인덱스를 값으로 갖도록 초기화해준다. 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와 dp를 활용한 최단경로 검색 알고리즘이다. 다익스트라 알고리즘은 가중치가 존재하는 그래프의 하나의 정점에서 다른 정점들로 가는 최단 경로를 알려준다. 만약에 가중치가 존재하지 않는다면 단순 BFS를 통해서 최단 경로를 구할 수 있지만, 이 경우 일반적으로 인접 행렬(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 그리디 알고리즘은 동적 프로그래밍과 다르게 지난 선택이나 앞으로의 선택을 고려하지 않는다. 그러므로 탐욕 알고리즘을 적용하려면 앞의 선택이 이후 선택에 영향을 주지 않고 부분적..
LIS LIS는 Longest Increasing Subsequence 의 약자로 한글로는 ‘최장 증가수열’, 또는 ‘최대 증가 부분수열’로 불린다. 이것은 어떤 수열에서 특정 부분을 지워서 만들어낼 수 있는 증가 부분수열 중 가장 긴 수열을 말하는데 이때 부분수열의 숫자들은 원 배열에서 위치가 이어져 있지 않아도 된다는 주요한 특징이 있다. 예를 들어 원 배열이 [1,4,6,8,3,5,6,7]일 때 [1,6,8], [4,6,8], [1,7]은 증가 부분수열인데, 이 중 가장 긴 부분수열은 [1,3,5,6,7]이 된다. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작..
백트래킹 백트래킹이란 말 그대로 '되추적'의 의미를 가진다. 즉 어떤 노드의 유망성을 판단한 뒤, 해당 노드가 유망하지 않다면 부모 노드로 돌아가서 다른 자식 노드를 찾는 방법을 의미한다. 브루트 포스 알고리즘과 다른 점은, 모든 경우의 수 중에서 가능성이 존재하지 않는다면(=더 이상 유망하지 않다면) 더이상 탐색하지 않는다는 점이다. 이를 위해서는 상태공간트리를 그려 DFS와 같은 탐색 알고리즘을 통해서 구현할 수 있다. DFS의 특징 자기 자신을 호출하는 순환형태의 알고리즘 형태를 가진다. (재귀 호출이 이루어진다) 상태공간트리에서 탐색한 노드에 대한 정보를 검사해야 한다. 상태공간트리에서 탐색할 노드가 유망한지를 검사해야 한다. 트리의 branch의 끝까지 탐색해야 다음 branch를 탐색하기 때문..