Computer Science/알고리즘

[알고리즘] Knapsack Problem(배낭 문제)

2023.03.15

정의 Knapsack Problem은 일정 무게를 담을 수 있는 배낭 안에 담을 수 있는 물건의 총량을 최적화 하는 문제이다. 배낭의 크기, 물건의 개수, 각 물건의 무게와 가치가 주어질 때, 배낭에 넣을 수 있는 물건들의 가치가 최대가 되게 하는 조합을 찾는 문제이다. Knapsack Problem은 크게 0-1 Knapsack Problem과 Fractional Knapsack Problem으로 나뉜다. Knapsack Problem의 예제는 백준 문제 12865번. 평범한 배낭 문제를 풀었다. 0-1 Knapsack Problem 물건을 쪼개 배낭에 넣을 수 없을 때, 각 물건을 배낭에 넣을 지 말지 결정하는 문제. Dynamic Programming으로 문제를 해결할 수 있다. 접근 방식 Data..

[알고리즘] 이분탐색(Binary Search)

2023.03.15

개인의 짧은 식견으로 작성했으니, 많은 조언 부탁드립니다. 설명 이분탐색은 기본적으로 Array와 같은 자료 구조에서 특정 값을 찾아낼 때 쓰인다. 찾고자 하는 값과, 현재 보고 있는 값을 비교하여 왼쪽과 오른쪽으로 탐색 범위를 쪼개 다시 탐색하는 과정을 거친다. 보고 있는 값과 찾고자 하는 값의 대소관계가 분명해야 하기 때문에, 이분 탐색을 사용하기 위해서는 배열이 정렬되어 있어야 한다. 한번 탐색마다 탐색 범위를 반으로 축소하기 때문에(left or right), O(nlogn)의 TC를 갖는다. 사용처 배열 속의 특정 값을 찾고자 할 때. 배열의 값들을 활용하여 찾아야 할 값에 특정 범위 내의 최적해를 찾을 때. Code 가장 기본적인 이분탐색 코드는 다음과 같다. ```cpp #include #i..

[알고리즘] Knapsack Problem(배낭 문제)

[알고리즘] 이분탐색(Binary Search)

티스토리툴바