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

boostcource
모두를 위한 컴퓨터 과학 (CS50 2019) : David J. Malan
www.boostcourse.org/cs112

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

 

 

알고리즘 (Algorithm)

이전 시간 컴퓨터 과학에 대해서 공부할 때, 컴퓨터에는 input(입력)과 output(출력)이 존재하고 그 중간 과정, 입력을 받아 그 입력을 처리한 후 출력하는 과정을 computing(컴퓨팅) 이라고 정의했다. 그리고 컴퓨터가 input을 받을 때 사용하는 표현식인 2진법을 공부했다.

 

알고리즘은 input에서 받은 자료를 output 형태로 만드는 처리 과정을 의미한다.

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

 

같은 input과 output을 받더라도, 수행되는 명령어들의 순서 등이 달라지면 알고리즘 역시 다르다고 구분할 수 있다.

실제로 각각 출력까지 걸리는 시간이 달라지기도 한다. 이를 정확성과 효율성의 차이라고 칭할 수 있다.

 

 

효율적인 알고리즘

Q. 전화번호부에서 "이령"을 찾자!

 

A1. 전화번호부 첫 페이지에서부터 "이령"을 찾아간다.

- 만약 찾을 이름이 "한령" 이였으면, 마지막 페이지까지 도달하길 기다려야하기 때문에 한참 걸릴 수도 ...

- 효율적이라고 판단하기는 어렵다.

- 정의) 한 장을 넘긴 다음 또 한 장 넘기는 규칙들의 순서적 나열

 

A2. 전화번호부 가운데를 펼친 뒤, 그 페이지를 기준으로 앞/뒤 선택. 또 가운데를 펼치기를 반복한다. 마지막 한 페이지가 남을 때까지 반복하며 "이령"을 찾아간다.

- 가운데 페이지에 있는 이름이 "윤뫄뫄" 이였으면, 그 뒤 페이지들만 갖고 또 반을 나눈다 (1/2 -> 1/4 -> 1/8 -> ...) 

- A1과 비교해 더 적은 시간이 소모된다. 조금 더 효율적이다.

- 정의) 반을 줄이고, 다음 또 반을 줄이는 규칙들의 순서적 나열

 

의사코드 (Pseudocode)

프로그램을 작성할 때 각 모듈이 작동하는 논리를 표현하기 위한 언어

필요한 행동이나 조건을 잘 설정함으로써 컴퓨터가 수행해야 하는 일을 절차적으로 파악할 수 있도록 돕는다.

 

위의 알고리즘 예시를 의사코드로 표현한다면 아래와 같이 정리할 수 있다.

 

1. 전화번호부를 집어 든다
2. 전화번호부의 중간을 편다
3. 페이지를 본다
4. 만약 "이령"이 페이지에 있으면
5.     "이령" 에게 전화한다.
6. 그렇지 않고 만약 "이령"이 앞 페이지에 있으면
7.     앞 페이지의 절반을 편다
8.     3번째 줄부터 다시 실행한다
9. 그렇지 않고 만약 "이령"이 뒷 페이지에 있으면
10.     뒷 페이지의 절반을 편다
11.     3번째 줄부터 다시 실행한다
12. 그러지 않으면
13.     그만둔다 

 

프로그래밍 언어로 변환하기 이전, 의사코드를 아래와 같이 구별할 수 있음을 미리 참고하자

함수(functions) 조건(conditions) 불리언(boolean) 루프(loop)