01. 알고리즘이란?

* 해당 포스트는 PC환경에 최적화 되어있습니다.

* 쉽게 배우는 알고리즘 개정판 교재로 공부했으며 학교에서 배운 내용과 섞어서 정리한 포스트입니다.

* 저작권 문제는 hjl3066@gmail.com으로 연락주시면 빠르게 조치하겠습니다.

---

어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것을 알고리즘이라 한다.

 

입출력의 간단한 예를 보자.

• 문제 : 1000개의 무작위 정수 중 최대값 찾기
• 입력 : 1000개의 무작위 정수
• 출력 : 1000개의 무작위 정수 중 최대값
• 알고리즘 : 1000개의 무작위 정수 중 최대값을 찾는 과정

알고리즘은 특정한 문제를 위한 알고리즘을 습득하고 체계적으로 생각하는 방법을 훈련하는데 목적을 둔다.

문제 자체를 해결하는 알고리즘을 배우고 그 과정에 깃든 생각하는 방법을 배우고 미래에 다른 문제를 해결하는 생각의 기반을 제공한다.

 

알고리즘은 선행 과목으로 프로그래밍, 자료구조, 이산수학에 대한 이해를 필요로한다.

개인적인 생각이지만 기초 프로그래밍 문법과 이산수학에 대한 어느정도의 이해 정도만 가지고 있으면 알고리즘 공부에 큰 영향은 없다고 생각한다. 자료구조는 알고리즘과 같이 배워나가면 된다.

 

알고리즘의 유래

• 9세기경 근대 수학의 아버지라 불리는 페르시아의 수학자인 무하마드 이븐 무사 알-콰리즈마(al-Khwārizmī)의 이름에서 유래
• 최초의 알고리즘은 BC 300년경 유클리드(Euclid)의 최대공약수 알고리즘

유클리드의 최대 공약수 알고리즘은 2개의 자연수의 최대공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수와 같다는 성질을 이용한다.

 

유클리드 최대 공약수 알고리즘 예

24와 14의 최대공약수

E(24 - 14, 14) = E(10, 14)

E(14 - 10, 10) = E(4, 10)

E(10 - 4, 4) = E(6, 4)

E(6 - 4, 4) = E(2, 4)

E(4 - 2, 2) = E(2, 2)

= 2, 최대공약수는 2이다.

 

아래는 간단한 의사코드이다. 

//입력 : 정수 a, b(단, a>=b>=0)
//출력 : 최대공약수(a, b)
Euclid(a, b) {
    if (a==b)
	return a
    return Euclid(b, a - b)
}

재귀함수를 사용하는 간단한 코드다. 프로그래밍 문법에 대한 기본적 지식이 있다면 이해하는데 어렵지 않을 것이다.

 

나머지(modulo)를 이용하는 알고리즘도 있다.

//입력 : 정수 a, b(단, a>=b>=0)
//출력 : 최대공약수(a, b)
Euclid(a, b) {
    if (b == 0)
	return a
    return Euclid(b, a mod b)
}

알고리즘의 표현

알고리즘의 각 단계별 절차는 보통 말로 서술할 수 있으며, 일반적으로 프로그래밍 언어와 유사한 의사 코드(pseudo code)로 표현한다.

 

- 말로 표현된 최대값 찾기 알고리즘 예시

1. 첫 숫자를 보고 머릿속에 기억하기
2. 다음 숫자를 보고 그 숫자를 머릿속 숫자와 비교하기
3. 비교 후 더 큰 숫자를 기억하기
4. 다음에 읽을 숫자가 없을 때까지 2 ~ 3 반복하기
5. 최종적으로 머릿속에 기억된 숫자가 최대값임.

- 의사 코드로 표현된 최대값 찾기 알고리즘 예시

//배열 A에 입력이 10개의 숫자가 있다고 가정
max = A[0]
for i = 1 to 9 // 1 ~ 9까지 차례로 i에 대입
    if (A[i] > max)
        max = A[i]
