[알고리듬] #5 사칙연산문제(3)

[key word] 카슈미르 동굴, 탐색, 가지치기, 무작위법

파이썬 실습창을 열 수 있습니다.

실습창 열기

알면 재미있고, 모르면 재미 없습니다.

모르는데 모르고 지나가면 쓸쓸하고,

아는데 더 잘 알면 신이 납니다.

그런데,

모르는데 도전해서 알게 되면 끝내(?) 줍니다.

 

1. 복잡한 계산

1-1. 차(tea)의 무게

험난한 차마고도(茶馬古道, 차를 운반하는 길)를 따라 중국의 차를 인도 등의 나라로 운반하는 카라반(caravane, 상인의 무리)이 있습니다. 카라반의 말 한 마리는 60kg의 차를 싣고 이동합니다.

차 잎을 7매를 한 묶음으로 하여, 말 등의 좌우에 각각 12묶음씩, 합하여 총 24묶음을 매달아서 이동합니다.

그러므로 차 잎 1매의 무게는 357g이 됩니다.
보이차(普洱茶, 푸얼차)의 무게 단위가 1매에 357g인 것은 이러한 전통 때문입니다.

 

357 그램은 어떻게 계산하여 나왔을까요?

계산식을 보여주세요. 1kg은 1000g입니다.

