📂 알고리즘/ETC

최장공통부분수열(Longest Common Subsequence - LCS)

1. 개념 🐢 최장공통부분수열(Longest Common Subsequence)이란 주어진 수열의 부분 수열에서 가장 긴 것을 의미한다. 위의 그림에서 알 수 있는 것처럼 부분 수열이 연속적일 필요는 없다. 2. 동작방식 🦎 동작 방식은 DP를 이용한다. 문자열 A와 문자열 B가 주어졌다고 하자. 문자열 A와 문자열 B를 한 글자씩 비교한다. 비교하는 문자가 같다면 DP[i][j] = DP[i - 1][j - 1] + 1이 된다. 비교하는 문자가 다르다면 DP[i][j]는 DP[i-1][j]와 DP[i][j-1] 중에 큰 값으로 설정한다. 1번과 2번 과정을 반복한다. 여기서 말하는 DP[i][j]는 문자열 A는 i번째까지 문자열 B는 j번째까지 고려하였을 경우에 얻을 수 있는 최장공통부분수열의 길이이다..

최장공통문자열(Longest Common Substring - LCS)

들어가기에 앞서 LCS를 구별하도록 하자. 일반적으로 LCS라고 하면 최장공통부분수열(Longest Common Subsequence)을 뜻하지만, 최장공통 문자열(Longest Common Sustring)도 LCS라고 부르기도 한다. 둘의 차이점은 구하고자 하는 부분 문자열의 연속성이라고 할 수 있다. 이번 글에서는 최장공통 문자열(Longest Common Substring)에 대해서 먼저 알아보자 1. 개념 🦆 최장공통부분문자열(LCS)은 연속된 부분 문자열 중 가장 길이가 긴 문자열을 말한다. 2. 동작 방식 🐓 동작 방식은 DP를 이용한다. 문자열 A와 문자열 B가 주어졌다고 하자. 문자열 A와 문자열 B를 한 글자씩 비교한다. 비교하는 문자가 같다면 DP[i][j]는 DP[i-1][j-1] ..

최장증가부분수열(Longest Increasing Subsequence - LIS)

1. 개념 🌠 최장 증가 부분 수열(LIS - Longest Increasing Subsequence)이란 임의의 수열로 만든 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 의미한다. '3 2 6 4 5 1'이 있다고 하자. 해당 수열의 부분 수열은 {3}, {2}, {6},... {3, 2}, {2, 1},... {2, 6, 4}, {2, 4, 5},... {3, 2, 5, 1},... {2, 6, 4, 5, 1},... {3, 2, 6, 4, 5, 1} 등이 존재한다. 여기서 최장 증가 부분 수열은 {2, 4, 5}이며 그 길이는 3이 되게 된다. 이번 글을 통해 최장 증가 부분 수열의 길이를 구하는 3가지 방법을 알아보자. 순서는 시간복잡도가 큰 것에서부터 작은 것으로 진행된다. 2. 방법 1 ..

서로소 집합(Disjoint-sets)

1. 서로소 집합의 개념 및 이해 🛺 1. 개념 서로소 집합이란 서로 중복 포함된 원소가 없는 집합을 말한다. 교집합이 없는(null) 집합이다. 2. 대표자 집합에 속한 하나의 특정 멤버를 대표자라고 한다. 이는 집합을 구분하기 위해 사용된다. 3. 예시 빠른 이해를 위해 간단한 예시를 살펴보자. 5명의 학생(A, B, C, D, E)이 있다고 하자. {A}, {B}, {C}, {D}, {E} 아래와 같은 친구 관계가 있다고 하자. A - B B - C D - E 친구 관계를 통해서 2개의 집합을 만들 수 있다. G1 = {A, B, C} G2 = {D, E} 서로 중복 포함된 원소가 없으므로 이는 서로소 집합이다. (한 사람이 분신술을 써서 양쪽 집합에 포함될 수 없으므로 당연한 결과이다.) 2. 표..