LCS(Longest Common Sequence) 알고리즘
LCS LCS(Longest Common Sequence)는 주어진 수열들에 대해 가장 긴 공통 부분 수열이다. 예를 들어, 두 문자열 BCDAACD와 ACDBAC에 대한 공통 부분 수열들은 다음과 같다. BC, CDAC, DAC, AAC, AC, CD ... 이러한 공통 부분 수열 중에서 가장 길이가 긴 부분 수열은 CDAC이다. LCS는 $Dynamic Programming$을 이용해 접근할 수 있다. 알고리즘 동작 다음과 같은 두개의 수열 $X$,$Y$가 있다. 우선, $n = length(X), m = length(Y)$ 일 때, $(n+1)*(m+1)$크기의 dp배열이 필요하다. 그리고 다음과 같이 배열을 채운다. dp[i][j]는 $X$의 i번째 원소와 $Y$의 j번째 원소까지 봤을 때, 현재..
LIS(Longest Increasing Subsequence - 최장 증가 수열) 알고리즘 (1)
LIS(Longest Increasing Subsequence - 최장 증가 수열) (1) https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net !본 글에서는 최장 증가 수열의 길이만 구한다! 또한 본글에서 설명하는 알고리즘의 시간복잡도는 O(N^2)이므로 매우 느리다. 크기가 작은 배열에서 간단한 아이디어로 구현을 하고싶을 때 사용하기 바람. 1. LIS의 길이와 수열을..
유니온 파인드(Union Find)
설명 유니온 파인드는 집합의 표현을 빠르게 구현하는 알고리즘이다. 예를 들어보자. 사람 P1, P2, P3, P4가 있다. 각 사람은 자신의 소속집단 C1, C2, C3, C4에 가입되어 있다고 가정하자. 1. C3에 속한 P3가 P1과의 합병을 진행한다. 그렇다면 P1, P2, P3, P4의 각 소속집단은 C1, C2, C1, C4으로 바뀔 것이다. 2. C1에 속한 P1이 P4와의 합병을 진행한다. 그렇다면 P1, P2, P3, P4의 각 소속집단은 C4, C2, C4, C4으로 바뀔 것이다. 2번 과정에서, P1(C1)과 P4(C4)의 병합을 위해 C1소속 사람과 C4소속 사람의 합병이 진행되었다. 이로인해 C1에 소속이었던 P3의 소속집단도 C4로 변한것을 확인할 수 있는데, 이 방법은 최악의 경..
