산타는 없다

설명 분할정복법은 큰 문제를 더 이상 나눌 수 없을 때까지 분할한 후 다시 합치면서 문제를 해결하는 방법입니다. 풀이 순서 1. 큰 문제를 둘 이상의 작은 문제로 분할한다. 2. 더 작은 문제로 나눌 수 없을때까지 분할한다. 3. 더이상 작은 문제로 나눌수 없다면 다시 합치면서 문제를 해결한다. 이렇게 되어있는 풀이 순서를 제 나름대로 제귀 함수를 쓴다 가정했을 때 풀이순서를 1. Input값을 둘 이상의 범위로 나눈다. 2. 나눈 범위를 제귀 함수의 매개변수로 넣어 반복 실행한다. 3. 입력받은 범위가 0이거나 1일때 반환처리를 한다. 4. 반환받은 값으로 문제를 해결하고 반환한다. 값들이 반환되면서 해답이 나오게 된다. 위와 같이 정리하였습니다. 응용 알고리즘 퀵 정렬 병합 정렬 이분 탐색 쿼드 트리..

물건을 최대 K 만큼 버틸 수 있는 배낭에 가장 가치가 높도록 물건을 구성했을때 가치의 최댓값을 구하는 알고리즘입니다. 그리드 알고리즘으론 정확한 답을 찾을 수 없어 동적 계획법으로 풀이하여야 합니다. 그리드 알고리즘으로 풀이를 할 경우엔 가장 높은 가치 순으로 탐색을 하였을 때 결과값 보다 더 높은 경우가 발생할 가능성이 있기 때문입니다. 따라서 동적 계획법으로 풀어야하는데 동적 계획법의 진행은 i번째 물건을 j무게까지 담을 수 있을 때 최댓값을 넣어 가면서 진행합니다. 그렇게 진행하면 물건이 중복되지 않고 무게를 갱신해 가면서 진행할 수 있습니다. 문제 출처 - 백준 12865번 평범한 배낭 무게 가치 6 13 4 8 3 6 5 12 위 물건들을 최대 무게 7 까지 버틸 수 있는 가방에 넣을 때 DP..