동일한 길이를 가지는 두 순열이 있을 때, 한 순열을 다른 한 순열로 변환하는데 필요한 최소한의 작업 횟수
두 문자열이 있을 때, 한 문자열을 다른 문자열로 변환할 때 필요한 최소한의 작업(추가, 삭제, 치환) 횟수추가 : m -> me삭제 : me -> m치환 : me -> my두 문자열을 각각 행, 열로 가지는 행렬을 생성하고, 그 위치에서 한 문자열을 다른 문자열로 변
문자열 T 내에 단어 W가 몇번 사용되는지 확인하는 선형 시간복잡도(O(|W|+|T|)) 알고리즘Z 배열문자열 T에서 인덱스 k까지의 하위 문자열이 k 이후의 하위 문자열에서 몇번 반복되는지를 계산한 배열문자열: aabcaabxaaazZ배열: \[0, 1, 0, 0,
길이가 M인 문자열 내에 길이가 N인 단어가 있는지 확인하는 알고리즘단어 내에 동일한 패턴의 문자가 반복될 경우, 이미 확인이 끝난 패턴의 재확인을 피하기 위해 패턴 테이블을 만든다.패턴 테이블단어: abcaby인덱스 0의 경우: 앞에 문자가 없으므로 0인덱스 1의 경
최장 공통 부분순열은 두 순열의 각 부분순열 집합에서 공통으로 속하면서 길이가 가장 긴 부분순열을 찾는 알고리즘최장 공통 부분문자열과의 차이점은 부분문자열과 다르게 부분순열 문제에서는 순서만 일치한다면 값의 연속성을 고려하지 않아도 된다.최장 공통 부분순열을 해결하기
최장 증가 부분순열은 순열의 부분순열 집합에서 오름차순으로 정렬된 부분순열 중에 길이가 가장 긴 부분순열의 길이를 구하는 알고리즘
배낭에 물건을 담을 때, 물건의 무게와 가치를 고려하여 가장 높은 가치를 가질 수 있는 경우의 수를 구하는 알고리즘물건의 개수가 1개인 경우(0/1)과 물건의 개수가 제한되어 있는 경우(Bounded), 물건의 개수가 제한되어 있지 않은 경우(Unbounded)가 있다