컴퓨팅 사고 | 알고리즘

✔ 학습목표

1. 우리가 일상생활에서 하는 일들을 컴퓨터가 이해할 수 있는 알고리즘으로 표현할 수 있다.

2. 효율적인 알고리즘에 대해 설명할 수 있다.

 

 

알고리즘

앞서 숫자, 글자, 색깔 등을 컴퓨터가 이해할 수 있는 2진법으로 표현하는 것은 입력(input)에 해당한다. 컴퓨팅은 입력을 받아 처리한 후 출력하는 과정이다. 여기서 처리 과정에 해당하는 것이 알고리즘(algorithm)이다. 알고리즘은 입력(input)에서 받은 자료를 출력(output) 형태로 만든다. 즉, 알고리즘은 출력값을 나타내기 위해 어떤 명령이 수행되어야 하는지에 대한 규칙들의 순서적 나열이다. 이때 정확성은 물론 효율성도 중요하다.

 

예를 들어 전화번호부에서 친구 Mike Smith를 찾는 경우를 생각해보자.

1) 첫 페이지를 펼친 후 친구를 찾을 때까지 한 장씩 넘기며 반복한다.

2) 가운데를 펼친 후 친구를 찾을 때 까지 절반씩 버리며 반복한다(이름순으로 정렬되어 있기 때문).

 

두 번째 알고리즘이 첫 번째보다 더 효율적이라는 것을 알 수 있다.

 

 

의사코드

알고리즘을 보다 명료하게 정리하는 방식을 의사 코드, 혹은 슈도 코드(pseudocode)라고 한다. 앞선 예시를 의사 코드로 나타내면 다음과 같다.

 

Pick up phone book
Open to middle of phone book
Look at page4 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

 

Pick up, Open to, Look at 등

  : 함수(function), 무엇을 할지 알려주는 동사 역할

 

If, Else if, Else 등

  : 조건(condition), 여러 선택지 중 하나를 선택

 

조건문 뒤 Smith is on page 등

  : 불리언(boolean), 결정을 내리기 위한 질문(답이 예/아니오, 참/거짓 혹은 2진법에서 0 또는 1로 나오는 질문)

 

Go back to line 3 등

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

 

 

 

---

 

이 글은 네이버 부스트 코스 David J. Malan(데이비드 J. 말란) 교수님의 모두를 위한 컴퓨터 과학(CS50 2019) 강의를 수강하고 작성한 글입니다. 

 

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