01. 알고리즘의 첫걸음

• 알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다.

---

01. 알고리즘의 첫걸음

• 알고리즘이라는 용어는 9세기경 페르시아 수학자인 알콰리즈미(al-Khwarizmi)의 이름으로 부터 유래되었다.

  • 문제를 해결하기 위한 단계적인 절차를 의미한다.

• 1장에서는 다양한 예시를 보여준다.

---

1.1 최대 숫자 찾기

문제 : 카드 10장 중에서 가장 큰 숫자 찾기

알고리즘 : 순차 탐색(Sequential Search) == 선형 탐색(Linear Search)

• 카드를 한 장씩 차례대로 읽어가며 찾는 방식

---

1.2 임의의 숫자 찾기

문제1 : 45, 20, 60, 35, 10, 55, 90, 85, 75, 25가 적힌 카드 중에 85가 적힌 카드 찾기

• 알고리즘 : 순차 탐색

• 최대 숫자 찾기처럼 85를 기억하고 카드를 하나씩 읽으며 해당 숫자를 찾는 방식

문제2 : 위와 같은 카드가 오름차순으로 정렬되어 있을 때, 효율적으로 85가 적힌 카드를 찾기

• 알고리즘 : 이진 탐색(Binary Search)

• 중간의 카드를 읽어 85와 비교하고 85가 앞 부분에 있는지 뒷 부분에 있는지 판단하여, 반으로 나눠가면서 찾아가는 방식

• 분할 정복(Divide-and-Conquer) 알고리즘의 일종이다.

---

1.3 동전 거스름돈

문제 : 730원을 거슬러 받을 때, 가장 적은 수의 동전으로 받는 방법

• 알고리즘 : 그리디(Greedy) 알고리즘

• 남은 거스름돈 액수를 넘지 않는 한도에서 가장 큰 액면의 동전을 계속하여 선택하는 방식

---

1.4 한붓그리기

문제 : 한붓그리기의 해결 방법

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

• 오일러 서킷(Euler Circuit) 문제와 같다.

---

1.5 미로 찾기

문제 : 미로에 갇혔을 때 따로 표시를 할 수 없는 상황에서 빠져나오는 방법

• 알고리즘 : 한 방향을 선택하여, 벽에 오른손을 대고 출구가 나올 때까지 손을 떼지 않고 걸어간다.

---

1.6 가짜 동전 찾기

문제 : 동전 더미 속에 1개의 가벼운 가짜 동전이 섞여있을 때, 이를 찾아낼 수 있는 최소한의 양팔 저울 사용 횟수 찾기

• 알고리즘 : 더미를 반으로 나누어 저울에 달고, 가벼운 쪽의 더미를 계속 반으로 나누어 저울에 달아 찾아낸다.

---

1.7 독이 든 술단지

문제 : 많은 술단지 중에 눈으로 확인할 수 없는 독이 든 단지가 하나 있다. 독이 들었는지 판단하는 방법은 오직 술을 마신 사람이 일주일 후에 죽는다는 것 밖에 없을 때, 죽는 사람을 최소화하며 일주일만에 독이 든 단지를 찾아내는 방법

• 알고리즘 : 술단지를 차례로 2진법으로 표기하고, 각 비트를 사람으로 생각한다. n개의 단지가 있으면 최대 log₂n명의 사람만 죽는다.

---

보간 탐색(Interpolation Search)