LCS(Longest Common Substring) 정의 최장 공통 부분 수열. 주어진 여러 개의 수열의 부분 수열이 되는 수열들 중에 가장 긴 것을 찾는 문제이다. 백준의 이 문제를 보면 어떤 것인지 이해할 수 있다. (LIS: Longest Increasing Subsequence와 비슷하지만 다른 문제다) LCS는 항상 유일하지 않기 때문에 보통 길이를 묻는 문제가 나온다. 알고리즘 여러 문자열의 LCS를 효율적으로 구하기 위해서 DP가 사용된다. 두 문자열 사이의 LCS 길이를 저장하는 2차원 배열 LCS를 만들고, 아래와 같은 방식으로 배열을 채운다. X, Y 문자열 앞에 0을 넣는 이유는, i=1 || j=1일 때 Xi-1, Yj-1 값을 참조해야 할 수도 있기 때문에 만들어두는 것이다. 아..
https://coding-insider.tistory.com/entry/Prim-vs-Dijkstra-%ED%94%84%EB%A6%BC-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EB%B9%84%EA%B5%90 Prim vs Dijkstra (프림 다익스트라 비교) 프림 알고리즘 (최소스패닝트리) 그래프상에 존재하는 모든 노드들을 최소비용으로 연결시키는 알고리즘 #include #include #include #include using namespace std; int visited[10001]; int V, E; int ans; vector map[10001]; coding-insider.tistory.com
최소 신장 트리, MST (Minimum Spanning Tree) 개념 신장 트리(spanning tree): 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 최소 연결 부분 그래프. 최소 신장 트리(minimum spanning tree): 신장 트리 중 간선의 가중치 합이 가장 작은 트리 특징 (n-1)개의 간선만을 사용하며 간선의 가중치 합이 최소여야 한다. 사이클이 없어야 한다. (사이클이 존재 == 한 곳으로 도달하는 경우가 두 개 이상 존재 != 최소한의 연결) 그리디 기법으로 최적의 해를 구할 수 있다. 관련 알고리즘 Kruskal's Algorithm 작동 그래프의 모든 간선의 집합 E을 만든다. E가 비어있지 않을 때까지 아래를 반복한다. E의 간선들 중 가중치가 최소인 간선을 지운..
유클리드 호제법(-互除法, Euclidean algorithm) 2개의 자연수 또는 정식(整式, 유리식)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법: 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘 유클리드 호제법은 A와 B의 최대공약수를 A를 B로 나눈 나머지 값을 활용하여 구하는 방식이다. 그 내용은 다음과 같다. A와 B의 최대공약수를 (A, B)라 표기할 때, (A, B) = (B, A%B) 이다. 유클리드 호제법은 위의 과정을 나누는 수가 0이 되어 더이상 나눌 수 없을 때 까지 반복한다. 수식으로 표현하면 이렇게 된다. (A, B) = (B, A%B) = (A%B, B%(A%B)) = (B%(A%B), (A%B)%{B%(A%B)}) = ... 예시를 함께 보자. 78..
LIS의 다른 두가지 방법 이번에는 이진 검색을 활용하여 최장 증가 수열의 크기를 구해보자. C[k]: 길이 k인 증가 수열에 대하여, 0~(k-1)번째 값을 고려하였을 때 k번째에 들어갈 수 있는 가장 작은 값을 C[k]에 저장한다. 이때 이전 알고리즘과는 다르게 LIS 길이는 C[k]에 저장되는 것이 아니라, k 그 자체가 된다! 예를들어 한 학급의 학생들을 키 순으로 정렬한다고 생각해보자. 결과적으로 완성되는 배치는 다음과 같다. 여기서 주의할 점은 line5는 LIS가 아니라는 것이다!!! 이 배열은 오직 LIS의 길이를 구하기 위해 제작된 것이라 이 배열만으로는 정확한 LIS를 알아낼 수 없다.
순열 ( nPr ) static int N, R; static int[] input, numbers; public static void permutation(int cnt, int flag) { // cnt: 직전까지 뽑은 수개수, flag: 뽑힌 수들에 대한 플래그 비트열 if(cnt == R) { System.out.println(Arrays.toString(numbers)); return; } // 입력받은 모든 수를 현재 자리에 넣어보기 for (int i = 0; i < N; i++) { if((flag&(1
