프로그램을 배웠으나 알고리즘 시험을 봐야 한다면. #22

초급 알고리즘 책이라면 뒤편에 조금 설명되어 있지만

알고리즘 대회에서는 가장 중요한 것이 Dynamic Program (동적계획법, 동적프로그램, DP) 입니다.

 

완전탐색에 비해 성능차이가 어마어마 하게 많이 나지요. 물론 효율적이고, 알아야 대회를 나갈 수 있습니다.

하지만 간단한 문제는 꼭 DP로 풀지 않고 완전탐색으로 풀수 있으면 충분한 경우도 있습니다.

(실행시간은 더 걸리겠지만)

 

당신은 S사에 입사해서 신입사원입니다.

 

1. 아래 링크의 오른쪽 그림과 같은 배낭(요즘 용어로 백팩)을 가지고 출장을 가려고 합니다.

   https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

   15Kg을 담을 수 있는 가방에 최대한 넣을 수 있는 가장 큰 금액은 얼마인가?

 

2. 갯수가 1개씩이 아니고 여려개가 있을때는 가장 큰 금액은 얼마인가?

 

배낭문제는 대표적인 DP 문제이지만 DP로 풀지 말고 완전탐색으로 풀라고 하는 것입니다.

이런 문제를 딱보고 DP네 하고 쉽게 정석인 DP로 풀수 있으면 제 강좌를 읽기에는 본인 수준이 좀 높은 것이에요.

 

몇회의 강좌 동안 하고 싶었던 말은 이미 알고 있는 많은 문제들도 완전탐색으로 풀어보자 입니다.

 

언제인가 말했던 것 처럼 한동안 모든 문제를 완전탐색으로 풀면 세상이 완전탐색으로 보이고

다 이렇게 풀 수 있을 것 같은 착각이 들지만 계산해보면 실제 이렇게 풀 수 있는 문제는

입력조건이 아주 제한적일 때만 입니다.

 

이걸 느낄때까지 완전탐색으로 하다가 DP로 넘어가야 합니다.

 

#삼성_소프트웨어_역량_테스트