배낭 문제, 왜 대표 DP일까
배낭 문제가 왜 대표 DP 예제인지 쉽게 설명합니다. 0/1 Knapsack에서 상태 정의, 점화식, 1차원 최적화와 완전 배낭과의 차이까지 코딩테스트 기준으로 정리합니다.
-
-
LIS는 왜 이분 탐색으로 풀릴까: 가장 긴 증가 부분 수열을 DP보다 빠르게 이해하는 법
LIS를 쉽게 설명합니다. 가장 긴 증가 부분 수열 문제에서 왜 이분 탐색이 등장하는지, DP와 무엇이 다르고 tails 배열이 어떤 의미인지 코딩테스트 기준으로 정리합니다.
-
플로이드 워셜 알고리즘 정리: 다익스트라와 무엇이 다를까
플로이드 워셜을 쉽게 설명합니다. 모든 정점 쌍 최단거리 문제에서 왜 다익스트라와 다르게 생각해야 하는지 코딩테스트 기준으로 정리합니다.
-
비트마스킹 입문: 코딩테스트에서 언제 써야 할까
비트마스킹을 쉽게 설명합니다. 부분집합, 방문 상태, 토글 문제에서 왜 비트로 상태를 표현하는지, 코딩테스트 기준으로 정리합니다.
-
구간 업데이트 문제 풀이: 차분 배열을 왜 알아야 할까
차분 배열을 쉽게 설명합니다. 누적합만으로는 부족한 구간 업데이트 문제에서 왜 difference array가 필요한지, 실제로 어떻게 동작하는지 코딩테스트 기준으로 정리합니다.
-
순서 제약 문제 풀이: 위상 정렬을 언제 써야 할까
위상 정렬을 쉽게 설명합니다. 선수 과목, 작업 순서처럼 순서 제약이 있는 문제에서 언제 떠올려야 하는지 코딩테스트 기준으로 정리합니다.
