Algorithms | Harvard CS 50 Week 0

 

모든 내용은 하버드의 CS50 수업을 한글로 정리한것입니다.

 

다시 처음으로 돌아가서, 1과 0, binary bits로 우리는 컴퓨터가 알아들을 수 있도록 input과 output을 나타낼 수 있게 되었다. 그게 색깔이 될수도, 숫자, 알파벳, 한글, 음악, 이미지 또는 영상이 될 수 있다. 그렇다면, 이것들을 처리하는것은 무엇인가?

 

 바로 알고리즘이다.

 

Contacts

핸드폰의 전화번호찾는 Contacts기능을 생각해보자. 한글 또는 영문 순서대로 이름이 정렬되어있고, 각각의 이름에는 전화번호와 또다른 저장된 정보들을 볼 수 있다. 예전에는 어땠을까? 어렸을때 기억을 해보면 전화번호부라는것을 사용해서 번호를 찾았었던적이 있었다 (지금도 상호명등을 볼 수 있는 전화본호부가 존재하는것으로 보인다).

전화번호를 열고, 아빠, 고모 또는 할아버지 이름을 찾기도 했었는데, 어떤 방식으로 빠르게 찾았었을까? 그 방식이 바로 알고리즘이다.

정말 단순한 방법, 또는 알고리즘은 맨처음 페이지를 열고 한토시도 빠지지 않고 읽어나가면서 한장한장 넘기게 되면, 언젠가는 가족의 이름에 도달한다. 하지만 이는 정말 비효율적인 방법인데다가, 우리 가족은 성이 '천'씨 여서, 전화번호부의 후반부에 가서야 찾을 수 있다. 이 방법은 책의 부피(페이지양)에 따라서 문제를 푸는 시간도 증가한다. 

이 알고리즘은 위와같이 빨간선으로 나타낼 수 있다. 우리의 시간은 문제의 크기가 증가할때마다 linear하게, 즉 지속적으로 증가한다. 여기서 n은 문제의 사이즈를 나타내는데, 여기서는 n pages, 즉 전화번호부의 페이지수에 해당한다. 우리는 이 문제를 풀기 위해 최대 n번의 넘김을 해야할수 있기 때문이다.

 

한장씩 넘기는것은 역시 느리다. 그리고 천씨가 아닌 '나'씨, '김'씨에게는 비효율적인 방법이다. 그렇다면 두장씩 넘기면서 어떨까? 속도가 빠르긴 하겠지만, 어쩌면 우리가 찾는 페이지를 지나쳐버릴수도 있다. 만약 알파벳 또는 한글 순서를 인식하고, 지나쳤다는것을 인식하고 뒷장으로 돌아가는 방식의 알고리즘으로 해결한다면, 이전에 한장씩 넘기던 알고리즘보다 2배 빠르게 처리할 수 있다. 

같은양이라면, 1/2로 시간을 단축할 수 있다.

이 두번째 알고리즘을 나타내면 위와같이 노란색 선으로 나타낼 수 있다. 첫번째 알고리즘보다 거의 2배 빠르게 처리할 수 있기 때문에, 총 n/2회의 시도를 통해서 해결할 수 있다.

 

더 나은 알고리즘은 없을까? 책의 중간부분을 열고, 순서를 생각해서 아직 앞쪽이라면 남아있는 부분의 중간을 열고, 혹시 지나쳤다면 중간부터 지금지점까지를 여는식으로 계속 반절씩 쪼개나가서 찾는것은 어떨까? 이런 방식으로 접근하는것이 가능한것은, 우리가 전화번호부가 이미 정렬이 되어있다는것을 알기 때문이다. 찾고자 하는 이름을 알때까지 해당하는 부분의 반절부분으로 가서 나누고 나누는 방식으로 찾아낼 수 있다. (이 알고리즘을 강의중 직접 전화번호부를 찢어가면서 보여주는 부분이 굉장히 인상적이다).

이 알고리즘을 그래프로 나타내면 위와 같다. 계속 1/2씩 나누어서 찾아내기때문에, 문제가 n이라고 하면, $log_2 n$의 시도 끝에 문제를 처리할 수 있다.

 

사실 이것보다 더 좋은 방식은, 첫 Index(목록)을 보고, ㅊ이 어디서부터 시작하는지 확인한 후, 그곳에서 'ㅓ'의 위치를 대충 알고 있으면(모음중 세번째이기때문에 ㅊ의 전화번호부 섹션에서 앞쪽에 있을것이다), '처'를 찾을 수 있고, 이후 '천'을 만들기 위해 조금만 찾아보면 된다. 이미 습득해온 지식으로 '처'씨나 '챠'씨등이 없는것을 알고있는것들도 도움이 된다. 이렇게 최적화된 알고리즘을 우리는 생활속에서 습득하고 써오고 있다.

 

 

Reference