print(60*1000//(7*24))

'''
말등에는 60*1000 그램의 차를 실었습니다. 단위를 주의하여야 합니다.
말등에 실은 전체 차의 매수는 7*24 입니다. 7매짜리 묶음이 24개입니다. 
24는 문제에 이미 있으므로 12*2 등의 식을 사용하지 않아도 됩니다.
말등에 실은 무게를 7*24 로 나누면 차 한 매의 무게가 나옵니다.

그런데 /를 사용하여 계산하면 357.142857143 입니다.
한 매의 무게가 357그램인 것은 소수 이하를 버림하였기 때문일 것입니다.
그래서 나눗셈 연산자를 // 로 바꾸어 계산하였습니다.

너무 쉬웠습니까?
좋습니다.
다음 문제는 좀 더 복잡한 것을 내어볼께요.

'''

 

1-2. 언니의 푸념

지갑에 1000원 밖에 남지 않았다고 언니가 푸념을 합니다.
백화점에서 가진 돈의 반으로 모자를 사고, 모금함에 2000원을 넣고,
식당에서 남은 돈의 반으로 점심을 먹고, 나와서 1000원 주고 커피 마시고,
서점에서 남은 돈의 반으로 책 한 권 사고, 3000원 짜리 아이스크림 먹고,
1000원으로 차비 하여 집에 왔답니다.
언니가 처음에 가지고 있던 돈은 얼마일까요?

• 푸념: 마음에 품은 불평을 함부로 퍼부어 말하는 것.

어때요? 이제 문제가 마음에 드나요?

print((((1000+1000+3000)*2+1000)*2+2000)*2)

'''
답은 48000원입니다.

복잡하지요? 내가 봐도 목잡합니다.
그런데 조금 귀찮기는(?) 해도 거꾸로(역순으로) 차례차례 추적하면 될것 같습니다.

현재의 돈                        
===> 1000

차비를 사용하기 전에는 얼마?     
===> 1000+1000

아이스크림을 사 먹기 전에는?     
===> 1000+1000+3000

책을 사기 전에는 얼마?  (지금 돈의 2배)
===> (1000+1000+3000)*2   

커피를 마시기 전에는?
===> (1000+1000+3000)*2+1000

점심 먹기 전에는?
===> ((1000+1000+3000)*2+1000)*2

모금함에 넣기 전에는?
===> ((1000+1000+3000)*2+1000)*2+2000

모자를 사기 전에는?
===> (((1000+1000+3000)*2+1000)*2+2000)*2

위의 식을 print()의 괄호 속에 넣어서 출력합니다.

식을 점점 확장했습니다. 
할 만 하지요?

'''

2.   카슈미르 동굴

2030년 어느 날,

지구 정복을 노리는 외계인들이 거미줄처럼 동굴이 얽혀 있는 카슈미르 동굴에 숨어들었습니다. 지구 방위대 사령관인 당신은 즉시 로봇 '다보아'를 출동시켜 동굴을 정찰하도록 했습니다. '다보아'는 최단 경로로 입구에서 출구로 나가기만 하면 구석구석 살피지 않아도 동굴 내부의 사정을 다 알 수 있습니다.

 

'다보아'가 입구인 1번으로 들어가서 출구인 37번으로 나오는 가장 짧은 길을 찾아 보세요.

물론 화살표 방향으로만 갈 수 있습니다.

 

카슈미르에 있는 데오사이 평원

카슈미르는 파키스탄과 인도 사이에 있는 아름다운 지역입니다.

동굴이 많은 산, 깊은 계곡, 더 넓은 평원, 그림 같은 호수가 어우러져 있습니다. 

 

1 --> 4 --> 6 --> 13 --> 10 --> 15 --> 22 --> 31 --> 27 --> 28 --> 29 --> 30 --> 36 -- 37

 

쉽지 않습니다.

그렇다면 길을 찾은 사람은 인간이 아닐까요?

아뇨. 길을 쉽게 찾던데요.

그 사람은 길을 거꾸로 찾았습니다.

 

그 사람은 길을 이렇게 찾았습니다.

출구인 37번은 36번에서 올 수 있다.

36번은 30번에서 올 수 있다.

30번은 29, 29는 28, ...., 4번은 1번.

그러므로 1번에서 시작하면,

1 --> 4 --> --> 6 ....................... 30 --> 36 --> 37

 

거꾸로 생각하는 것이 비결이었습니다.

 

[참고]

이 문제를 해결하기 위하여 시도할 수 있는 몇가지 방법들을 생각하여 봅시다.

1. 깊이 우선 탐색(DFS)

1번에서 갈 수 있는 곳은 3번과 4번이다. 먼저 3번으로 간다.

3번에서는 9번, 9번에서는 12와 21이 있는데 먼저 12번-->8번 --> 14번. 막혔다.

막히면 한 단계 되돌아 가서 같은 과정을 반복한다.(이것을 backtracking이라 한다)

결국은 길을 찾을 수 있을 것이다.

많은 사람들이 이 방법으로 접근한다.

 

2. 너비 우선탐색(BFS)

종이를 꺼내어 놓고 입구가 1이므로 1을 적는다.       종이에 1

종이의 1을 지우고 종이의 다른 곳에 1을 적는다.

그리고 1에서 갈 수 있는 곳은 3과 4이므로  1을 지운 곳의 1 다음에 3, 4를 적는다.        종이에 1, 3, 4

3을 지우고 다른 곳 1을 적은 다음에 3을 적는다. 3에서 갈 수 있는 곳인 9를 맨 뒤에 적는다. 종이에 1, 3, 4, 9

이런 과정을 반복하여 37을 만나면 다른 곳에 적은 순서가 우리가 찾는 경로가 된다.

 

3. 가지치기(pruning)

길찾기 진행 중에 어떤 번호를 만났는데 그 번호로 진행하면 길이 없다는 것을 알고 있다면 그 길로 가지 않는다.

 

4. 무작위법(heuristic-random) 

길만 있으면 이리저리 다녀본다.

운이 좋으면 길을 찾을 수 있고, 운이 없으면 계속 헤멜 수도 있다,

이것을  링반데룽(ringwanderung)이라 한다.

 

모두가 좋은 방법입니다.

문제에 따라 적절한 해결책이 될 수 있습니다.

.

그렇다면 우리가 사용한 거꾸로 진행하여 문제를 해결하는 방법을  무엇이라고 할까요?

넓은 의미에서 역발상(관점의 변화, perspective shift ) 또는 되짚기?

적절한 이름이 생각나시는 분은 댓글 부탁드립니다.

오늘도 수고하셨습니다.

끝.