[CS50 | 모두를 위한 컴퓨터 과학] 컴퓨팅사고 - 알고리즘

 

 

주어진 학습목표를 이루기 위해서 이해를 우선으로 두고 공부할 것이다.

들어가기 전에 학습목표, 핵심 단어는 강의 자료를 가져올 것이고 그 이후로는 내가 이해하고 공부한 부분을 직접 적고, 마지막에는 배운 점이나 느낀 점을 적도록 하겠다. 

 

 

---

 

 

들어가기 전에

우리는 이제 컴퓨터에 정보를 입력하는 방식을 배웠습니다. 그렇다면 이 정보를 컴퓨터는 어떻게 가공하여 출력하는 걸까요? 우리가 일상생활에서 다양한 문제를 처리하는 방식처럼, 컴퓨터 또한 순서대로 필요한 동작을 하며 문제를 처리합니다. 이를 알고리즘이라고 하는데, 알고리즘은 어떻게 정의할 수 있고, 그 정확성과 효율성은 어떨까요?

 

 

학습 목표

1. 우리가 일상 생활에서 하는 일들을 컴퓨터가 이해할 수 있는 알고리즘으로 표현할 수 있습니다.
2. 효율적인 알고리즘에 대해 설명할 수 있습니다.

 

핵심 단어

• 알고리즘
• 의사코드

 

 

---

 

알고리즘

 

지난 시간에 어떤 숫자든 글자든 색깔, 영상이든 2진법으로 나타냄으로써 입력을 나타내는 법을 알았다. 이번엔 그 입력으로부터 출력을 어떻게 얻을 수 있는지 알아보겠다. 

 

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

 

문제 해결 관점에서 보면 알고리즘은 문제를 해결하는 단계적 방법이다. 문제의 처리과정에 따라서 같은 출력 값이라도 알고리즘에 따라 출력 시간이 좀 더 빠를 수도, 느릴 수도 있다.

 

 

 

예를 들어, 1000페이지의 전화번호부에서 Mike Smith를 찾는 일을 한다고 할 때, 아래와 같은 방법들을 쓸 수 있다. 

 

 

1. 한 장씩 넘기며 찾는다.  - n

정확하지만, 비효율적이다.

 

2. 두 장씩 넘기며 찾는다. - n/2

1번보다 정확하지 않다. 이전 페이지를 확인하면 되게끔 하면 되지만 역시 이도 효율적이지만은 않은 방법이다. 

 

3. 책의 절반을 잘라 버려 가며 찾는다. - log n

이름순으로 정렬된 전화번호부에 따라 Mike Smith는 뒤쪽에 있을 것이므로 책의 절반을 잘라 앞부분을 버린다. 

이 과정을 반복하다 보면 마지막에 남은 한 페이지에는 Mike Smith가 있거나, 없거나 둘 중 하나의 결과가 나올 것이다. 

정확하면서 효율적인 방법이 되겠다. 

 

 

 

 

만약 전화번호부가 2000페이지라면?

 

여기서 1번 알고리즘은 1000번의 페이지를 2번 알고리즘에서는 500페이지를 더 넘겨야 하지만, 3번 알고리즘은 단 한 번의 동작으로 2000페이지의 반인 1000페이지가 사라지기 때문에 단 한 번의 절차만 더 수행하면 된다. 

 

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

 

1번 알고리즘은 한 장을 넘긴 다음 또 한 장 넘기는 규칙들의 순서적 나열이다.
2번  알고리즘은 반을 줄이고, 다음 또 반을 줄이는 규칙들의 순서적 나열이다.

 

이것이 알고리즘의 정의가 된다. 

 

 

 

 

의사 코드

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

영어이든 어떤 것이든 우리의 생각을 간결하게 정리한 코드와 비슷한 구문을 말한다.  

 

여기서 들여 쓰기는 종속관계를 나타낸다.

 

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

 

 

이 의사 코드를 보면 여러 언어에서 볼 수 있는 여러 가지 공통점이 있다.  이 의사 구문에서 프로그래밍 언어를 사용하는 방식에는 네 가지가 있다. 

 

• functions
• conditions
• Boolean expressions
• loops

 

왼쪽 사진에서 노란색으로 강조된 부분들은 앞으로 함수(functions)로 불린다.  함수는 컴퓨터에게 이 경우에는 사람에게 무엇을 할지 알려주는 동사와 같다.

다음으로 오른쪽 사진에서 노란색으로 강조된 부분들은 조건이라고 부른다. 이 것은 여러 선택지 중 하나를 고르는 것이다.

 

앞서 말한 결정을 내리기 위해서는 질문이 필요하다.  (왼쪽 사진) 이것을 불리언(Boolean)이라고 한다. (수학자 Boole의 이름을 땄다고 함) 답이 Yes(예) 또는 No(아니오) 혹은 True(참) 또는 False(거짓)으로 나오는 아니면 2진법에서 0 또는 1로 나오는 질문을 뜻한다.

 

마지막으로 오른쪽 사진에서 노란색으로 강조된 부분은 루프(loop)라고 한다. 이 것은 뭔가를 계속해서 반복하는 순환이다.

 

 

 

물론 이 네 가지 말고도 변수(variables) , 스레드(threads), 이벤트(events)등 여러 가지가 있다. 우리는 이들을 실제 프로그래밍 언어를 사용하는 방식으로 다루게 될 것이다.

 

 

---

 

생각해보기

 

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

 

1. 1-100사이의 중간사이의 값인 50이냐고 물어본다. 
	2. 친구에게 정답 확인
    3. 정답이라면 게임종료 후 점수 얻음
    
4. 그렇지 않고 만약 50보다작으면
	5. 25냐고 물어본다. 
    6. 2부터 실행
    
7. 그렇지 않고 만약 50보다 크면?
	8. 75냐고 물어본다. 
    9. 2부터 실행 
    
10. 질문 횟수가 20회가 되면 게임이 끝나고 점수를 출력한다. (혹은 이겼는지 졌는지)

 

 

알고리즘이 무엇인지 정확한 정의를 알았다. 내가 항상 푸는 것인데도 정의라는 것에 크게 생각하지 않았는데, 저번에 공부했던 시간 복잡도를 생각하며 보니 더 이해가 잘 되었다.

 

3번 알고리즘과 같이 반으로 자르는 효율적인 방식도 강의에는 알려주지 않았지만 이분 탐색이라는 개념을 얘기하고 있다는 것을 스스로 생각하게 되는 것을 보고 지난 시간 동안 공부했던 것들이 결국 나도 모르게 컴퓨팅적 사고를 길러준 것이었구나- 하는 생각이 들었다. 

 

또 평소 알고리즘을 풀 때 너무 복잡한 게 있으면 절차를 생각하며 의사 코드 표현방식으로 쓰고 코드를 쓰기도 했는데 이게 '의사 코드'라는 표현방식이었다는 것을 알았다. 확실히 저렇게 적고 코드를 적으면 혼자 생각하는 것보다 더 효율적으로 작성할 수 있게 되는 것 같다. 

 

 

Reference : CS50