이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 알고리즘 — 문제 해결의 체계적 접근 → 알고리즘 — 문제 해결의 체계적 접근 → 고급 알고리즘
Learn advanced DP: LCS, edit distance, bitmask DP, interval DP, tree DP, probability DP, and optimization techniques.
DP 기초에서 계단 오르기, 배낭 같은 1차원 2차원 문제를 풀었죠.
이번엔 한 단계 더 깊이 들어가 볼 거예요.
문자열 두 개를 동시에 다루는 LCS 패턴이 첫 번째예요.
편집 거리는 삽입 삭제 교체를 써서 문자열을 바꾸는 최소 비용이에요.
비트마스크 디피는 부분집합을 정수 하나로 표현하는 트릭이에요.
구간 디피는 구간을 어디서 자를지 결정하는 패턴이에요.
다이어그램을 보시면 다섯 가지 패턴이 나란히 있어요.
각각의 시간 복잡도가 다른 것을 확인해 보세요.
왜 심화가 필요할까요? 기초 패턴만으론 풀 수 없는 문제가 많기 때문이에요.
기초에선 인덱스 하나면 충분했는데요.
심화에선 인덱스 두 개나 비트마스크처럼 복잡한 상태가 필요해요.
아래쪽 비교 박스를 보세요.
기초 디피의 상태는 디피 아이 또는 디피 아이 더블유처럼 단순해요.
심화 디피의 상태는 비트마스크 구간 트리 노드까지 확장돼요.
결국 상태 설계가 곧 문제 해결력이라는 핵심 메시지예요.
상태를 어떻게 정의하느냐가 복잡도와 정확도를 결정해요.
이 레슨에서는 각 패턴의 핵심 아이디어를 깊이 배울 거예요.
실전에서 어떤 패턴을 써야 할지 판단하는 능력도 기를 거예요.
특히 경시대회에서 자주 나오는 패턴들이라 확실히 익혀두세요.
그럼 첫 번째 패턴인 엘시에스부터 자세히 살펴보겠습니다.
선생님: 디피 기초와 심화의 가장 큰 차이가 뭘까요?
학생: 상태 정의가 더 복잡해지는 건가요?
선생님: 맞아요, 기초에선 인덱스 하나면 충분했는데 심화에선 두 개 이상이 필요해요.
학생: 비트마스크는 상태가 정수 하나인데 왜 복잡한 건가요?
선생님: 그 정수 안에 엔개 원소의 선택 여부가 모두 담겨 있어서 실질적으로 2의 엔승가지 상태예요.
학생: 그러면 어떤 패턴을 먼저 익히는 게 좋을까요?
선생님: 엘시에스와 편집 거리부터 시작하세요 2차원 테이블 패턴이 가장 범용적이에요.
학생: 네 그러면 엘시에스부터 집중해 볼게요.