컴퓨터 과학 CS - 알고리즘

 

 

부스트코스 - 모두를 위한 컴퓨터 과학 (CS50 2019) / 1. 컴퓨팅 사고 / 3) 알고리즘 

https://www.boostcourse.org/cs112/lecture/118999?isDesc=false 

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

 

 

알고리즘 정의

알고리즘이란 입력(input)받은 자료를 출력(output)형태로 만드는 "처리과정"을 의미하며
입력값으로 출력값을 얻기위한 어떤 명령들이 수행되어야 하는지에 대한 "규칙들의 순서적 나열"을 말한다.

 

---

알고리즘 평가

알고리즘을 평가할때는 정확성이 제일 중요하지만 이와 함께 효율성에 대한 평가도 중요시한다.
같은 입력값으로 같은 출력값을 내는 두 알고리즘을 비교하여 보다 적은 노력과 시간을 들이는 것이 중요하기 때문이다.

 

1000장의 전화번호부 사이에서 Mike Smith를 찾아보자.

1. 한장 한장 살펴보는 알고리즘
2. 이름 순이라는 규칙에 따라 Mike Smith가 앞부분에 위치한지 뒷부분에 위치한지 인지하며 전화번호부의 반절을 버리고 이 2번 행동을 반복하는 알고리즘

1번이 Mike Smith를 찾기위해 페이지를 넘기는 행동을 500번 넘게 하고 있을때
2번은 1000 페이지 중 Smith가 없는 500페이지 버리기 > 나머지 500페이지 안에서 Smith가 없는 250페이지 버리기 > ...
이 행동을 반복하다 단 10번째에 Mike Smith씨를 찾아내버린다.

두가지를 비교해보면 둘다 언젠가 Mike Smith씨를 찾겠지만 들이는 노력과 시간이 차이가 완전히 다르다는 걸 알 수 있다. 그럼 당연히 선택되는 알고리즘은 2번인 것이다.

 

 

 

---

의사코드

알고리즘을 표현하는 방식 중 의사코드에 대해 알아보자.

 

의사코드는 작동의 논리를 프로그래밍 언어가 아닌 사람의 일반적인 언어를 사용해 코드를 흉내내어 알고리즘을 표현하는 방식으로 이를 통해 필요한 행동이나 조건을 잘 설정하여 컴퓨터가 수행해야 하는 일을 절차적으로 파악할 수 있게 해준다.

 

Mike Smith를 찾는 알고리즘을 다음과 같이 의사코드로 표현할 수 있다.

1	전화번호부를 든다
2	전화번호부를 가운데를 편다
3	페이지에서 Mike Smith를 찾는다
4	만약 Smith가 이 페이지에 있다면
5 		Mike를 찾아 전화한다
6	그렇지 않고 만약 Smith가 앞 페이지에 있다면
7		앞 페이지의 가운데를 편다
8		3번 줄로 가서 다시 실행한다
9	그렇지 않고 만약 Smith가 뒷 페이지에 있다면
10		뒷 페이지의 가운데를 편다
11		3번 줄로 가서 다시 실행한다
12	그렇지 않다면
13		그만둔다

이 의사코드를 기능에 따라 나누면

함수(Function)

빨간색으로 강조된 부분을 함수(Functions)라 한다.
여기서는 사람이 해야할 동작을 알려주는 동사지만 컴퓨터 입장에서도 해야할 동작을 알려주는 것 또한 함수라고 합니다.

---

조건

여기서 빨간색으로 강조된 건 조건이다. 행동에 있어 선택지를 만드는 부분이다.

---

불리언(Boolean)

선택을 위한 결정을 내리기 위한 질문 부분으로

YES(예) / TRUE(참) / 1
이나
NO(아니오) / FALSE(거짓) / 0

의 답이 다오는 질문을 불리언이라 한다.

---

루프(loop)

행동을 반복, 순환 할 수 있게 하는 부분을 의미한다.