CS 알고리즘 - 알고리즘과 의사코드

문제 해결 관점에서 '알고리즘'은 문제를 해결하는 단계적 방법이다.

대부분 문제 해결은 이미 가지고 있는 직관이나 생각을 기계나 다른 사람들이 이해할 수 있는 방식으로 번역하는 것과 같다.

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

어떤 알고리즘이 더 좋은지는 어떻게 알 수 있을까?

알고리즘을 평가할 때는 정확성도 중요하지만 효율성도 중요하다.
예를 들어 Smith Mike를 찾기 위해 알파벳순으로 정렬된 전화번호부를 열었을 때 맨 앞페이지부터 한장씩 넘기면서 찾는 방법도 정확하지만 효율성이 매우 떨어져서 비효율적인 알고리즘이 될 것이다.

2페이지씩 넘긴다면 어떨까? 1페이지 넘길 때보다 약 2배 정도 빠를 수는 있지만 Smith Mike를 찾지 못하고 지나쳐버릴 수도 있기 때문에 주의가 필요하고 그다지 효율적이지 않다.

전화번호부 가운데를 펴서 정렬된 이름을 확인하면 어떨까? 가장 효율적으로 찾을 수 있을 것이다.
가운데를 펴서 있으면 한번에 찾을 수 있고 없으면 해당 위치의 이름을 확인해서 Smith Mike의 S가 앞쪽에 있을지, 뒤쪽에 있을지 판단하고 앞에 있다면 뒤부분은 버리고 앞쪽을 절반으로 나눠서 같은 행동을 반복하면 된다. 1024 페이지였다면 512 페이지에서 256.. 과 같이 탐색을 계속 진행할 때마다 찾아야 하는 페이지가 절반으로 줄어들게 된다.

한 페이지나 두 페이지씩 넘겨서 찾았던 것보다 훨씬 더 빠르고 정확하게 Smith Mike를 찾을 수 있게 된다.

의사코드

이 생각과 직관을 예시 코드로 나타낼 수 있는데 이것을 의사 코드 라고 한다.
정확한 정의는 없지만 의사 코드는 생각을 간결하게 정리한 코드와 비슷한 구문을 말한다.

1. 전화번호부를 집어든다.
2. 전화번호부의 중간을 편다.
3. 페이지를 살펴본다.
4. 해당 페이지에 찾는 이름(Smith Mike)이 있는가?
5. (있다면) Smith Mike에게 전화를 건다.
6. (없다면) Smith Mike의 S가 현재 위치에서 앞쪽, 뒤쪽인지 확인한다.
7. (왼쪽이라면) 책의 앞쪽(왼쪽) 절반에서 가운데를 펼친다.
8. (오른쪽이라면) 책의 뒤쪽(오른쪽) 절반에서 가운데를 펼친다.
9. 3번으로 돌아가서 반복한다.
10. 다 찾아봐도 없다면 탐색을 종료한다.

생각해보기

친구와 1부터 100까지 숫자 중 1가지 숫자를 맞추는 스무고개 게임을 하려고 한다. 이 때 사용할 알고리즘을 의사코드로 표현하면 어떻게 될까?

1. 친구에게 1부터 100까지 중 숫자를 1개 정하라고 한다.
2. 현재 숫자의 절반값보다 크거나 같은지 물어본다.
3. (맞다고 하면) 숫자 N / 2 의 큰쪽으로 범위를 좁힌다.
4. (아니라고 하면) 숫자 N / 2 의 작은쪽으로 범위를 좁힌다.
5. 이 과정을 2번부터 반복한다.
6. 마지막에 남은 숫자를 부른다.

---

참고 자료
모두를 위한 컴퓨터 과학(CS50 2019)