배낭 문제가 뭔지 잘 모른다면 이 글을 읽고 오자! 🔍 배낭 문제에서 넣은 물건을 어떻게 찾을까?보통 배낭 문제에서는 어떤 물건을 넣었는지 보다는 가치의 최댓값을 물어보기 때문에, 해당 방식을 무조건 알지 않아도 된다고 생각한다.하지만 내가 풀지 못했던 코딩테스트 문제에서는 내 생각에는 넣은 물건을 알아야 문제를 풀 수 있었다. 따라서 배낭 문제에서 넣은 물건을 찾는 방법에 대해 추가로 글을 작성하게 됐다. ▶️ 넣은 물건을 찾는 방법바로 선택된 물건을 역추적 하면 된다.설명을 위해 이전 포스팅에서 사용한 그림을 그대로 가져왔다.아래 예제의 경우에는 마지막 값인 가치의 최댓값이 14이다.즉, 선택된 물건을 찾기 위해서는 14를 만든 물건을 역추적 하면 된다. 무게가 7일 때, 최댓값이 14이므로, ..
먼저, 많은 알고리즘 중 배낭 문제를 꼽은 이유는 다음과 같다... 최근에 응시한 코테에 나왔는데 풀지 못했다. 문제를 보자마자 배낭 문제라는 것을 알았고, 심지어 DP 문제라는 것도 알았다. 하지만 1차원 배열을 써야 하는지, 2차원 배열을 써야하는지 상세한 풀이 방법이 생각나지 않았다.대충, 점화식의 형태도 기억이 났지만, 결과적으로는 풀지 못했다. 그래서 다시 한 번 공부를 하면서, 다음 번에는 꼭 한 번에 풀 수 있도록 하고자 한다. 🔍 배낭 문제란?배낭 문제는 유한한 용량을 가진 배낭과 여러 개의 물건들이 주어졌을 때, 배낭에 담을 수 있는 물건들의 조합을 찾아 그 가치의 합이 최대가 되도록 하는 문제이다. 각 물건은 고유한 가치와 무게를 가지며, 물건을 쪼개서 넣을 수 없다는 제약(0-1 ..
코딩테스트 문제를 풀 때, 입력의 크기 n에 대해 시간초과가 나지 않도록 알고리즘을 고려해야 한다.이 사실을 알고 있지만, 항상 특정 시간복잡도에 대해 n의 크기를 어느정도까지 가져갈 수 있는지를 까먹어 해당 글을 작성하게 됐다. 1️⃣ 입력의 크기에 따른 시간복잡도입력의 크기시간복잡도대표 알고리즘n \[O(n!)\]완전탐색n \[O(2^n)O(n^2*2^n)\]Bitmask DPn \[O(\sqrt{2}^n)\]MITMn \[O(n^3)\]Matrix Chain Multiplication(행렬 곱셈)n \[O(n^2)\] n \[O(n\sqrt{n})O(n\log^{2}n)\]모스(Mo's) 알고리즘n \[O(n\log n)\]정렬, LIS(최장 증가 부분 수열)n \[O(n)\]DP, DFS, Tre..
해당 글에서는 입국심사 문제를 Python을 이용해 풀이하고자 한다. 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 🔷 문제 설명더보기이 문제는 이분탐색에 관련된 문제다.코딩테스트를 보기에 앞서 평소에 이분탐색 문제인 것을 알아내는데 어려움을 느껴 연습하는 시간을 가지고자 해당 문제를 풀게 됐다. 🔷 문제 풀이만약 이 문제가 이분탐색인 문제라는 걸 몰랐다면 어떻게 접근했어야 할까?이분탐색이라는 것의 힌트는 바로 입력의 크기이다. 해당 문제에서 입국심사를 기다리는 사람의 최댓값과 한 명을 심사하는데 걸리는 최대 시간은 1,000,000,000이다. 따라서 ..
