어제 저를 멘붕시킨 초등 수학문제

'배낭 알고리즘'과 'NP-완전 문제'가 무슨 뜻인지 궁금해요.

대표적인 알고리즘입니다.

가령 31kg까지 담을 수 있는 가방에 금덩어리 7kg 5kg 3kg 을 몇개씩 담아야 최대한 많은 양을 담아서 갈 수 있느냐는 식의 형태가 대표적이라서 그런 이름이 붙었습니다.

짐을 나눌 수 있는 경우는 (즉, 소숫점으로 무게를 나눌 수 있다면) 그리디 알고리즘으로 O(nlogn) 이던가..? 정도 시간에 풀 수 있고 나눌 수 없으면 다항시간 내에 풀 수 없습니다.(NP-완전)

Knapsack problem 에 NP-완전 문제이므로 모든 순서쌍을 구하기 위한 dynamic solution을 사용해야 합니다.. 라고 초등 5학년이 답변하면 선생님이 멘붕이겠..죠...?

선생님 깜놀할 듯 ㅋㅋㅋ

저는 합쳐서 끝자리 3 이 나오는 8과 9의 배수 순써상을 잡고 소거했죠.
친구는 그냥 하나씩 예를 들어줬다는데 그게 분명 오학년 방법은 아닐거다 라고 합니다. 어느 쯤 과정인지는 본인도 잘 몰라요--;

제가 이야기한 해법의 공식 명칭이 그리디 알고리즘이군요. 역시 수학이란, 해법 형태에도 다 이름이 붙어있군요.

돈을 다 써야 한다고 해도 결국은 최적값을 구하는 문제죠. 나머지가 최소가 되도록 이라는 조건이고 최소는 결국 0원이니까요.

쪼갤 수 없는데 그리디 알고리즘을 썼기 때문에 운이 좋은 경우가 아니면 사용할 수 없습니다. 즉, 저 배의 값이나 사과의 값이 다른 숫자로 변하면 최적의 해를 구할 수 없는 경우가 생깁니다.

위에 제가 제일 처음 쓴 해법도 사실은 그리디 알고리즘이죠. 비싼 배를 먼저 산 다음 하나씩 버리고 나머지를 사과로 대체했으니까요. 두번째는 단지 하나는 꼭 사야한다는 조건을 붙여서 부분해의 범위를 넓힌 겁니다. 돈을 다 쓴다는 조건이 있다면 이미 사과나 배가 한개씩은 필요 (9나 8의 배수 중 83은 없으므로) 하다고 볼 수 있으니까요.

아, 그리고 그리디 알고리즘이나 Knapsack problem 을 언급한 건 답이 정해져 있어서가 아니라 답을 어떻게 빨리 찾느냐를 설명하기 위한 것입니다. 모든 경우를 다 구하거나 조합을 구해도 답은 나오는데, 그 답을 좀 더 빨리 구하는 방식이 알고리즘이라는 거죠.

여기부터 못 알아들어서 검색질 중....이지만 역시 못 알아먹고 있어요. 전 문과.