[알고리즘-공부] 1.알고리즘의 첫걸음(2)

1.3 동전 거스름돈 : 그리디(Greedy) 알고리즘 -> 4장에서 설명!

동전 거스름돈 문제를 해결하는 알고리즘은 남은 거스름돈 액수를 넘지 않는 한도에서 가장 큰 액면의 동전을 계속하여 선택하는 것이다.

 

1.4 한붓그리기 : 오일러 서킷(Euler Circuit)

알고리즘의 핵심은 현재 점에서 다음으로 이동 가능한 점을 선택할 때에는 반드시 현재 점으로 돌아오는 사이클이 존재하여야 한다는 것이다. (한 점을 여러번 방문 할 수 있다.)

한붓그리기?? 한붓그리기는 연결되어 있는 선이 홀수개인 점이 아예 없거나 두 개만 있는 도형 위에서만 가능하다.

 

1.5 미로 찾기 : 오른손 법칙

현 위치에서 한 방향을 선택하고, 벽에 오른손을 댄다. 그리고 출구가 나올 때까지 계속 오른손을 벽에서 떼지 않고 걸어간다.

 

1.6 가짜 동전 찾기 : 분할 정복(Divide-and-Conquer) -> 3장에서 설명!

동전 더비를 반으로 분할하여 저울에 달고, 가짜 동전이 있는 더비를 계속해서 반으로 나누어 저울에 단다. 이는 분할 정복 알고리즘의 일종이다.

 

1.7 독이 든 술단지 : 2진코드

2진수(bit)를 이용하여 해결한다. 최소의 희생자 수 = 0, 최대 희생자 수 이다.

 

ex) 4개의 술단지 중 1개의 단지에만 독이 들어다. 최소의 사람을 이용하여 독이든 술단지를 찾아보자. (단, 이 독을 먹으면 일주일 후에 죽는다.)

 

 

방법)

(1) 먼저 술단지의 개수를 2진수로 표기하여 각 비트당 1명의 신하를 할당한다.

(2) 그런 후 각 신하들는 자신이 할당 받은 비트가 1인 단지들을 모두 맛보게 한다.

 

결과) 위에 상황은 4가지의 결과를 도출할 수 있다.

- 아무도 시음하지 않은 단지에 독이 있다면, 일주일 후에 두 신하 모두 살아남는다.

- A가 혼자 시음한 단지에 독이 있다면, 일주일 후에 A만 죽는다.

- B가 혼자 시음한 단지에 독이 있다면, 일주일 후에 B만 죽는다.

- A,B 둘다 시음한 단지에 독이 있다면, 일주일 후에 A,B 둘다 죽는다.

 

출처 : [알기쉬운 알고리즘-양성봉] 전공책입니다.