[알고리즘] 최장 공통 부분수열(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.
[알고리즘] Greedy Algorithm(탐욕 알고리즘)
Greedy Algorithm[탐욕 알고리즘]이란? 각 단계에서 가장 최선의 선택지(가장 큰, 가장 작은 등)를 고르는 것. Greedy 알고리즘은 구현이 쉽다는 장점이 있지만, 항상 최선의 답을 구하는 것은 아니다. Greedy Algorithm을 활용 가능한 문제 1) 거스름돈 x라는 금액의 거스름돈이 주어야할 때, 10,000원, 5,000원, 1,000원, 500원, 100원으로 가장 적은 갯수의 거스름 돈을 주어야하는 상황 #include using namespace std; int main(){ int x, cnt = 0; cin >> x; // 가장 큰 액수의 화폐부터 선택 cnt += x / 10000; x = x % 10000; cnt += x / 5000; x = x % 5000; cn..
2020. 1. 8.
