코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
알고리즘 — 문제 해결의 체계적 접근 → 고급 알고리즘
DP 기초에서 1D/2D 상태를 배웠습니다. 이제 더 복잡한 DP 패턴을 배웁니다.
이 레슨에서 배울 것:
1. LCS — 두 문자열의 최장 공통 부분 수열
2. 편집 거리 — 문자열 변환의 최소 비용
3. 비트마스크 DP — 부분집합 상태를 비트로 표현
4. 구간 DP — 구간을 쪼개는 최적화
5. 상태 설계 패턴 — 복잡한 문제의 상태 정의 노하우
왜 심화가 필요한가?
핵심 마인드셋: DP 심화의 핵심은 "상태를 어떻게 정의하느냐"입니다. 더 많은 정보를 상태에 넣을수록 더 복잡한 제약을 처리할 수 있습니다.
DP 기초에서 계단 오르기, 배낭 같은 1차원 2차원 문제를 풀었죠.
이번엔 한 단계 더 깊이 들어가 볼 거예요.
문자열 두 개를 동시에 다루는 LCS 패턴이 첫 번째예요.
편집 거리는 삽입 삭제 교체를 써서 문자열을 바꾸는 최소 비용이에요.
비트마스크 디피는 부분집합을 정수 하나로 표현하는 트릭이에요.
구간 디피는 구간을 어디서 자를지 결정하는 패턴이에요.
다이어그램을 보시면 다섯 가지 패턴이 나란히 있어요.
각각의 시간 복잡도가 다른 것을 확인해 보세요.
왜 심화가 필요할까요? 기초 패턴만으론 풀 수 없는 문제가 많기 때문이에요.
기초에선 인덱스 하나면 충분했는데요.
심화에선 인덱스 두 개나 비트마스크처럼 복잡한 상태가 필요해요.
아래쪽 비교 박스를 보세요.
기초 디피의 상태는 디피 아이 또는 디피 아이 더블유처럼 단순해요.
심화 디피의 상태는 비트마스크 구간 트리 노드까지 확장돼요.
결국 상태 설계가 곧 문제 해결력이라는 핵심 메시지예요.
상태를 어떻게 정의하느냐가 복잡도와 정확도를 결정해요.
이 레슨에서는 각 패턴의 핵심 아이디어를 깊이 배울 거예요.
실전에서 어떤 패턴을 써야 할지 판단하는 능력도 기를 거예요.
특히 경시대회에서 자주 나오는 패턴들이라 확실히 익혀두세요.
그럼 첫 번째 패턴인 엘시에스부터 자세히 살펴보겠습니다.