안녕하세요

저자님의 책을 보고 공부하던중 질문이 있어 왔습니다.

혹시 "알고리즘 문제해결전략"으로 공부하시는 분들 있으면
제가 모르는 부분에 대해서 좀 알고계시지 않을까 생각이 들어 질문을 올리게 됐네요.

2문제가 좀 이해가 안가는데요.

질문1) 사탕배분 문제(p30)

//문제:30개의 사탕을 3명한테 분배하는 방법
(각 사탕의 무게는 20이하의 정수로 하며 사탕의 개수는 n<=30)

질문1과 관련하여 게시판내의 관련 질문들을 모두 봤습니다만
풀리지 않는 점이 있어서 질문좀 드리려 합니다.

일단 저자님께서 경우의 수를 줄여나가는 과정을 추적해보면

과정1)3^30(가장 기본적인 사탕분배 방법)

과정2-1)위의 과정중 모든 사탕의 무게가 같은 단순한 입력이 있다고 가정하며(총량이 중복이 되는 경우에 해당) , 여기서 더 세분화하여 배분하는 모든 사탕의 무게는 각 20이라 가정.

과정2-2) 또한 배분하는 사탕의 개수는 30개라 가정

과정3)위의 과정2를 고려할 경우 세명의 아이가 받을 수 있는 사탕의 총무게합(량)의 Maximum(최대치)한도 값은
최댓값이 20*30 = 600

음...일단 여기까지를 보겠습니
다.
여기서 일단 질문이 하나 있는데요

아래는 저의 생각입니다.

과정 3)에서 3명의 아이가 받을 수 있는 사탕의 총 무게합이 600입니다
그러면 아이들이 차례로 c1 , c2 , c3이라고 하면

각 어린이가 받은 사탕 총량이 같은 경우는..

한가지 예를 들때(만약 무게합이600이라 가정)

c1이 받는 사탕의 무게합이 600이라하면 c2 ,c3은 모두 0
c2가 받는 사탕의 무게합이 600이라면 c1 , c3은 모두 0
c3이 받는 사탕의 무게합이 600이라면 c1 , c2는 모두 0

이렇게 되어야 하는데

저자님의 방법대로 하면

600* 600* 600=약 2억

이므로

한명의 어린이가 동시에 취할 수 있는 무게값이 모두
(0~600)값이 나올 수 있다는 의미가 됩니다.

그러면 이럴경우 모든 어린이 c1,c2,c3가 600의 값을 갖는다고 했을 때
사탕의 총합은 1800이 나옵니다.

즉 2억가지의 경우의 수에 합이 최대 1800까지 되는 경우가 있다는 말이 되는데 이럴 경우 경우의 수를 너무 부풀리게 되는게 아닌가 싶습니다.

좀더 깊이 파면 이 경우 전체 총량의 합의 경우가

600을넘어서
0<총량<1800까지 될 수가 있게되는데

그러면 601<=총량<=1800의 나올 수 없는 총량의 경우까지

2억가지에 포함이 되어, 이거는 실제 나 올 수 있는 경우의 수보다 너무 많은 경우를 포함시킨게 아닌가 하는 생각이 드네요..

아무리 어림을 잡는다고 해도 그렇습니다.

제 생각대로라면

만약 한 아이가 무게가 600이라면
전체 총량의 경우는 600이하로 한정을 시켜서
(600 , 0 , 0)
(0 , 600 , 0)
(0 , 0 ,600)
(580 , 20 , 0)
(580 , 0 ,20)
(0 , 580 ,20)
(20 , 580 , 0)
...

이런식으로 해서

합이 600이하로 유지가 되게 해야 되는게 아닌가 싶습니다..

일단 여기까지 한 후

아래로 내려가면

과정 4)
-1)"사탕총량의 최대치와 최소치가 20 이상 차이가 난다고 가정해봅시 다사탕의 최대무게는 20이므로 이때 사탕을 가장 많이 받은 어린이가 가장 적게 받은 어린이에게 사탕을 하나 준다고 해도 사탕의 총량은 역전되지 않습니다.
-2)그러면 최대치와 최소치의 차이는 항상 감소하며, 따라서 차이가 20이상인 경우는 최적의 답이 될 수 없나는 것을 알 수 있지요 따라서 넉넉잡아도 사탕을 가장 많이 받은 어린이가 220넘게 사탕을 받는 경우는 무시해도 됩니다"

라는 문구가 있습니다.

이 문장을 어떻게 이해를 해야될지요...
통째로 이해가 안갑니다. ㅡㅡ;

즉, 위의 과정4에서 말하는 사탕 총량이라는게..

전체 총량에서 아이3명중 각각1명의 어린이가 가질 수있는 사탕의 총량을 말하는것이고 ,

그중(전체총량 중)에서 가장 많은 총량을 가진 어린이의 총량을 최대치라 하고

가장 적은 총량을 가진 어린이의 총량을 최소치라고 이해를 해야되는지요?? 그리고 그 최대치와 최소치의 차이가 20이라는 걸의미하는건지요..?

이것좀 쉽게 풀이 해 주실 수 있는 분좀 계실까요...

마지막으로..

질문2)
p37에 격자문제에 질문이 있습니다.
이 문제는 클릭 수를 최소화해서 (5*5)격자의 모든 칸에 있는 불을 끄는 문제입니다.

여기는 1곳이 이해가 안가는데요.

p38 아래에서 13번째줄을 보면

"그림2.3(c)에서 칸 c를 클릭할지 생각해 봅시다. c를 클릭하면 a의 불이 꺼질텐데, 우리는 항상 왼쪽 위에서부터 순서대로 클릭하기 때문에 앞으로는 저 불을 다시 켤 수가 없습니다. 따라서 c는 클릭해선 안되는 칸이죠. 반면 d를 클릭하지 않고 넘어가면 이제 b를 다시는 켤 수 없기 때문에 , d는 반드시 클릭해야하지요"

이렇게 문장이 있는데 지금 이문제에서는 불을 "끄는것"이 목표 입니다.
만약 위의 문장대로 할 시 그림2.3에서 c칸은 불이 영구적으로 켜져있게 됩니다.

즉 불을 "키는 것"이 목표가 되버리는데 이걸 어떻게 생각해야될지요.. ??

휴.. 좀 질문이 많네요...

질문들 중에서 알고 계시는것 몇개만이라도 답변 주셔도 감사드리겠습니다.

여기에 시간을 너무 많이 쏟다보니까 하루가고 또 하루가 가버렸네요..ㅡ; 비효율 적인거 알면서도 내가 왜 이정도도 이해못하나 하는 오기때문에;;

참 공부하다보니 프로그래밍 분야 특히

알고리즘 이런분야는 진짜 어느정도 재능을 타고나야되는건가...

하는 생각도 들고...

다른 분들은 이정도 문제는 그냥 쉽게 쉽게 이해하고 넘어가는데

저만 이렇게 한두문제 들고 오래 걸리나 이런 생각도 들고...

아무튼 추운 겨울 모두 감기 조심하셔요.~!