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 값을 참조해야 할 수도 있기 때문에 만들어두는 것이다. 아..
위상 정렬(Topological Sorting)정의방향 그래프에서 각 정점들이 어떤 순서로 방문되어야 하는지를 결정하는 알고리즘.그래프에서 어떤 정점이 다른 정점에 의존하는 관계가 있을 때, 그래프를 순서대로 방문하기 위해 위상 정렬을 사용할 수 있다.위상 정렬은 다양한 분야에서 사용된다. 예를 들어, 컴파일러에서는 소스 코드의 의존성을 파악하기 위해 위상 정렬을 사용한다. 그 외에도 작업 스케줄링, 프로젝트 관리, 그래프 이론 등 다양한 분야에서 유용하게 사용된다. 예제https://www.acmicpc.net/problem/14567선수과목처럼 어떤 상태에 도달하기 위해 우선적으로 도달해야 할 상태가 있고, 이것을 준수한 채 모든 정점을 방문할 수 있는 순서를 구하는 것이다. 해당 문제에서는 그래프의..
Prim VS Dijkstra두 알고리즘은 동작 방식은 비슷하지만 사용의 목적이 다르다.특징프림 알고리즘다익스트라 알고리즘목적최소 신장 트리(MST) 생성출발점으로부터 각 노드까지의 최단 경로 탐색비슷한 알고리즘Kruskal벨만 포드, 플로이드 와샬결과모든 노드를 최소 비용으로 연결하는 트리출발 노드에서 다른 노드로 가는 최단 거리간선의 가중치음수 간선 허용 가능음수 간선 허용 불가시작점시작점은 임의의 노드여도 무관출발점이 명확하게 정해져야 함중간 목표매 단계에서 MST에 포함되지 않은 가장 비용이 적은 간선을 선택매 단계에서 출발점으로부터 최단 거리 노드를 선택동작 방식1. 특정 노드를 MST에 추가2. 해당 노드(MST 대표)에서 다른 노드들 까지의 거리를 구함 -> dist[]3. dist[] 기준..
최소 신장 트리, 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
