[알고리즘] 최장 공통 부분수열(LCS, Longest Common Subsequence)
최장 공통 부분수열(LCS, Longest Common Subsequence) 최장 공통 부분 수열은 두 개의 문자열이 주어졌을 때, 문자로 이루어진 부분 수열 중에서 가장 긴 문자열이 일치하는 수열을 말한다. 예를 들어 cdabe와 cdegt가 주어졌다면 이 두 문자열의 최장 공통 부분수열은 cdabe, cdegt 즉, 길이가 3인 부분수열 {c, d, e} 된다. 최장 공통 부분수열 과정 최장 증가 수열은 동적 계획법(DP, Dynamic Programming)을 이용해 풀 수 있다. 각각 n, m길이의 두 문자열 str1, str2가 주어졌을 때, n X m 크기의 2차원 배열을 만든다. 이 2차원 배열은 각 문자열, i번째, j번째 원소까지의 최장 공통 부분을 저장할 배열이다. 각 문자열의 부분문..
2020. 3. 2.
[알고리즘] 최장 증가 수열(LIS, Longest Increasing Subsequence)
최장 증가 수열(LIS, Longest Increasing Subsequence) 최장 증가 수열이란 어떤 수열이 주어졌을 때, 최장으로 증가하는 부분 수열을 말한다. 즉, 1, 2, 3, ..., i, i+1, i+2, ..., n까지의 수열 a[n]이 주어졌을 때, a[i]
2020. 3. 2.
[알고리즘] 에라토스테네스의 체
에라토스테네스의 체 에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 소수를 찾기위해 만들어낸 방법으로, 마치 체를 치듯이 수를 걸러내기 때문에 에라토스테네스의 체라고 부른다. '에라토스테네스의 체'로 소수를 구하는 방법은 2부터 시작해 하나의 수를 뽑고, 뽑은 수의 배수를 소수의 후보에서 제외시킨다. 에라토스테네스의 체 과정 만약, 1부터 10까지의 수 중 소수를 찾는다면 2부터 시작해서 2의 배수를 소수의 후보에서 제외시킨다. 2, 3, 4, 5, 6, 7, 8, 9, 10 (1은 소수가 아니므로 후보에서 제외)에서 2의 배수를 제거하면 2, 3, 5, 7, 9가 남는다. 2, 3, 5, 7, 9 에서 3의 배수를 제거하면 2, 3, 5, 7이 남는다. 이러한 방식으로 소수의 후보를 계속해서..
2020. 2. 27.
