Introduction to Computer Algorithms

알고리즘이란 무엇일까?

알고리즘의 정의는 다양하다. 컴퓨터 용어가 아닌 의미의 알고리즘도 정의가 다양할 뿐더러, 컴퓨터공학 내에서 알고리즘의 정의도 다양하다. 다음은 컴퓨터학에서 쓰이는 알고리즘의 다양한 정의의 두 가지 예이다.

몇 개의 값 혹은 값들의 집합을 input 으로 가지고 몇 개의 값 혹은 값드의 집합을 output 으로 도출하는 컴퓨터적 수행 절차. 

입력값을 출력값으로 변환하는 컴퓨터적 단계의 순서 

이를 보고 내 나름대로 알고리즘에 대한 정의를 내려 보았다. 

아하, 컴퓨터 알고리즘이란, 인풋(입력값)을 가지고 컴퓨터가 이해할 수 있는 방식으로 인풋을 가공한 다음에 아웃풋(출력값)을 내는, 일종의 함수같은 것이구나

내가 내린 정의인 만큼, 틀릴 가능성은 열어 두어야 겠다. 이번 학기가 끝나고 이 글을 다시 열어 보았을 땐, 위 정의에 조금 더 살을 붙일 수 있었으면 하는 바람이 있다. 

---

인풋을 가지고 아웃풋을 만드는 알고리즘. 이 알고리즘이란 놈은 좀 까다로워서, 다음 세 가지 조건을 지켜줄 것을 프로그래머들에게 요구한다. 

1. 유한성(Finiteness)
2. 효율성(Effectiveness)
3. 범위성(?)(Scalability)

유한성 조건은 자명해서 설명할 필요가 있나 싶다. 우리가 알고리즘을 구현하는 목적은 간단하다. 바로 원하는 출력값(아웃풋)을 얻기 위해서이다. 그런데 영원히 값은 안주고 실행만 하고 있는 알고리즘을 상상해 보자. 이는 사실상 알고리즘을 작성하지 않은 것이나 마찬가지이다. (우리 인생에서도 "시간 안에" 끝내야 의미가 있는 것들이 많다.) 

효율성이라는 것은, 알고리즘은 결국 사람이 작성해야 하고, 사람이 읽어야 하며 사람이 이해해서 컴퓨터에 명령을 내리는 것이다. 따라서 컴퓨터와 사람 모두가 명확하게 이해할 수 있게끔 아주 간단하고 쉽게 쓰여져야 한다. 만약 알고리즘이 이진수 기계어로 작성되어 있다고 가정해 보자. 이를 사람이 이해할 수 있을까? 

범위성, 사실 이 세 가지 조건 중, 개발자에게 가장 중요한 조건은 이 범위성/범주성이 아닐까 싶다. 이는 곧 알고리즘은 "큰 범위"의 인풋에도 동작해야 함을 의미한다. 예를 들어 보자.

1부터 5까지의 합을 계산하는 알고리즘을 짜시오. 라고 한다면 혹자는 

1+2+3+4+5 = 15 이런 알고리즘을 생각할 것이다. 그런데 이는 인풋이 1부터 5까의 합을 다루는 한 가지의 경우에만 사용할 수 있다. 

만약 이를 확장시켜서, 1부터 10000까지의 합을 계산하는 알고리즘을 짜라고 한다면, 위 알고리즘은 사용할 수 없다. 

또 이런 경우도 생각해 보자. 

5초 안에 아웃풋을 내야 하는 알고리즘을 작성해야 한다. 1부터 100까지의 값을 처리할 때는 5초 이하로 처리할 수 있지만, 100을 초과하면 5초 안에 아웃풋을 낼 수 없다. -> 이 경우 인풋의 최대값은 100이다. 좋은 개발자라면, 응당 효율적인 알고리즘을 구현함으로써 제한 시간 내에 처리할 수 있는 인풋의 scale 을 넓혀야 한다.

---

지금까지 알고리즘이란 무엇이며, 알고리즘이라는 까다로운 녀석이 제시하는 조건 3가지에 대해 알아 보았다. 지금부터는 그렇다면 어떻게 알고리즘을 작성할 수 있는지 대략적인 가이드라인을 그려보도록 하겠다. (사실 상식적인 선에서 스스로 생각해 볼 수도 있는 것 같다)

 

1. 문제 정확히 이해하기 

