알고리즘 들어가기

알고리즘이란 문제를 해결하기 위한 단계적인 절차를 의미한다.

주어진 문제에 여러 종류의 알고리즘이 있을 수 있으나, 보다 효율적인 알고리즘을 고안하는 것이 매우 중요하다.

 

1. 최대 숫자 찾기

mission: 다음 카드들 중에 가장 큰 숫자를 찾는다.

- 순차 탐색 (Sequential Search)

카드를 한 장씩 차례대로 읽어 가며 찾는 방법이다.

 

2. 임의의 숫자 찾기

mission: 다음 카드들 중에 임의의 숫자(ex. 85)를 찾는다.

- 순차 탐색 (Sequential Search)

- 이진 탐색 (Binary Search)

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

 

3. 동전 거스름돈

mission: 거스름돈을 동전으로 줄 때, 가장 적은 수의 동전을 준다.

- 그리디 알고리즘 (Greedy Algorithm)

greedy는 '탐욕스러운'이라는 뜻이다.

여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

 

4. 한붓그리기

mission: 종이에서 연필을 떼지 않고 한붓그리기를 한다.

한붓그리기는 그래프의 어느 한 점에서 출발하여 모든 선분을 한 번만 지나서 출발점으로 돌아오되, 궤적을 그리는 동안 연필이 종이에서 떨어져서는 안 된다. 단, 점은 여러 차례 방문하여도 괜찮다.

solution: 현재 점으로부터 진행하고자 하는 점을 지나서 현재 점으로 돌아오는 사이클을 찾는다.

 

5. 미로 찾기

solution: 오른손 법칙

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

알고리즘으로 출구를 찾아 나아가는 궤적을 점선으로 나타냈다.

 

6. 가짜 동전 찾기

mission: 아주 많은 동전 더미 속에 1개의 가짜 동전이 섞여있다. 가짜 동전은 눈으로 식별할 수 없지만, 정상적인 동전보다 약간 가볍다. 양판 저울만 사용하여 가짜 동전을 찾되, 가능한 한 저울에 동전을 다는 횟수를 줄여야 한다.

 

solution1: 임의의 동전 1개를 저울 왼편에 올리고, 나머지 동전을 하나씩 오른편에 올려서 가려낸다. -> 1번~(n-1)번

solution2: 동전을 2개씩 짝을 지어, n/2 짝을 각각 저울에 달아서 가짜 동전을 찾는다. -> 1번~n/2번

solution3: 동전 더미를 반으로 나누어 저울 양편에 달고, 가벼운 쪽의 더미를 계속 반으로 나누어 저울에 단다. 분할된 더미의 동전 수가 1개씩이면, 마지막으로 저울을 달아 가벼운 쪽의 동전이 가짜임을 찾아낸다. -> log₂n번

solution3이 이진 탐색을 이용한 방법으로, 세 가지 중 가장 효율적이다.

 

7. 독이 든 술단지

mission: 희생되는 신하의 수를 최대한 줄이면서 독이 든 술단지를 찾는다.

solution: 각 단지에 2진수를 0부터 부여하고, 각 신하가 술맛을 보면 1, 안 보면 0으로 하여 단지와 신하를 짝짓는다.

단지 수가 n일 때, 희생자 수는 0~log2₂n명이다.

 

[참고] 알기 쉬운 알고리즘