알고리즘 첫 수업 : 전체적 프리뷰

알고리즘의 유래

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

이것은 알고리즘 어원의 의미이고 최초의 알고리즘은 BC 300년 경 유클리드의 최대공약수 알고리즘으로 알려져 있다.

 

알고리즘이란

알고리즘의 의미를 챗 GPT에게 물어봤다.

Q. 알고리즘이란?
A. 알고리즘은 일련의 명확한 단계나 절차를 따라 특정한 작업을 수행하는 방법이나 규칙의 집합을 의미합니다.
이것은 컴퓨터 과학, 수학, 공학 및 다른 여러 분야에서 사용되며, 문제를 해결하거나 원하는 결과를 얻기 위한 체계적인 접근법을 제공합니다.
알고리즘은 다양한 형태로 존재할 수 있으며, 간단한 것에서 복잡한 것까지 다양합니다. 예를 들어, 수학적 알고리즘은 수학 문제를 해결하기 위한 절차를 설명하고, 컴퓨터 프로그래밍에서는 데이터 처리, 정렬, 검색 등 다양한 작업을 수행하기 위한 알고리즘이 사용됩니다.
알고리즘은 일반적으로 다음과 같은 특징을 가집니다
1. 명확성: 각 단계는 명확하게 정의되어야 하며 모호성이 없어야 합니다.
2. 유한성: 알고리즘은 유한한 시간 내에 실행을 완료해야 합니다.
3. 입력과 출력: 알고리즘은 입력을 받아서 원하는 출력을 생성하는 역할을 합니다.
4. 효율성: 가능한 한 효율적으로 작동해야 하며, 자원을 효과적으로 활용해야 합니다.
알고리즘은 컴퓨터 과학에서 특히 중요한 개념으로, 컴퓨터 프로그래밍과 데이터 처리에서 핵심 역할을 합니다.
그러나 이것은 단순히 컴퓨터 과학에 국한된 것이 아니며, 수학 문제 해결부터 현실 세계의 복잡한 문제까지 다양한 분야에서 활용됩니다.

복잡해 보이지만 이를 요약해 보면 

알고리즘은 문제를 해결하기 위한 위의 네 가지 특징을 가진 단계적 절차를 의미한다.

이제 대표적인 알고리즘 문제를 하나씩 살펴보겠다.

 

최대 숫자 찾기

Q. 10, 20, 30, 40, 50, 60 ,70 ,80이라고 쓰인 카드들 중에서 가장 큰 숫자의 카드를 찾아보자.

 

방법은 다양하겠지만 여기서 사용할 방법은 순차탐색이다.

카드를 한 장씩 차례대로 (주어진 순서대로) 읽어 가며 가장 큰 숫자를 찾는 방법이다.

 

임의의 숫자 찾기

Q. 45, 20, 60, 35, 10, 55, 90, 85, 75, 25 가 적힌 카드 중에서 85를 찾아보자.

 

최대 숫자 찾기 처럼 85를 기억하고 바닥에 펼쳐진 카드를 차례대로 한 장씩 읽으며 비교하는 것은 순차탐색이다.

만약 10장의 카드가 오름차순으로 미리 정렬되어 있다면?

이 경우 순차탐색으로 85를 찾는 것은 위로부터 8장의 카드를 읽은 후에나 찾을 수 있다.

그럼 더 효율적인 방법은 없을까?

 

카드가 오름차순으로 정렬되어 있기 때문에 중간에 있는 카드 45 (혹은 55)와 85를 먼저 비교한다.

85가 45보다 크기 때문에 45 왼쪽 카드들은 더 이상 살펴볼 필요가 없다.

그리고 또 다시 45 오른쪽 카드 중 중간의 카드를 골라 85와 비교해 나간다면 

순차 탐색보다 훨씬 빠르게 85를 찾을 수 있다.

이 방법을 이진탐색이라고 한다.

 

동전 거스름돈

Q. 물건을 사고 거스름돈을 동전으로 받야 한다. 이때 가장 적은 수의 동전을 받으려면 어떻게 해야 할까.

 

거스름돈이 730원이라면?

500원 1개, 100원 2개, 10원 3개 총 6개의 동전을 거슬러 받는 게 최선의 방법이다.

다시 한번 살펴보면 730원에 대해서

1. 500원 동전 1개 선택 - 잔액 230원

2. 100원 동전 2개 선택 - 잔액 30원

3, 10원 동전 3개 선택 - 잔액 0원

 

각 단계에서 남은 거스름돈 액수를 넘지 않는 한도에서 (욕심내어) 가장 큰 액면의 동전을 계속하여 선택하고 있다.

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

 

한 붓 그리기

한 붓 그리기 문제는 어느 한 점에서 출발해 모든 간선(edge)을 한 번만 지나서

출발점으로 돌아오되, 궤적을 그리는 동안 연필이 종이에서 떨어져서는 안 된다. 

