1. 스트링 알고리즘 관련 기본 개념스트링( string )이란?문자가 연속적으로 나열된 문자열예시ATATCGCCCACTAT001011010001110101알파벳 ( alphabet, Σ )스트링에 사용되는 문자들의 집합예시DNA 서열 ➝ Σ = { A, C, G, T }이진 데이터 ➝ Σ = { 0, 1 }2. 스트링 알고리즘스트링에 대한 다양한 문제를 해결하는 알고리즘을 통칭스트링 매칭스트링 압축최장 공통 부분 수열최장 반복 서브스트링최장 회문 서브스트링접미부 트리접미부 배열…3. 스트링 매칭텍스트에서 패턴이 나타나는 위치를 찾는 것텍스트 T = t₀t₁t₂⋯tₙ₋₁ → 긴 스트링, 길이 n패턴 P = p₀p₁p₂⋯pₘ₋₁ → 짧은 스트링, 길이 mn ≥ m예시T = a a b a a b a a aP..
1. 동적 프로그래밍문제의 크기가 작은 소문제에 대한 해를 테이블에 저장해 놓고, 이를 이용해서 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법각 소문제는 원래 주어진 문제와 동일한 문제 ➝ 입력 크기만 작아진 문제소문제들은 서로 독립일 필요는 없음동적 “프로그래밍” ➝ “동적 계획법”컴퓨터 프로그램과는 무관, 해를 구축하는 데 테이블을 이용한다는 의미최소값 / 최댓값을 구하는 최적화 문제에 주로 사용"최적성의 원리 ( principle of optimality )"를 반드시 만족하는 문제에만 적용 가능최적성의 원리란?주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성동적 프로그래밍 방법의 처리 과정(0) 최적성의 원리가 주어진 문제에 성립하는 지 확인(1) 주어진..