return max

- 플로 차트(flow chart)로 표현된 최대값 찾기 알고리즘 예시

최대값 찾기에서의 알고리즘

숫자를 하나씩 비교하면서 본 숫자들 중 가장 큰 숫자를 기억한다.

마지막 숫자를 본 후에 마지막으로 기억된 숫자가 가장 큰 숫자일 것이다.

이러한 진행 방식을 가진 알고리즘을 순차탐색(Sequential Search) 알고리즘이라고 한다.

n개의 숫자 중 비교는 n - 1번 한다. 그러므로 순차탬색 알고리즘은 O(n) 알고리즘이라고 할 수 있다.

자세한건 뒤에 언급할테니 그냥 그런가보다 하고 넘어가도 무방하다.

임의의 숫자 찾기

▶ 45, 20, 60, 35, 10, 55, 90, 85, 75, 25 (무작위 순서라고 가정)

다음의 숫자 리스트에서 85를 찾아보자.

 

위에서 봤던 순차탐색 알고리즘을 이용해보자.

머릿속에 85를 기억하고 차례로 앞에서부터 하나씩 읽으며 85를 찾는다.

 

여기서 경우의 수가 3가지 있다.

1. 가장 빠르게 찾는 경우
2. 가장 늦게 찾는 경우
3. 평균

1. 가장 빠르게 찾는 경우

85가 숫자 리스트 중 가장 앞에 있을 경우 순차탐색 알고리즘에 의해 한 번에 바로 찾을 것이다.

 

2. 가장 늦게 찾는 경우

85가 숫자 리스트 중 가장 뒤에 있을 경우 순차탐색 알고리즘에 의해 가장 늦게 10번째 비교에서 찾을 것이다.

 

3. 평균적인 경우

무작위로 나열된 숫자 중 85를 찾는 순차탐색을 무수히 많이 진행하면 가장 빠르게 찾는 경우의 1번과 가장 늦게 찾는 경우인 10번의 평균인 5.5와 근사하게 나올 것이다. 그러므로 평균적인 경우 순차탐색 알고리즘에 의해 5.5번째 비교에서 찾을 것이다.

 

알고리즘의 성능에서 가장 빠르게 찾는 경우 즉 최상의 결과는 배제한다고 보면 된다. 아무리 운이 좋아 한 번에 찾더라도 그 뒤의 실행에서도 알고리즘의 성능을 지속해서 보장할 수 없기 때문이다. 그렇기에 앞으로 우리는 순차탐색 알고리즘뿐만이 아닌 다른 알고리즘에 대해 알아볼 때도 최악의 결과와 평균적인 결과를 주의깊게 살펴볼 것이다.

가짜 동전 찾기 알고리즘

1. 많은 동전 더미 속에 1개의 가짜 동전이 섞여 있다.
2. 가짜 동전은 매우 정교하여 눈으로 식별할 수 없다.
3. 가짜 동전은 정상적인 동전보다 약간 가볍다.
4. 양팔 저울만을 사용하여 가짜 동전을 찾아내야 한다.(단, 저울에 동전을 다는 횟수를 최소화한다.)

생각 1. 임의의 동전 1개를 저울 왼편에 올리고, 나머지 동전을 하나씩 오른편에 올려서 가짜 동전을 찾아보자.

 → 운이 좋으면 한 번에 찾겠지만 최악의 경우에는 (n - 1)번만에 찾을 것이다.

 

생각 2. 동전을 2개씩 짝지어 놓고, 각각 저울에 달아서 가짜 동전을 찾아보자.

 → 운이 좋으면 한 번에 찾겠지만 최악의 경우에는 n/2번만에 찾을 것이다.

 → 생각 1보다는 효율적이지만 여전히 최악의 경우엔 많은 비교를 해야하는 비효율적인 생각이다.

 