단, 점(vertex)은 여러 번 방문해도 무방하다.

현재점에서 갈 수 있는 경로는 세 가지 9, 6, 10이다. 이 중에서 어디로 진행해야 할까?

- 점 6으로 간다면 5 - 4 - 3 - 9 - 7 - 10을 거쳐 점 1 시작점으로 돌아올 수 있다.

- 점 9로 가면 3 - 4 - 5 - 6 - 7 - 10을 거쳐 시작점으로 돌아올 수 있다. 

- 점 10으로 가면 점 1로 갈 수밖에 없고, 방문하지 못한 간선이 생긴다.

그럼 점 6과 9는 되는데 왜 10은 안 되는 것일까?

 

그 이유는 현재 점으로부터 점 6이나 점 9를 지나서 현재 점으로 돌아오는 사이클이 있다는 것이다.

이를 통해 현재 점으로 돌아오는 사이클이 있다면 진행하지만, 외길이라면 즉, 인접한 점이 하나밖에 없다면 진행하면 안 된다는 것을 알 수 있다.

즉 한붓그리기의 전제조건은 모든 vertex의 degree가 짝수면 어떻게든 시작 vertex로 돌아올 수 있는 사이클이 존재하기 때문에 모든 vertex의 degree가 짝수이어야 한다. (이를 오일러 정리 라고 한다.) (참고로 헤밀턴 정리는 모든 vertex를 방문하는 알고리즘)

 

미로 찾기

미로에 갇혔을 때 어떻게 빠져나올 수 있을까? 

- 오른손 법칙: 현 위치에서 한 방향을 선택하고, 오른손을 벽에 댄다. 그리고 출구가 나올 때까지 계속 오른손으로 벽을 짚으며 나아간다. 어떻게 오른손 법칙으로 항상 출구를 찾을 수 있는 것일까?

 

오른손 법칙으로 지나온 길을 하나씩 펼쳐보면... 시작점에서 출구까지의 일직선이 생긴다. (시간의 효율성을 보장하지 못한다. 출구를 찾는데 얼마나 걸릴지는 모르겠다...)

 

가짜 동전 찾기

아주 많은 동전 속에 1개의 가짜 동전이 있다. 이 가짜 동전은 눈으로 파악할 수 없고 다른 정상적인 동전보다 약간 가볍다.

방법 3가지를 살펴보자.

1. 동전 1개를 저울 왼편에 올리고 나머지 동전을 하나씩 오른편에 올려 비교한다.

이 방법은 운이 좋은 면 1번 만에 찾을 수 있지만 운이 나쁘다면 n-1번 해야 할 수도 있다.

 

2. 동전을 2개씩 짝을 지어 n/2 짝을 각각 저울에 달아서 가짜 동전을 찾아보자.

이는 1번 ~ n/2번으로 최악의 경우 저울 사용 횟수가 거의 1/2로 감소한다.

 

3. 동전 더미를 반으로 나눠 저울 양편에 놓아보자. 남은 동전 수는 계속 1/2로 줄어들고 나중에 2개가 남았을 때 가짜 동전을 가려낸다. 이 알고리즘은 운이 좋을 때가 없다. 왜냐하면 마지막에 가짜 동전을 찾기 때문이다.

 

만약 1024개의 동전이 있을 때 몇 번 저울에 달아야 할까?

먼저 512개씩 양쪽에.. 다음 256개.. 다음 128.. 64.... 이는 총 10번이다. 로그 1024 = 10

 

독이 든 술단지

창고에 많은 술단지가 보관되어 있다. 어느 날 이웃 스파이가 술단지 하나에 독을 탔는데 이 독은 아주 조금만 먹어도 정확히 일주일 후에 죽는 독이다.

이때 주인이 하인들에게 명하였다. 독이 든 술단지를 반드시 일주일 만에 찾아내라. 단 희생되는 하인들의 수는 가능한 줄여야 한다.

술단지의 수가 아주 적을 때에 문제의 답을 찾아서 힌트를 얻어보자.

1. 술단지가 2개 일 때

 

 

일주일 후 하인이 살아있으면 맛보지 않은 단지에 독이,

죽었으면 맛보았던 단지에 독이 있다.

 

 

2. 술단지가 4개 일 때

 

하인 2명이 각각 하나씩 시음하고 마지막 술은 두 명 동시에 맛을 보게 해 보자. 두 신하를 각각 A와 B라고 한다면,

 

 

 

1. 아무도 시음하지 않은 단지에 독이 있다면 : 둘 다 살아있다.

2. A가 시음한 단지에 독이 있다면 : A만 죽는다.

3. B가 시음한 단지에 독이 있다면 : B만 죽는다.

4. A와 B 둘 다 시음한 단지에 독이 있다면 : 둘 다 죽는다.

 

3. 술다지가 8개 일 때

즉 희생자 수는