[CS50] 컴퓨팅 사고 - 알고리즘

알고리즘?

알고리즘이란 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열이다.

 

일련의 순서적 규칙들을 어떻게 나열하는지에 따라 알고리즘의 종류가 달라진다.

 

같은 출력값이라도 알고리즘에 따라 출력을 하기까지의 시간이 다를 수 있다.

 

예를 들어, 홍길동을 전화번호부에서 찾는 일을 한다고 가정해보자.

 

먼저 전화번호부를 집어 들고 첫 페이지를 펼친 후 홍길동이 그 페이지에 있는지 확인한다.

 

없다면 다음 페이지로 넘어가서 다시 찾는다.

 

이러한 과정을 홍길동을 찾을 때까지 혹은 전화번호부가 끝날 때까지 반복한다.

 

전화번호부에 홍길동이 있다면 이 방법을 통해 결국 찾을 수 있을 것이다.

 

알고리즘을 평가할 때는 정확성뿐만 아니라 효율성도 중요한 요소이다.

 

효율성은 주어진 작업을 완료하는 데 걸리는 시간과 노력의 양을 줄이는 것이다.

 

한 페이지씩 넘겨가며 확인하는 방식은 정확하지만 매우 오래 걸리고 비효율적이다.

 

이 알고리즘을 개선하기 위해 한 번에 두 페이지를 넘겨보는 방법을 시도해볼 수 있다.

 

그러나 이렇게 하면 홍길동이 있는 페이지를 지나쳐버릴 위험이 있다.

 

이럴 때는 이전 페이지로 돌아가서 확인할 수 있지만, 이 방법도 여전히 비효율적이다.

 

더 나은 방법은 전화번호부의 중간 페이지를 펼쳐서 홍길동이 그 페이지에 있는지 확인하는 것이다. 만약 홍길동이 있다면 문제는 해결된다.

 

만약 없다면 홍길동의 이름이 그 페이지의 이름보다 앞에 있는지 뒤에 있는지에 따라 전화번호부의 앞쪽 절반이나 뒷쪽 절반을 다시 탐색하는 방식이다. 이를 반복하면 결국 홍길동을 찾을 수 있다.

 

이 방법은 앞서 언급한 방식들보다 훨씬 효율적이다.

 

 

의사 코드$_{pseudocode}$

위와 같은 알고리즘은 의사코드라는 방식으로 명료하게 정리할 수 있다.

 

의사코드는 필요한 행동이나 조건을 잘 설정해 컴퓨터가 수행해야 하는 일을 절차적으로 파악할 수 있게 한다.

전화번호부를 집어 든다
전화번호부의 중간을 편다
페이지를 본다
만약 홍길동이 페이지에 있으면
    홍길동에게 전화한다
그렇지 않고 만약 홍길동이 앞 페이지에 있으면
    앞 페이지의 절반을 편다
    3번째 줄부터 다시 실행한다
그렇지 않고 만약 홍길동이 뒷 페이지에 있으면
    뒷 페이지의 절반을 편다
    3번째 줄부터 다시 실행한다
그러지 않으면
    그만둔다

 

의사 코드를 보면 여러가지 공통점이 있다.

노란색으로 강조된 부분들은 함수$_{function}$라 불린다.

 

다음 사진의 노란색으로 강조된 부분은 조건$_{condition}$이라고 부른다. if, else if, else가 해당된다.

 

결정을 내리기 위한 질문이 필요한데, 이를 불리언$_{boolean}$이라고 한다. 값이 True 또는 False로 나오는 질문을 뜻한다.

 

마지막 사진으로, 노란색 강조된 부분은 루프$_{loop}$라고 한다.

 

 

References

모두를 위한 컴퓨터 과학 (CS50 2019)

모두를 위한 컴퓨터 과학 (CS50 2019)