들어가며 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence; LIS)은 DP로 풀 수 있는 유명한 문제 유형 중 하나입니다. 문제의 핵심은 주어진 시퀀스에서 오름차순으로 정렬된 가능한 가장 긴 부분 수열을 찾는 것 입니다. 참고로 답이 되는 부분 수열은 꼭 하나가 아니라 여러 개가 될 수도 있습니다. 이 문제를 푸는 방법은 크게 두 가지가 알려져 있습니다. DP로만 풀기 와 DP + 이분탐색으로 풀기 입니다. 각각 O(n²)와 O(n log(n))의 시간복잡도를 가집니다. n이 작으면 전자의 방법으로도 충분할 수 있지만 n이 더 커지면 힘들겠죠. 풀어볼 문제는 가장 긴 증가하는 부분 수열5 입니다. 문제는 아주 짧고 명확합니다. 예를 들어 수열 A가 A = {10,

들어가며 배낭 문제(Knapsack Problem)는 조합 최적화 문제의 기본적인 문제 유형으로 동적 계획법(DP)을 이용해 풀 수 있습니다. 코딩 테스트에서 배낭 문제 혹은 냅색이라고 하면 바로 이 유형이구나 생각하면 됩니다. 배낭 문제의 핵심은 각각 가중치(Weight)와 가치(Value)를 가진 집합이 주어졌을 때, 총 가중치의 한계 내에서 유지하면서 총 가치가 가장 커질 수 있도록 어떤 원소를 포함시킬 것인지 결정하는 것 입니다. 쉽게 말해 10kg 용량 배낭에 [5kg, 5만원, 신발], [6kg, 4만원, 패딩], [4kg, 3만원, 속옷]이 있을 때 어떤 것들을 가져가야 용량에 넘치지 않으면서 최대 가치를 챙길 수 있는지 찾는 것입니다. 위 예시에서는 신발과 속옷을 챙기는 것이 8만원으로

외판원 문제란? 외판원 문제(Traveling Salesman Problem; TSP)는 컴퓨터 과학 및 수학 분야에서 잘 알려진 조합 최적화 문제입니다. 이 문제의 핵심은 주어진 각 도시(노드)를 정확히 한 번만 방문하고 시작 도시로 돌아가는 가능한 최단 경로를 찾는 것 입니다. 이때, A도시에서 B도시로 가는 거리(d)는 가중치가 존재합니다. 문제의 경우에 따라서 시작점으로 돌아가지 않을 수도 있는데, 이 제약 조건이 없다고 해도 계산 복잡도는 변하지 않습니다. 어쨌든 TSP는 대표적인 NP-난해(NP-hard) 문제로 모든 문제에 대해서 다항식 시간에 해결할 수 있는 알려진 알고리즘은 없습니다. 대신 작은 N의 경우(일반적으로 N ≤ 16) 에는 분기한정법(Branch and Bound; B&B