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

알고리즘이란

컴퓨터는 입력을 받아 처리한 후 출력한다. 입력받은 자료를 출력 형태로 만드는 처리 과정을 알고리즘이라고 한다.

알고리즘은 입력값을 출력값으로 바꾸기 위한 명령들의 순서적 나열이다. 같은 결과를 만들더라도 알고리즘에 따라 소요 시간이 달라질 수 있다.

정확한 알고리즘

전화번호부에서 Mike Smith를 찾는다고 가정해보자.

1. 첫 페이지를 펼친다.
2. Mike Smith가 있는지 확인한다.
3. 없으면 다음 페이지로 넘긴다.
4. 찾을 때까지 또는 끝날 때까지 반복한다.

이 알고리즘은 정확하다. Mike Smith가 있다면 언젠가는 찾을 수 있다.

하지만 한 페이지씩 넘기는 방식은 매우 비효율적이다.

 

한 번에 두 페이지를 넘기면? 빨라지지만 원하는 페이지를 건너뛸 수도 있다. 여전히 가장 효율적인 방법은 아니다.

 

효율적인 알고리즘

1. 가운데를 펼친다.
2. Mike Smith가 있으면 끝낸다.
3. 없으면 이름순 정렬을 이용해 앞/뒤를 판단한다.
4. 절반을 버리고 나머지 절반에 같은 과정을 반복한다.
5. 한 페이지가 남을 때까지 계속한다.

이 알고리즘은 매번 문제를 절반으로 줄인다. 첫 번째 알고리즘보다 훨씬 효율적이다.

 

의사 코드

알고리즘을 의사코드로 표현하면 더 명료하다. 의사코드는 컴퓨터가 수행해야 하는 일을 절차적으로 나타낸다.

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

 

의사코드에는 프로그래밍 언어의 공통 요소들이 포함되어 있다.

 

함수

함수(function)는 컴퓨터에게 무엇을 할지 알려주는 동작이다.

 

조건

조건은 여러 선택지 중 하나를 고르는 것이다.

 

불리언

불리언(boolean)은 조건 판단을 위한 질문이다. True/False, Yes/No, 1/0으로 답할 수 있는 질문을 뜻한다.

 

루프

루프(loop)는 특정 동작을 반복하는 것이다.

 

연습 문제

Q. 1부터 100까지 숫자를 맞추는 스무고개 게임의 알고리즘을 의사코드로 표현하면?

1부터 100사이의 숫자를 말한다.
    만약 숫자를 말한 횟수가 20회를 초과하면
        게임은 패배로 끝난다.
    그렇지 않고
        만약 정답을 맞췄다면
            게임은 승리로 끝난다.
        그렇지 않았다면
            1번부터 다시 반복한다.