calendar2 님의 블로그

개념배낭에 담을 수 있는 최대 용량이 있고, 각 물건들의 용량과 가치가 존재할 때 배낭에 담을 수 있는 최대 가치를 찾는 알고리즘기본적으로 DP 개념 응용0-1 배낭 알고리즘은 물건을 쪼갤 수 없는 상태에서의 알고리즘 풀이2차원 DP일반적인 1차원 배열의 dp가 아닌 2차원 배열로 값을 저장해야 한다.col은 배낭의 최대 무게, row는 n번째 물건으로 지정한다.각 row, col 인덱스에 저장되는 값은 j 무게까지 담을 수 있을 때 i번째 물건을 고려했을 때 얻을 수 있는 최대 가치DP 안에 DPDP 문제답게 재귀성이 존재한다. 그래서 로직을 다음과 같이 바라보는 것이 중요하다고 생각한다.최대 무게 6kg까지 수용할 수 있는 배낭에 물건을 담아 최대 가치를 찾는다.첫 번째 물건이 3kg, 4달러라면 이..

개념구간 내 절반을 잘라가면서 값을 찾아나가는 탐색 방법시간복잡도O(log N)전제 조건탐색하는 범위가 정렬되어 있어야 한다메커니즘탐색 범위내의 배열의 중간인덱스를 구한다.중간 인덱스의 값과 key값을 비교한다.값이 중간 값보다 작다면 왼쪽 부분을, 값이 중간 보다 크다면 오른쪽 부분을 탐색하고, 같다면 해당 인덱스를 반환한다.세부적인 탐색 방법정확한 key 값 찾기상한 값 찾기하한 값 찾기정확한 key 값 찾기이름 그대로 key 값과 정확하게 일치하는 값을 찾는 경우이다.예를 들면, [1, 2, 3, 4, 5] 중에서 3을 찾는 경우 이 방식을 사용한다.코드로 구현하면 다음과 같다.static int binarySearch(int[] arr, int key) { int left = 0; in..