<알기쉬운 알고리즘> Chapter1 - 알고리즘의 첫걸음

1.1 최대 숫자 찾기 

 

카드 10장이 바닥에 펼쳐져 있을 때, 

가장 큰 숫자가 적힌 카드를 찾는 한가지 방법은 카드의 숫자를 하나씩 비교하면서 

본 숫자들 중에서 가장 큿 숫자를 기억해가며 진행하는 방법일 것이다. 

 

-> 이렇게 찾는 방법을 순차탐색 (Sequential Search)라고 한다. 즉, 카드를 한장씩 차례대로 (주어진 순서대로) 

읽어가며 찾는 것이다. 

 

 

 

 

 

1.2 임의의 숫자 찾기 

 

만약 카드가 15,20,25,35,45,55,60,75,85,90 일때 85를 순차탐색으로 찾을 경우 앞쪽에 있는 8장의 카드를 읽은 후에나 85를 찾는다 

 

-> 오름차순으로 정렬된 데이터를 반으로 나누고, 나누어진 반을 다시 반으로 나누고, 이과정을 반복하여 원하는 데이터를 찾는 탐색 알고리즘을 이진탐색(Binary Search)이라고 한다. 

 

*이진 탐색(Binary Search)란: 정렬된 데이터에 대해서 중간에 있는 데이터를 비교하여 그 결과에 따라 같으면 탐색을 마치고, 다르면 작은 데이터가 있는 쪽 또는 큰 데이터가 있는 쪽을 같은 방식으로 탐색한다. 

 

 

 

 

 

1.3 동전거스름돈 

 

물건을 사고 거스름돈을 동적으로 받아야 한다면 대부분의 경우 가장 적은 수의 동전을 받기를 원한다 

거스름돈이 730원이라면 거스름돈에 대해서 가장 큰 액면의 동전부터 차례로 고려한다.  500원짜리 동전 1개, 100원짜리 동전 2개, 10원짜리 동전 3개인 총 6개를 거슬러 받으면 거스름돈 730원에 대한 최소 동전수가 된다.

 

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

이런 종류의 알고리즘을 그리디(Greedy)알고리즘 이라고 한다. 

 

 

 

 

 

1.4 한붓 그리기 

 

 

  Eulerian trail(circuit) 혹은 Euler Path 라고 불리며 우리나라에서는 한 붓 그리기 라고 불리는 이것은 그래프의 어느 한 점에서 출발하여 모든 선분을 한번만 지나서 출발 점으로 돌아오되 궤적을 그리는 동안 펜이 종이에서 떨어져서는 안된다. 단, 한 점을 여러차례 방문해도 좋다. 

 

어떻게 한붓 그리기를 해결 할까?

-> 이 질문에 대한 답은 현재점으로부터 진행하고자 하는 점을 지나서 현재 점으로 돌아오는 사이클을 찾는 것이다. 즉, 현재 점에서 다음으로 이동 가능한 점을 선택할 때에는 반드시 현재 점으로 돌아오는 사이클이 존재 하여야 한다. 

 

 

 

 

 

 

 

1.5 미로 찾기 

 

미로찾기의 해결 

 

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

 

 

 

 

 

 

 

1.6 가짜 동전 찾기 

 

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

 

 

 

 

 

1.7 독이 든 술단지 

 

어느 나라에 술을 좋아하는 임금님이 있었다. 어느날 스파이가 임금님의 술단지 중 하나에 독을 넣었다. 독은 조금만 맛보아도 정확히 일주일 뒤에 죽는 것었다. 임금님은 신하에게 먹고 일주일 만에 찾아내라고 하였다. 

문제는 이용하는 신하의 수를  최대한 줄이는 것이다. (신하가 몇 명 없다고 생각하고 풀기)

 

 

-> 각 단지를 2진수의 수로 0부터 부여하고, 각 비트를 신하에게 할당하는 것이다 

예를 들어 4개의 단지라고 한다면 생성되는 수는 0,1,2,3 이어야 하고 2진수로  00 , 01 , 10 , 11 로 표현된다. 

 

 각 비트가 2개이니 신하 A,B 두명이 각 비트를 담당하고 비트의 수가 1 일때 술을 먹는다.  

  0   0         0   1         1   0         1   1  

  x    x         x   A        B   x         A   B

 

1주일 뒤에 A만 죽는다면 01 의 술단지에 독이 

1주일 뒤에 B만 죽는다면 10 의 술단지에 독이 

1주일 뒤에 A,B 둘다  죽는다면 11 의 술단지에 독이 

1주일 뒤에 아무도 죽지 않는다면 00 의 술단지에 독이 든 것이다. 

 

이렇게 한다면 8개의 술단지를 확인하고자 한다면 3개의 비트가 생길 것이니 3명의 신하 A,B,C 로 확인 할 수 있다. 

0	0	0

 

0	0	1
		C

 

0	1	0
	B

 

0	1	1
	B	C

 

1	0	0
A

 

1	0	1
A		C

 

1	1	0
A	B

 

1	1	1
A	B	C

 

 

1주일 뒤에 A만 죽는다면 100 의 술단지에 독이

1주일 뒤에 B만 죽는다면 010 의 술단지에 독이 

1주일 뒤에 C만 죽는다면 001 의 술단지에 독이

1주일 뒤에 A,B 둘다  죽는다면 110 의 술단지에 독이 

1주일 뒤에 B,C 둘다 죽는다면 011 의 술단지에 독이 

1주일 뒤에 A,C 둘다  죽는다면 101 의 술단지에 독이 

1주일 뒤에 A,B,C 셋 다 죽는다면 111 의 술단지에 독이 

1주일 뒤에 아무도 죽지 않는다면 000 의 술단지에 독이 든 것이다. 

 

일반적으로  n 개의 단지가 있으면  밑이 2인 log(n) 명의 신하를 시음하게 하면 된다 

일주일 후에 반드시 독이 든 술단지를 찾을 수 있고, 최소 희생자 수는 0명 최대 는 신하의 수만큼이 된다.