우리 학교 교수님께서 쓰신 책에 나오는 프로그래밍 격언에 이런 말이 적혀 있었다. "1분 생각하고 하루종일 코딩하지 말고, 1시간 생각하고 1시간 코딩해라" 이 말인 즉슨, 문제를 똑바로 읽고 해석해야 샛길로 빠지지 않고, 그로 인한 헛수고를 막을 수 있다는 것 아닐까? 문제를 읽을 때는 꼼꼼히 읽는 것이 기본이고, 더 나아가 생각해 봐야 하는 것이 하나 있다. 바로 edge case 에 대해서 생각해 보는 것이다. 앞서 알고리즘은 가능한 한 넓은 범위의 인풋을 다뤄야 한다고 했다. 이때 null, 0 과 같이 (수학으로 치자면 특이점) 일반적이지 않은 인풋에 대해서도 동작할 수 있게끔 알고리즘을 설계하는 것이 중요하다. 이러한 edge case 를 고려하지 않고 알고리즘을 작성했다가, 해당 인풋을 처리하지 못해 대대적인 수정을 거치는 불상사를 막기 위해 문제 이해 단계에서 이런 edge case 를 넣어 예를 들어보는 태도가 바람직하다. 

 

2. "알고리즘 설계 전 정해야 하는 것들" 을 정하기 

문제를 깊이 있게 이해했다면, 다음으로 알고리즘 설계의 방향을 잡는 것이 필요하다. 학부생 레벨에서 고려해야 하는 것은 Exact 알고리즘으로 풀 문제이냐 approximation 으로 풀 문제이냐를 결정하는 것과 어떤 자료 구조를 만들어 자료를 관리할 것인가와 그리디, 동적 계획법 등 어떤 테크닉으로 알고리즘을 구성할 것이냐 이 세 가지 정도인 것 같다. (좀 더 깊은 레벨로 들어가면, 알고리즘을 수행하는 컴퓨터가 병렬 컴퓨팅을 지원하는지 여부도 고려할 사항이 된다.) 그 중 이 강의에서 핵심적으로 다룰 내용이 바로 세 번째, 어떤 알고리즘 테크닉(알고리즘을 효율적으로 작성할 수 있게 해주는 논리)으로 알고리즘을 작성할 것인가? 하는 문제이다. 

 

3. 알고리즘 검증하기

문제를 잘 읽고, 가능한 모든 케이스에 대해서 동작하며 적절한 자료구조와 알고리즘 기술을 사용해 알고리즘을 다 작성했다면, 이 알고리즘이 과연 유한한 시간 내에 모든 합법적 인풋에 대해 원하는 결과를 도출하는지 시험해 보아야 한다. 

---

지금까지 배운 내용을 종합해서 예시를 분석해 보자. 

굉장히 많은 pots 가 있다. 그리고 각 pot 은 고유 넘버를 가지고 있다. 이때, 10,000 이 쓰여 있는 pot 을 가장 빠르게 찾을 수 있는 알고리즘은 무엇일까?

먼저 가장 직관적인 방법은 linear search 이다. 이 경우, 총 n 개의 pot 이 주어졌다고 가정할 때, 10,000 이 쓰여있는 pot 이 배열의 마지막 요소에 들어 있다면, 이 pot 을 찾는 데 총 n 번의 탐색이 필요하다. 

두 번째 방법은 binary search 이다.

def binarysearch (target, pots)
	start = 0
    end = len(pots)-1
    while start <= end:
    	mid = (start+end)//2
        if target == pots[mid]:
        	return mid
        elif target < pots[mid]:
        	end = mid - 1
        else:
        	start = mid + 1
    return None

위 알고리즘은 파이썬으로 작성된 binary search 알고리즘이다. 먼저 인풋값은 두 개로, 찾고자 하는 Pot 의 번호를 의미하는 target 과 pot 들이 들어 있는 배열, pots 가 있다. 
start 는 pots 배열의 첫 번째 요소의 인덱스이고 end 는 배열의 마지막 요소의 인덱스이다. 
start 와 end 가 같거나, 교차될 때까지 반복문을 돌릴 것이다. 
mid 는 배열의 중간 요소의 인덱스이며 start 와 end 를 더한 뒤 2를 나눔으로써 구해진다. 그리고 이 mid 는 while 문 한 바퀴를 돌고 나면, 새로운 값으로 갱신되어 새로운 mid 를 찾는다. 언제까지? start > end 가 되는 순간 전까지!
이렇게 mid 인덱스를 구하고 나면, 총 3가지 케이스가 있을 수 있다. 그 mid 에 있는 값, 다시 말해 pots[mid] 가 우리가 찾고자 하는 target 과 같은 경우, target 보다 큰 경우, target 보다 작은 경우.
먼저 첫 번째 경우는 쉽다. 우리가 찾는 그 값을 드디어 찾았으니, 그 값을 return 시키고 함수를 종료시키면 된다. 
두 번째 경우, 즉 우리가 찾는 값이 중간값보다 더 왼쪽에 있다? 그러면 그 값은, start 부터 중간값 하나 전까지, 그 사이 어딘가에 놓여 있다는 말이 되니, end 의 범위를 mid - 1 로 수정해 주면 된다. 
세 번째 경우는 두 번째 경우를 뒤집기만 하면 되어 설명 생략. 
만약 start > end 가 되도록 반복문을 돌았는데, target 과 일치하는 값을 찾지 못했다면? 해당 배열에 target 이 아예 없다는 뜻이다. 이럴 경우를 대비해, whlie 문이 다 끝난 뒤에 아무 수확이 없다면 None 을 리턴 시켜주면 된다. 

