동적 프로그래밍

행렬 체인의 최적 괄호화를 찾아 스칼라 곱셈 횟수를 최소화합니다. CLRS 15장의 대표적인 동적 프로그래밍 문제입니다.

중복 계산을 피하기 위해 동적 프로그래밍을 사용하여 피보나치 수를 효율적으로 계산합니다. 지수 시간 재귀 솔루션을 선형 시간 알고리즘으로 변환하는 메모이제이션의 힘을 보여줍니다. 동적 프로그래밍 개념에 대한 고전적인 소개입니다.

두 시퀀스에 동일한 순서로 존재하는 가장 긴 부분 수열을 찾습니다. 동적 프로그래밍을 사용하여 솔루션 테이블을 구축합니다. DNA 서열 정렬, 파일 차이 도구(diff), 표절 감지 등의 응용 프로그램이 있습니다.

한 문자열을 다른 문자열로 변환하는 데 필요한 최소 단일 문자 편집(삽입, 삭제, 대체) 횟수를 계산하는 동적 프로그래밍 알고리즘입니다. 맞춤법 검사, DNA 서열 정렬, 자연어 처리의 기본이 됩니다.

주어진 무게와 가치를 가진 아이템을 선택하여 무게 제한 내에서 총 가치를 최대화하는 고전적인 동적 프로그래밍 문제입니다. 각 아이템은 한 번만 선택할 수 있습니다(0/1). 자원 할당, 포트폴리오 최적화, 화물 적재 등의 응용이 있습니다.

모든 요소가 증가하는 순서인 가장 긴 부분 수열을 찾습니다. 대표적인 동적 프로그래밍 문제입니다.

O(n) 시간에 최대 합을 가진 연속 부분 배열을 찾는 우아한 동적 프로그래밍 알고리즘입니다. 각 단계에서 현재 부분 배열을 확장할지 새로 시작할지를 결정하여 탐욕적 원리와 DP를 결합합니다. 주식 수익 최적화, 신호 처리, DP 최적화 기법 이해에 필수적입니다.

목표 금액을 만드는 데 필요한 최소 동전 개수를 찾는 고전적인 DP 문제입니다. 더 작은 금액으로부터 솔루션을 구축하여 최적 부분 구조를 보여줍니다. 화폐 시스템, 자동 판매기, 자원 할당의 실용적 응용이 있습니다. 변형으로는 거스름돈을 만드는 모든 가능한 방법의 수를 세는 것이 있습니다.

2D 동적 프로그래밍을 사용하여 문자열을 회문으로 분할하는 데 필요한 최소 컷을 찾습니다. 먼저 O(n²)로 회문 테이블을 구축한 다음 최소 컷을 계산합니다. 텍스트 처리, 문자열 최적화, 여러 단계가 있는 복잡한 DP 시연의 응용이 있습니다. 문자열 조작 문제에서 최적 부분 구조를 보여줍니다.