<컴퓨팅 사고> 알고리즘

* 알고리즘

 - 지난 강의에서 컴퓨터가 이해할 수 있는 2진법으로 숫자뿐만아니라 글자나 색 등을 입력할 수 있음을 배웠다. 우리는 이러한 입력을 통해 원하는 출력(output)을 얻기를 원한다. 이 때 input을 output으로 만드는 일련의 과정을 알고리즘이라 한다.

  - 즉 알고리즘은 우리의 명령을 수행하는 규칙들을 나열한 것과 같다. 하지만 규칙을 어떻게 나열하느냐에 따라 다양한 알고리즘이 존재할 수 있다. 그리고 같은 결과가 나오더라도 얼마나 짧은 시간이 걸리는지, 얼마나 정확한지 그리고 얼마나 효율적인지도 다를 것이다.

 

* 정확한 알고리즘

 - 요즘은 보기 힘들지만 책으로 된 1,000페이지의 전화번호부가 있다고 가정하자. 여기서 윤해리를 찾는 작업을 해보자.

 

 - 우리는 첫페이지부터 한 장씩 넘겨가면서 윤해리의 번호가 나올 때까지 책장을 넘길 수 있다. 매우 오래 걸리는 작업이지만 이 알고리즘은 매우 정확하다.

 

 - 위의 방식은 너무 오래걸리므로 두 장씩 넘겨보자. 그러면 말그대로 속도가 2배가 될 것이다. 물론 두 장씩 넘기다가 윤해리가 있는 페이지를 넘길 수 있어서 정확도가 떨어진다고 생각할 수 있지만 이는 특정 상황에서 이전 페이지를 확인한다는 작업만 넣으면 된다.

 

 - 위 두 알고리즘은 매우 정확하지만 시간이 매우 오래걸리므로 효율적이지 않다.

 

* 정확하고 효율적인 알고리즘

 - 위와 달리 더 효율적으로 전화번호부를 찾아보자.

 

 - 가장 먼저 1,000페이지 짜리 전화번호부의 절반을 펼친다. 전화번호부는 이름이 가나다 순으로 나열되어 있다. 따라서 펼친 페이지에 윤해리가 없다면 앞부분일지 뒷부분일지 알 수 있다.

 

 - 우리는 위의 결과로 전화번호부의 절반이 필요없어지고, 나머지 절반에서 또 절반을 펼쳐서 위와 같은 작업을 반복한다.

 - 계속 절반을 펼쳐가다보면 결국 한페이지가 남게된다.

 

 - 위와 같은 알고리즘은 앞서 보았던 과정에 비해 훨씬 효율적이다. 게다가 정확하기까지 하다.

 

 - 지금까지 봤던 알고리즘이 걸리는 시간을 그래프로 표현하면 위와 같다. 마지막 알고리즘이 한 눈에 보기에도 시간단축이 훨씬 나은 것을 알 수 있다.

 

 - 첫 번째 방식은 1,000페이지에서 새로운 1,000페이지가 추가되면 1,000번의 과정이 더 추가되지만 마지막 방식은 1,000페이지가 추가되더라도 단지 한 번의 과정만 추가될 뿐이다.

 

 

* 의사코드(Pseudocode)

 - 의사코드란 일련의 과정들을 컴퓨터가 수행가능할 정도의 절차로 정리한 코드이다.

 

 - 위에서 보았던 알고리즘을 의사코드 형식으로 작성하면 다음과 같다.

 

전화번호부를 집어 든다.
전화번호부의 중간을 펼친다.
페이지를 살핀다.
만약 윤해리가 페이지에 있으면
	윤해리에게 전화한다.
그렇지 않고 만약 윤해리가 앞 페이지에 있으면
	앞 페이지의 절반을 편다.
	3번째 줄부터 다시 실행한다.
그렇지 않고 만약 윤해리가 뒷 페이지에 있으면
	뒷 페이지의 절반을 편다.
	3번째 줄부터 다시 실행한다.
그렇지 않으면
	종료한다.

 

 - 작성한 의사코드를 살펴보면 프로그래밍 언어에서 볼 수 있는 여러가지 공통점이 있다.

 

 - 먼저 집어든다, 펼친다, 살핀다, 전화한다, 종료한다 등은 함수(function)이다. 일종의 동사이다.

 

 - 만약, 그렇지 않고 만약, 그렇지 않으면 과 같은 구문은 조건이라 부른다.

 

 - 조건의 뒤에 있는 질문들은 불리언(Boolean)이라 한다. 이들은 모두 Yes 또는 No의 값을 반환한다. 컴퓨터에서는 이를 True와 False로 반환할 것이다.

 

 - 다시 실행한다는 부분은 루프(loop)라고 한다. 특정 부분을 계속 반복하는 것을 의미한다.

 

 

---

 

 

참고

 

 

이 글은 하버드 대학교 David Malan 교수의 CS50 강의를 수강 후 정리하며 쓴 글입니다.

 

 

 

CS50 공식사이트

CS50

 

부스트코스

다 함께 배우고 성장하는 부스트코스