이 방법을 사용하면 linear search 와 비교했을 때 어떤 점이 좋을까? 바로 탐색 횟수가 현저히 줄어든다는 것이다. 예를 들어보자. 만약 총 32개의 pot 이 있다고 하자. 이 경우 최악의 경우 발생하는 연산 횟수는 몇 번일까? 이 경우 최악의 경우가 발생할 땐, 찾고자 하는 요소가 배열의 맨 앞이나 맨 뒤에 있는 경우이다. 

찾고자 하는 요소가 맨 앞에 있다고 가정해 보자.

1. start = 0, end = 31 (32)

mid = 31/2 = 15

2. start = 0, end = 14 (15)

mid = 14/2 = 7

3. start = 0 end = 6 (8)

mid = 6/2 = 3

4. start = 0 end = 2

mid = 2/2 = 1

5. start = 0 end = 0

mid = 0/2 = 0

pots[mid] = target => return pots[mid]

 

총 5번의 반복 끝에 원하는 값을 찾아 리턴시켰다. 최악의 경우에도 32번이 아닌, 5번만에 문제를 해결할 수 있다니! 얼마나 효율적인가! 이 차이는 n 값이 커질수록 더 극명하게 나타난다. 총 길이 n 인 배열이 인풋으로 주어진다고 했을 때, Linear Search 의 경우 최대 n 번의 search 를 해야 하고, Binary Search 의 경우 최대 log2n번의 search 를 해야 한다. 

---

두 번째 예시는 피보나치 수열에 관한 것이다. 

피보나치 수열을 수식으로 정리해 보면 다음과 같이 쓸 수 있다. 

Fn = {
if n > 1
	Fn-1 + Fn-2
if n = 0
    0
if n = 1
    1
}

이를 글로 묘사하면, n 이 0 과 1일 때는, 각각 자기 자신을 반환하지만, n 이 1 보다 커지면, Fn 은 그 Fn-1 과 Fn-2 의 합이 된다. 

이 피보나치 수열을 코드로 구현해 보자. 먼저 재귀적인 알고리즘 technique 으로 구현해 본다면 다음과 같이 구현할 수 있을 것이다. 

def fib1(n):
	if n==0 or n==1:
    	return n
    else:
    	return fib1(n-1)+fib1(n-2)

이 경우는 최악의 경우 그런 것은 없다. 그저 n 에 비례해서 더 많은 더하기 연산을 재귀적으로 수행해야 한다. 자료구조를 수강한 사람이라면 알겠지만, 재귀의 구조는 기본적으로 트리 구조이다. 즉 위 코드는 트리 구조로 재현해 볼 수 있는데, 이를 그림으로 나타내면 아래와 같다. 

그렇다면 F(n) 을 구하기 위해 몇 번의 재귀호출이 필요할까? 위 트리 구조에서 트리는 두 개의 자식 노드를 가지고 있으므로 약 2^n 번의 호출이 필요할 것이다. (이는 매우 가파르게 증가하는 시간 복잡도에 속한다.)

---

반면, 같은 피보나치 수열을, 반복문을 이용해서 구현해 보자. 

def fib3(n):
  a, b = 0, 1
  for i in range(0, n):
    a,b = b, a+b

  return a

파이썬은 c 언어와 달리, 동시에 두 개 이상의 값을 지정할 수 있다. 단 위 경우처럼 동시에 입력하는 값 중 전자를 후자에 넣는 경우, 즉시 반영은 되지 않는다. 따라서 b 에 넣은 a의 경우 갱신되기 전의 a값이다. 

피보나치 수열의 주 특징이라 한다면, 연속한 두 항의 합이 다음항이 된다는 것이다. 따라서 이 연속한 두 항을 설정해 주고, 이를 각각 a, b 라고 칭했다.(사실 변수 이름은 이렇게 지으면 안된다. a 를 보고 이것이 전전항을 뜻한다고 알 수 없기 때문이다.) 그 뒤 값을 갱신할 때는 전전항에는 전항의 값을, 전항에는 전전항과 전항의 합을 새롭게 써 주어야 한다. 이때 반복문의 반복이 0번 이루어지면, a 를 그대로 반환하면 되고 1번 이상 반복될 경우, 우리가 찾는 값은 a 값이 되므로, 반복문이 모두 종료된 뒤에는 a 를 리턴해주면 된다. 

