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

숫자, 글자, 색깔 등을 컴퓨터가 이해할 수 있는 2진법으로 표현해 입력(input)에 해당하는 것을 배웠다. 
그럼 어떻게 입력(input)에서 출력(output)을 얻을 수 있을까?
입력을 받아 그 입력을 처리한 후 출력하는 과정을 컴퓨팅이라고 한다. 

 

알고리즘

• 입력(input)에서 받은 자료를 출력(output)형태로 만드는 처리과정을 뜻한다. 
• 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열이다.
• 일련의 순서적 규칙들을 어떻게 나열하는지에 따라 알고리즘의 종류가 달라진다.
• 같은 출력값이라도 알고리즘에 따라 출력하기까지의 시간이 다를 수 있다.

 

 

알고리즘을 평가할 때는 정확성도 중요하지만, 효율성도 중요하다. 
효율성은 작업을 완료하기까지 얼마나 시간과 노력을 덜 들일 수 있는지에 대한 것이다. 

 

예시 : 전화번호부에서 Mike Smith 찾기

 

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

1. 전화번호부를 집어든다.
2. 첫 페이지를 펼친다.
3. 펼친 페이지에 Mike Smith가 있는지 찾는다.
4. 없으면 그 다음 페이지로 넘긴다. 
5. Mike Smith를 찾을 때까지 혹은 전화번호부가 끝날 때까지 이것을 반복한다.

=> 정확하지만 매우 오래걸리고 비효율적이다.

 

 

B ) 두장을 넘긴 다음 또 두장을 넘기는 규칙들의 순서적 나열

1. 전화번호부를 집어든다.
2. 2 페이지를 펼친다.
3. 펼친 페이지에 Mike Smith가 있는지 찾는다.
4. 없으면 2장을 넘긴다. 
5. Mike Smith를 찾을 때까지 혹은 전화번호부가 끝날 때까지 이것을 반복한다.

=> A의 알고리즘보다 2배 빠르다.

=> 하지만 Mike Smith가 있는 페이지를 그냥 넘어갈 수 있는 문제가 있다. 이럴경우 이전페이지로 돌아가서 그 실수를 고치면 된다.

=> 하지만 전화번호부가 1000페이지가 넘는다면 여전히 Mike Smith을 찾기위해 500번 이상 페이지를 넘겨야 한다.

 

 

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

1. 전화번호부를 집어든다.
2. 전화번호부 가운데를 펼친다.
3. 펼친 페이지에 Mike Smith가 있는지 찾는다.
4. 없다면 M이 지금 페이지보다 뒷부분에 있다면 앞부분을 버린다. (앞부분에 있다면 뒷부분을 버린다.)
5. Mike Smith를 찾을 때까지 혹은 전화번호부가 끝날 때까지 이것을 반복한다.

=> A와 B의 알고리즘보다 더 효율적이다. 

=> 전화번호부가 1024페이지일 경우, C 알고리즘은 10번만에 가능하다. (1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 →)

 

 

? ) 기존의 전화번호부가 100페이지고, 100페이지가 또 추가되어 200페이지가 될 경우

 

A 알고리즘 : 한장씩 넘기므로 100번의 페이지를 더 넘겨야한다.

B 알고리즘 : 두장씩 넘기므로 50번의 페이지를 더 넘겨야한다.

C 알고리즘 : 절반씩 줄어들기 때문에 단 1번의 절차만 더 수행하면 된다. (단 한 번의 동작으로 200페이지의 반인 100페이지가 사라진다.)

 

즉, A와 B는 정확한 알고리즘이지만 효율적이지 않다. 둘에 비하면 C는 정확하고 효율적인 알고리즘이다. 

 

수직축(y축) : 문제해결에 걸린 시간, 수평축(x축) : 문제의 크기

y축을 따라 위로 올라 갈수록 페이지를 넘기는데 걸리는 시간이 길어진다.
x축을 따라 오른쪽으로 갈수록 전화번호부의 페이지 수가 커진다.

 

의사코드

• 필요한 행동이나 조건을 잘 설정하여 컴퓨터가 수행해야 하는 일을 절차적으로 파악할 수 있게 도와준다. 
• 영어 혹은 다른 언어로 생각을 간결하게 정리한 코드와 비슷한 구문을 말한다.

 

함수(functions)

• 컴퓨터에게 이 경우에는 사람에게 무엇을 할지 알려주는 동사와 같다.

 

조건(conditions)

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

 

불리언 표현(boolean expressions)

• 조건에 대한 결정을 내리기 위한 질문이다.
• 답이 Yes 또는 No 혹은 True 또는 False로 나오는 질문, 아니면 2진법에서 0또는 1로 나오는 질문을 뜻한다.

 

루프(loops)

• 뭔가를 계속해서 반복하는 순환이다.

 

이외에도 변수(variables), 쓰레디(threads), 이벤트(events) 등이 존재한다.

 

 

think about

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

1. 1~100사이의 1가지 숫자를 정한다.

2. 도전 기회를 20번으로 지정한다.

3. 만약 도전 기회가 있다면

4.     답을 말한다. 

5.     만약 정답이라면

6.         승리

7.     그렇지 않으면

8.         도전기회를 차감한다.

9.         3번째 줄부터 다시 실행한다. 

10. 그렇지 않으면 (도전 기회 0번 이하)

11.     패배

 

David J. Malan의 강의

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