부스트코스(Boostcourse) CS50 1주차 컴퓨팅 사고 - 알고리즘

CS50 1주차 컴퓨팅 사고 - 알고리즘에 대한 강의를 듣고 정리하고 또 추가적으로 공부한 내용을 정리하려고 한다.

 

컴퓨터에 정보를 입력하고 어떻게 정보를 표현하는지 배웠다.
그러면 컴퓨터는 어떻게 입력한 정보를 처리해서 출력을 하는 것인지 궁금해진다.
컴퓨터가 처리하는 과정은 우리가 일상 생활에서 다양한 문제를 처리하는 방식과 비슷하다고 한다.
컴퓨터는 순서대로 필요한 동작을 하며 문제를 처리하는 데, 이를 알고리즘이라고 한다.

 

알고리즘 | Algorithm

그럼 알고리즘에 대해서 알아보자.

 

컴퓨팅은 입력을 받아 그 입력을 처리한 후 출력하는 과정이다.
알고리즘은 입력에서 받은 자료를 출력 형태로 만드는 처리 과정을 뜻한다.

 

입력(Input) → 알고리즘(Algorithms) → 출력(Output)

 

따라서, 알고리즘은 입력 값을 출력 값의 형태로 바꾸기 위해
어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열 이라고 한다.
간단하게 말하면 어떤 일을 처리할 때 처리할 규칙들의 순서를 정해 처리한다는 것이다.

 

이 강의에서는 좋은 예를 통해 알고리즘에 대한 이해를 도와준다.

 

1) 첫 페이지부터 한 페이지씩 확인하는 알고리즘

전화번호부에서 "남제이" 를 찾아야 한다.
그럼 전화번호부를 들어 첫 페이지를 펼친 후 "남제이" 가 펼친 페이지에 있는지 확인한다.
없으면 다음 페이지로 넘어간다.
"남제이" 를 찾을 때 까지 반복한다.
만약 전화번호부에 남제이가 있다면 언젠가는 찾을 수 있을 것이다.

 

위의 예는 처음부터 확인하기 때문에 정확한 알고리즘이라고 말할 수 있다.

 

하지만 알고리즘에 대해서 평가할 때, 정확성도 중요하지만 효율성도 중요하다.
효율적이다는 말은 얼마나 시간과 노력을 덜 들일 수 있는지에 대한 것이다.
그럼 위의 알고리즘은 효율적일까? 아니다. 처음부터 일일이 찾아야하기 때문에 매우 비효율적인 알고리즘이다.

 

2) 두 페이지씩 확인하는 알고리즘

그럼 한 번에 두 페이지씩 넘기면 시간이 반으로 줄지 않을까? 하는 생각을 할 수 있다.
하지만 "남제이" 가 있는 페이지가 그냥 넘어갈 수 있기 때문에 주의해야한다.
추가적으로 이전 페이지도 확인하게 할 수 있지만 역시 효율적이지 않은 알고리즘이다.

 

3) 이름순으로 정렬된 것을 활용해 절반씩 줄여가며 확인하는 알고리즘

그럼 이번에는 전화번호부의 가운데를 편다.
만약 "남제이" 가 있다면 알고리즘이 끝난다.
없다면? 전화번호부가 이름 순으로 정렬되어 있기 때문에
"남제이" 가 현재 펼쳐진 페이지에서 앞에 있는지 뒤에 있는지 알 수 있다.
그럼 전화번호부의 절반을 버리고 나머지 절반에서 똑같은 알고리즘을 수행하면 된다.
찾을 때까지 계속 반복하면 마지막에 "남제이" 가 있거나 없거나 둘 중 하나의 결과를 얻게 된다.
한 번의 동작으로 반이 줄기 때문에 시간 또한 반으로 줄어든다.

 

확실히 앞 서 예를 들었던 1번과 2번의 알고리즘과는 달리 효율적인 것을 알 수 있다.

 

알고리즘을 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열 이라고 말했듯이,
1번과 2번은 한장을 넘기고 다음 또 한 장을 넘기는 규칙들의 순서적 나열,
3번은 반으로 줄이고 다음 또 반으로 줄이는 규칙들의 순서적 나열이라고 정리할 수 있다.

 

의사코드 | Pseudo Code

위에서 알고리즘이 진행되는 과정을 서술해가며 예를 들었는데
알고리즘은 의사코드 라는 방식으로 보다 쉽게 정리할 수 있다.

 

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

 

위에서 예를 들었던 3번 알고리즘을 의사코드로 다시 적어보면

 

1. 전화번호부를 집어든다.
2. 전화번호부의 중간을 편다.
3. 페이지를 본다.
4. 만약 "남제이" 가 페이지에 있으면
    4-1. "남제이" 에게 전화한다.
5. 그렇지 않고 "남제이"가 앞 페이지에 있으면
    5-1. 앞 페이지의 절반을 편다.
    5-2. 3번으로 돌아간다.
6. 그렇지 않고 "남제이"가 뒷 페이지에 있으면
    6-1. 뒷 페이지의 절반을 편다.
    6-2. 3번으로 돌아간다.
7. 그렇지 않으면
    7-1. 그만둔다.

 

의사코드에서 다른 프로그래밍 언어를 공부했다면 알겠지만 여러가지 공통점을 볼 수 있다.

 

노란색으로 강조한 부분들은 함수(Functions) 라고 부른다.
함수는 집어들다, 펴다, 보다 와 같이 컴퓨터에게 무엇을 해야하는지 알려주는 동사와 같은 역할을 한다.

 

초록색으로 강조한 부분들은 조건(Conditions)라고 부른다.
조건은 여러 선택지 중에서 하나를 고른다는 것이다.
정해진 조건이 맞는다면 실행하고 맞지 않으면 실행하지 않는다.

 

파란색으로 강조한 부분들은 불리언(Boolean) 이라고 한다.
결과가 예 또는 아니오 , 참 또는 거짓, 0 또는 1 로 나오는 질문을 말한다.
애매모호한 결과가 나오는 것이 아닌 긍정 또는 부정의 결과가 명확한 질문을 해야한다.

 

보라색으로 강조한 부분들은 루프(Loop)라고 한다.
말 그대로 무언가를 계속해서 반복하는 것이다.

 

정리해보면
알고리즘은 정해진 규칙들을 순서대로 실행한다는 것이다.
알고리즘은 정확한 결과를 얻는 것도 중요하지만 효율적인 부분도 매우 중요하다.
그리고 의사코드를 통해 알고리즘을 보다 쉽게 파악하고 정리할 수 있게 도와준다.

 

어떤 알고리즘을 만드는지에 따라 보다 정확하고 효율적으로 결과를 얻을 수 있다는 점을 기억해야겠다.

 

 

- 참고 사이트 - 

www.boostcourse.org/cs112/lecture/118999

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