흰고래의꿈

1. 개요 LCS란 Longest Common Subsequence의 약자로 최장 공통 부분 문자열이다. 우리가 알고 있는 substring과 비교하면 substring은 연속된 부분 문자열이고 subsequence는 연속적이지는 않은 부분 문자열이다. 예로 들어 Iamhungry라는 문자열에서 연속된 부분 문자열인 mhun은 substring이 되고 연속적으로 이어지지는 않았지만 순서는 맞는 mugy는 subsequence가 된다. 그러면 LCS는 어디에 쓰일까? 대표적으로 LCS가 쓰이는 곳은 염기서열 유사성 분석이다. 이외에도 음파 단어 검색 및 교정 등에 사용된다. 2. 접근방법(1) - LCS의 길이 구하기 DP(Dynamic Programming)으로 특정 범위까지의 값을 구하고 다른 범위까지..

1. 개요 생물의 진화를 모방하여 최적해를 구하는 알고리즘이다. 2. 용어 정의 - 염색체(Chromosome) : 유전정보를 담고 있는 생물학적인 집합을 연속된 문자열로 추상화한 것. - 유전자(Gene) : 염색체를 구성하는 요소, 예를 들어 염색체가 ABC라면 유전자는 A 또는 B 또는 C를 뜻한다. - 교차(Crossover) : 두 개의 유전자가 각각의 유전자를 조합하여 새로운 염색체를 생성하는 연산. - 돌연변이(Mutation) : 교차연산 이후, 확률적으로 유전자의 정보가 바뀌는 것, 생물학적인 돌연변이와 같음. - 자손(Offspring) : 이전 세대의 염색체로부터 교차, 돌연변이 연산을 통해 생성된 다음 세대 염색체. 3. 추상화 예시 유전 알고리즘을 이용하여 해결할 수 있는 문제 중..