이 경우 F(n)을 찾는 데는 몇 번의 search 가 필요할까? 어떠한 경우에도 반복문이 총 n 번 돌기 때문에, n 만큼의 search 로 원하는 아웃풋을 찾을 수 있게 된다. 

앞선 방법이 2^n 의 search 를 해야했던 것에 비해, 획기적으로 감소된 수치이다. 이처럼 같은 문제에 대해 같은 답을 낸다고 해도 어떤 알고리즘 테크닉을 구현하느냐에 따라 결과를 구하는 데 걸리는 시간은 천차만별이 될 수 있다.

---

마지막 세 번째 예시, Great Common Divisor 를 살펴보자. 이는 크게 세 가지 방법으로 소개할 수 있다.

가장 먼저, 이 알고리즘을 평범한 방식으로 구현한다면 다음과 같이 구현할 수 있을 것이다. 

def gcd(a, b):
  for i in range(min(a,b), 0, -1):
    if a % i == 0 and b % i == 0:
      return i

위 알고리즘은 입력받은 a 와 b 두 수 중 더 작은 값에서부터 시작하여, i 로 두 수를 나눈 나머지가 0이 되는 순간 i 를 리턴함으로써 최대공약수를 찾는 방식이다. 이 경우 a와 b 가 서로소일 때가 최악의 경우이며 이 때 총 min(a,b) 번의 search 를 해야 한다.

 

두 번째로 Factorization, 다시 말해 소인수분해를 활용하는 방법이 있다. 

a와 b 가 있을 때, 최대공약수를 구하는 방법은, 두 수를 소인수분해한 뒤 공통 인자를 찾고, 그 공통 인자의 차수 중 더 작은 차수를 가지는 인자를 모두 곱해주면 된다. 그러나 이 방법의 경우 수가 커질수록, 소인수분해를 하기 위한 시간이 급격하게 증가하므로, 배보다 배꼽이 더 커지는 결과를 초래하게 된다. 

 

마지막 세 번째 방법이 유클리드 알고리즘이라 불리는 알고리즘 테크닉을 사용하는 법이다. 

유클리드 알고리즘이란, 두 수 a와 b 가 주어지고, a >= b 일 때, a와 b 의 최대공약수는 곧 b 와 a mod b 의 최대공약수와 같다는 이론이다. 

위 이론을 사용해 알고리즘을 작성해 보면 다음과 같이 작성할 수 있다. 

def gcd(a,b):
  while b > 0:
    a, b = b, a % b
  return a;

위 알고리즘의 실행 과정을 적어보면 다음과 같다.

a = 3, b = 6 일 때

a, b = 6, 3

a, b = 3, 0

b가 0이므로 수행 종료, a 리턴. 

어떤 수와 0의 최대공약수는 그 수이니까, b 가 0이 되면 리턴하는 것이다. 

 

이때 살펴봐야할 것은 a >= b 라고 정의했기 때문에, 이를 b, a % b 로 바꾸었을 때, b >= a % b 가 보장되느냐 하는 부분일 것이다. 이는 다음과 같이 증명할 수 있다. 

b >= a/2 라고 하자. 
그렇다면 a 를 b 로 나눈 나머지는, a-b 와 같을 것이다. 그리고 b 가 a의 반보다 크거나 같기 때문에, a - b = a % b <= a/2 이다.
따라서, a%b <= b 이므로, a%b <= b 이다.
이번엔 b < a/2 라 하자. 
이때, a 를 b 로 나눈 나머지는 당연히 b 보다 작을 것이다. 즉 a % b < b < a/2 이다.
이 결과를 종합하면, b 는 언제나 a % b 보다는 크거나 같다는 것을 알 수 있으며, 
a % b 는 a/2 보다 작다는 것을 알 수 있다. 

그렇다면 이 유클리드 알고리즘을 사용했을 때, 최대공약수를 구하기 위해서는 몇 번의 search 가 필요할까? 

a 의 반보다 작은 a % b 가 두 번의 시행 뒤 a 의 자리에 온다. 즉 두 번의 시행마다 인풋이 최소 반 이하로 줄어든다. 만약 a 가 k 자리 수의 정수라고 한다면, 2번의 시행 후면 자리수가 하나 줄어든다. 따라서 최악의 경우에도, 최대 2k번의 시행 후면 원하는 결과를 얻을 수가 있다.