알고리즘

CS50

XZXXZX 2022. 3. 20. 01:05

728x90

컴퓨팅은 입력을 받아 그 입력을 철리한 후 출력하는 과정이다.

알고리즘은 입력(input)에서 받은 자료를 출력(output)형태로 만드는 처리 과정을 뜻한다.

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

이러한 일련의 순서적 규칙들을 어떻게 나열하는지에 따라 알고리즘의 종류가 달라진다. 같은 출력값이더라도 알고리즘에 따라 출력을 하기까지의 시간이 다를 수 있다.

정확한 알고리즘

예시)

전화번호부에서 Mike Smith를 찾는 일을 한다고 한다.

전화번호부를 집어 들고 첫 페이지를 펼친 후 Mike Smith가 그 페이지에 있는지 찾는다. 없다면 그 다음페이지에서 찾는다.

Mike Smith를 찾을 때까지 혹은 전화번호부가 끝날 때까지 이것을 반복한다.

언젠가는 Mike Smith가 전화번호부에 있다면 이 알고리즘을 통해 Mike Smith를 찾을 수 있을 것이다.

알고리즘을 평가할 때는 정확성도 중요하지만, 효율성도 중요하다.

효율서은 작업을 완료하기까지 얼마나 시간과 노력을 덜 들일 수 있는지에 대한 것이다.

한 번에 한 페이지씩 보는 알고리즘은 정확하지만, 매우 오래걸리고 비효율적인 알고리즘일 것이다.

한 번에 두페이지를 넘기게끔 하여 개선할 수도 있다.

하지만 이 알고리즘을 그대로 사용하게 된다면 Mike Smith가 있는 페이지가 그냥 넘어갈 수도 있으니 주의해야 할 것이다. 이럴 때는 이전 페이지를 확인하면 되지만 이 알고리즘마저도 이 문제를 해결하기에 가장 효율적이지는 못하다.

먼저, 전화번호부 가운데를 편다. 만약 Mike Smith가 그 페이지에 있다면 알고리즘은 끝난다.

없다면, 전화번호부가 이름순으로 정렬되어 있으므로 Mike Smith가 지금 페이지보다 앞쪽에 있는지 뒷쪽에 있는지 알고있다.

그러므로 책의 절반을 버릴 수 있고 나머지 절반에 대해서도 똑같은 알고리즘을 수행한다.

마지막에 남은 한 페이지에는 Mike Smith의 이름이 있거나 없거나 둘 중 하나다.

이 알고리즘은 위의 두개의 알고리즘보다 효율적이다.

만약 기존 전화번호부가 100페이지고, 100페이지가 또 추가되어 200페이지가 되었다고 생각해본다면 한장 한장 넘기는 첫 번째 알고리즘은 100번의 페이지를 더 넘겨야 하지만, 절반씩 줄어드는 두 번째 알고리즘은 1번만 더 수행하면 된다.

한 번의 동작으로 200페이지의 반인 100페이지가 사라지기 때문이다.

👉🏻 만약 책이 1024페이지일 경우

1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1

10단계면 Mike Smith의 페이지를 찾을 수 있다.

알고리즘이란 입력값을 출력값의 형태로 바꾸기 위한 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열 이라고 하였는데 그에 따라 위의 알고리즘을 보면

첫 번째 알고리즘은 한 장을 넘긴 다음 또 한 장 넘기는 규칙들의 순서적 나열이고

마지막 알고리즘은 반을 줄이고, 다음 또 반을 줄이는 규칙들의 순서적 나열이다.

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

의사코드는 필요한 행동이나 조건을 잘 설정하여 컴퓨터가 수행해야 하는 일을 절차적으로 파악할 수 있게 도와준다.

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

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

조건에 대한 결정을 내리기 위해서는 질문이 필요하다. 이것을 불린(Boolean)이라고 한다.

답이 Yes(예) 또는 No(아니오) 혹은 True(참) 또는 False(거짓)으로 나오는 아니면 2진법에서는 0또는 1로 나오는 질문을 뜻한다.

이번 노란색으로 강조된 부분은 루프(loop)라고 한다. 이것은 뭔가를 계속해서 반복하는 순환이다.

728x90