배낭 문제는 정해진 비용 내에서 최적의 가치를 갖는 해를 찾는 문제다. 처음 이 문제를 접하는 사람들 대부분이 그리디로 접근하지만 그리디 알고리즘만으로는 해결할 수 없는 배낭 문제도 있다. 배낭 문제는 크게 두 유형으로 분류되는데 먼저 그리디 알고리즘을 적용할 수 있는 분할 가능한 배낭 문제와 그리디 알고리즘으로는 해결하기 어려운 0-1 배낭 문제가 있다. 1. 분할 가능한 배낭 문제 분할 가능한 배낭 문제는 말 그대로 가치와 비용을 분할해 가져올 수 있다. 예를 들어 10kg의 제한을 두고 배낭을 싸는데 5kg에 75의 가치를 가진 A와 4kg에 120의 가치를 가진 B, 7kg에 140의 가치를 가진 C가 있다고 해보자. 여기서 A, B, C 모두 원하는 만큼 쪼개서 가져갈 수 있는 물건이라고 가정하..

이진 탐색은 배열 속에 내가 원하는 자료가 있는지 찾는 방법이다. 탐색 구간을 둘로 나누어 실행하며 이를 반복해나가기 때문에 이진 탐색이라고 부른다. 책을 펼쳐서 내가 원하는 페이지를 찾는 과정과 아주 비슷하다. 우선 길이가 10인 arr이라는 배열이 아래와 같이 있다고 해보자. 배열이 정렬되어있지 않기 때문에 내가 원하는 값이 어디에 어떤 규칙으로 있는지 알 수 없다. 이 배열에서 자료를 찾으려면 앞에서부터 순차적으로 찾아야 한다. 이걸 선형 탐색(Linear Search)라고 한다. 8을 찾는다면 적당히 5번의 비교로 끝나겠지만 5를 찾는 경우 최악의 상황으로 배열 내 모든 데이터를 확인해야 한다. 따라서 이 방법은 시간 복잡도가 O(n)이다. 사실 이 정도의 시간복잡도가 그리 나쁘지는 않지만 배열의..

BFS는 그래프나 트리의 자료구조에 적용할 수 있는 맹목적 탐색 알고리즘이다. 맹목적 탐색은 주어진 정보에 따라 효율적인 탐색을 실시하는 것이 아닌 이미 정해진 순서로 탐색을 실시하는 방법으로 실용적으로 따져볼 때 매우 비효율적인 알고리즘이지만 구현이 쉽고 간단한 문제에 한해 아주 유용하다. 이름 그대로 트리에서 노드를 깊게 파고드는 것보다 한 계층을 순차적으로 모두 살펴보는 것을 우선하는 알고리즘이다. BFS는 Queue로 구현할 수 있다. 1. 탐색을 시작할 정점을 Queue에 삽입한다. 2. Queue가 비었다면 '9'로 이동한다. 3. Queue의 가장 위에 있는 정점이 현재 탐색 중인 정점이다. 4. 탐색 중인 정점이 찾으려는 자료이면 '8'로 이동한다. 5. 탐색 중인 정점과 연결된 정점을 Q..