1. 컴퓨팅 사고 - 알고리즘

*boostcourse의 '모두를 위한 컴퓨터 과학 (CS50 2019)' 코스 강의를 듣고 정리한 글입니다.
 모든 내용의 출처는 boostcourse의 해당 코스에 있습니다.

 

알고리즘

- 문제 해결의 관점에서는, '문제 해결을 위한 단계적 방법'

- 대부분의 경우, 문제 해결은 단지 우리가 가지고 있는 생각이나 직관들을 기계나 다른 사람들이 이해할 수 있는 방식으로 번역하는 것

 

1) 알고리즘의 예시 - 전화번호부에서 Mike Smith 찾기

(1) 전화번호부를 집어 들고 첫 페이지를 펼친 후 Mike Smith가 그 페이지에 있는지 찾음.

Mike Smith 를 찾을 때까지 혹은 전화번호부가 끝날 때까지, 'Mike Smith'가 이번 페이지에 없다면 다음 페이지로 넘기는 작업을 반복함.
Mike Smith 가 전화번호부에 있다면, 언젠간 이 알고리즘을 통해 Mike Smith 를 찾을 수 있을 것

 

한 번에 두 페이지를 넘기게끔 하여 알고리즘을 개선할 수 있으나, Mike Smith가 있는 페이지를 그냥 넘겨 버릴 수 있음
이럴 때는 이전 페이지를 확인하면 되지만, 이 문제를 해결하기에 가장 효율적이지는 않음

-> 정확하지만, 매우 오래걸리고 비효율적인 알고리즘.

 

(2) 더 직관적이고 효율적인 알고리즘?

전화번호부 가운데를 펼쳐서 Mike Smith가 그 페이지에 있다면 끝.
그 페이지에 없어도, 전화번호부가 이름순으로 정렬되어 있으므로 Mike Smith가 지금 페이지보다 앞부분에 있는지 뒷부분에 있는지 알고 있음. 그래서 책의 한 페이지가 남을 때까지, 나머지 절반의 똑같은 알고리즘을 수행하면 됨.

마지막에 남은 한 페이지에는 Mike Smith의 이름이 있거나 없거나 둘 중 하나일 것.
이 알고리즘은 기존 알고리즘보다 더 효율적.

만약 기존 전화번호부가 100페이지고, 100페이지가 또 추가되어 200페이지가 되었다고 가정하면
(1)번 알고리즘은 페이지를 100번 더 넘겨야 하지만, 절반씩 줄어드는 두 번째 알고리즘은 단 1번의 절차만 더 수행하면 됨.
첫 번째 절차에서 200페이지를 반으로 나누기에, 100페이지를 만들 수 있기 때문.

 

 

 

2) 알고리즘의 정의

- 입력(input)에서 받은 자료를 출력(output)형태로 만드는 처리 과정을 뜻함

   *입력: 숫자, 글자, 색깔 등을 컴퓨터가 이해할 수 있는 2진법으로 표현하는 것
   *출력: 위의 표현을 원본의 숫자, 글자, 색깔로 화면에 나타내는 것

 

- 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열

 

- 일련의 규칙들을 어떤 순서로 나열하는지에 따라 알고리즘의 종류가 달라짐

- 같은 출력값이라도 알고리즘에 따라 출력을 하기까지의 시간이 다를 수 있음

 

- 알고리즘을 평가할 때는 정확성과 효율성이 중요.
  (효율성: 작업을 완료하기까지 얼마나 시간과 노력을 덜 들일 수 있는가)

 

- 1)에서 Mike Smith를 전화번호부에서 찾기 위해 어떤 명령들이 수행되어야 하는지에 대해 두 가지 알고리즘을 찾아봄
  1)-(1) 알고리즘은 한 장을 넘긴 다음 또 한 장 넘기는 규칙들의 순서적 나열,
  1)-(2) 알고리즘은 반을 줄이고, 다음 또 반을 줄이는 규칙들의 순서적 나열

 

 

3) 의사코드

- 알고리즘은 아래와 같은 의사코드라는 방식으로 보다 명료하게 정리할 수 있음

- 필요한 행동이나 조건을 잘 설정하여 컴퓨터가 수행해야 하는 일을 절차적으로 파악함

Pick up phone book
Open to middle of phone book
Look at page
If Smith is on page
	call Mike
Else if Smith is earlier in book
	Open to middle of left half of book
    Go back to line 3
Else if Smith is later in book
	Open to middle of right half of book
    Go back to line 3
Else
	Quit
    

##의사코드
##중간중간 들여쓰기가 되어있는 부분은 종속 관계를 나타내는데, 자세한 설명은 나중에 나온다고 함

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

- 위 의사코드는 C언어나 파이썬과 같은 언어들과 여러가지 공통점이 있음

  1. 함수(functions). 컴퓨터가 사람에게 무엇을 할지 알려주는 동사와 같음
      -> 1번째 줄 Pick up, 2번째 줄 Open to, 3번째 줄 Look at, 5번째 줄 Call, 7&10번째 줄 Open to, 13번째 줄 Quit

 

  2. 조건. 여러 선택지 중 하나를 고르는 것
      -> 4번째 줄의 If, 6&9번째 줄의 Else if, 12번째 줄의 Else

 
  3. 불리언(Boolean). 답이 예/아니오/참/거짓으로 나오는 질문 (2진법의 경우 답이 0또는 1로 나옴) 

     -> 4번째 줄의 Smith is on page, 6번째 줄의 Smith is earlier in book, 9번째 줄의 Smith is later in book

 

  4. 루프(loop). 무언가를 계속해서 반복하는 순환

    -> 8&11번째 줄의 Go back to line 3