생각 3. 동전 더미를 정확히 반으로 나누어 저울 양편에 놓으면 어떨까?

 → 더 가벼운 동전 더미에 가짜 동전이 속해있을 것이다.

 → 더 가벼운 동전 더미를 다시 정확히 반으로 나누어 저울로 비교한다.

 → 계속 반복하여 분할된 더미의 동전 수가 1개씩이 될 때, 가벼운 쪽의 동전이 가짜이다.

 → 생각 1과 생각 2와 달리 운에 맡기지 않는다. 무조건 마지막에 가서 가짜 동전을 찾기 때문이다.

 → 무조건 n개의 동전에 대해서 log₂n번만에 찾을 것이다.

 ▶ 생각 1, 생각 2와 달리 생각 3은 무수히 반복되거나 인간의 상상을 벗어날 정도로 큰 수를 상대로 훨씬 유리하다.

 

독이든 술 단지 알고리즘

1. 술을 매우 좋아하는 한 임금이 있다.
2. 이웃 나라의 스파이가 술 창고에 들어가서 술 단지 하나에 독을 넣고 붙잡혔다.
3. 스파이는 하나의 단지에만 독을 넣었다고 실토하고 숨을 거두었다.
4. 독은 무색무취이며, 술을 아주 조금만 맛 보아도 정확히 24시간 후에 죽는다.
5. 임금은 독이 든 술 단지를 반드시 24시간 안에 찾으라고 신하에게 명하였다.
6. 투입되는 신하의 수를 최소화하여 독이 든 술 단지를 찾아라. 술 단지는 1,000개이다.

문제가 크다면 작은 문제부터 시작하여 패턴을 찾아내면서 일반적인 규칙을 찾아봐야한다.

 

2개의 술 단지 중 1개의 술 단지에 독이 있다면?

 → 신하 1명을 투입하여 술 단지 하나를 맛보고 죽는지 사는지 확인한다.

 

4개의 술 단지 중 1개의 술 단지에 독이 있다면?

생각 1. 신하 3명을 투입하여 술 단지를 각각 하나씩 맛보고 죽는지 사는지 확인한다.

생각 2. 신하 2명을 투입하여 술 단지를 각각 하나씩 맛보고 시음하지 않는 2개의 단지 중 하나를 두 신하에게 동시에 맛보게 한다.

 → 아무도 시음하지 않은 단지에 독이 있다면, 24시간 후 두 신하 모두 살아있다.

 → A신하가 혼자 시음한 단지에 독이 있다면, 24시간 후 A신하는 죽을 것이다.

 → B신하가 혼자 시음한 단지에 독이 있아면, 24시간 후 B신하는 죽을 것이다.

 → A, B신하 모두 시음한 단지에 독이 있다면, 24시간 후 A, B신하는 죽을 것이다.

 

 ▶ 생각 1은 신하 3명을 투입하였다. 생각 2는 신하 2명을 투입하였다. 생각 2가 더 효율적이다.

 

그렇다면, 각 단지에 2진수를 0부터 부여하고, 각 신하가 술 맛을 보면 1, 안보면 0으로 하여 아래와 같이 짝지어 보자.

2² = 4, 2명의 신하로 4개까지 찾을 수 있다.

 

8개의 술 단지 중 1개의 술 단지에 독이 있다면?

2³ = 8, 3명의 신하로 8개까지 찾을 수 있다.

 

6만개의 술 단지 중 1개의 술 단지에 독이 있다면?

2¹⁵ = 32,768

2¹⁶ = 65,536

 → 16명의 신하로 찾을 수 있다.

 

n개의 술 단지 중 1개의 술 단지에 독이 있다면?

2³ = 8, log₂8 = 3

 → 투입되는 신하의 수는 log₂n명이다.

 

큰 문제를 작은 문제로 줄여서 최선의 해결 방법으로 패턴을 찾아서 알고리즘으로 만들 수 있다.