알고리즘
입력으로부터 출력을 얻는 방법이 뭘까?
알고리즘은 입력에서 받은 자료를 출력형태로 만드는 처리 과정을 의미한다.
알고리즘이란 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열이다.
알고리즘의 예시로 전화번호부에서 Mike라는 사람을 찾는다고 해보자.
이런 문제를 해결할 수 있는 방법에는 여러 방법이 있지만, 우선 맨 앞장부터 넘겨가며 찾아보자.
전화번호부에 Mike가 있으면 언젠가 Mike를 찾을 수 있을것이다.
하지만 전화번호부의 페이지가 너무 많다면 시간이 매우 오래걸릴것이다.
이번에는 2장씩 넘겨가며 Mike씨를 찾아보자. 이렇게하면 이전 방법보다는 2배 빠르게 동작하지만 이 알고리즘이 정확한가?
Mike가 있는 페이지를 그냥 넘어갈수도 있으니 부정확하다.
이런식으로 알고리즘은 정확성과 효율성 모두 중요하다.
정확하고 효율적인 알고리즘
그렇다면 어떻게해야 빠르고 정확하게 Mike씨를 찾을 수 있을까?
먼저 전화번호부 가운데 페이지를 펼치고, 거기 Mike씨가 있으면 종료한다.
없다면 전화번호부는 이름순으로 정렬되어있기 때문에 현재 페이지에서 Mike씨가 있는 부분을 알 수 있고, 책의 절반을 버릴 수 있게된다.
그 다음 과정은 Mike씨가 나올때까지 책의 절반을 버리는 작업을 반복하면 된다.
이런 방식으로 찾게되면 마지막 페이지에는 Mike의 이름이 있거나, 만약 없다면 Mike씨는 애초에 전화번호부에 이름이 없던 것이므로 정확한 알고리즘이라고 할 수 있다.
효율성 측면에서는 어떤가? 책이 1024페이지가 있다 하더라도 절반씩 버리다보면 마지막 페이지에 가는 단계가 10단계면 된다.
앞선 알고리즘으로는 최악의 경우 1024단계 / 512단계씩 걸리게 되지만 해당 알고리즘으로는 매우 빠르게 진행된다.
또 전화번호부의 페이지가 두 배로 증가해도 해당 알고리즘에서는 1단계만 더 하면 되므로 매우 효율적이다.
의사코드
앞서 길게 설명한 알고리즘의 내용을 의사코드라는 방식으로 명료하게 정리할 수 있다.
이러한 의사코드를 보면 특징이 있다.
노란색으로 표현된 부분을 함수라고 한다.
함수는 컴퓨터에게 사람에게 뭘 할지 알려주는 동사와 같다.
또한 위와 같이 노란색으로 표현된 부분은 조건이라고 한다.
일종의 갈림길같이 여러 선택지 중 하나를 고르는 것이다.
앞서 설명한 조건에 대한 부분을 결정하려면 질문이 필요한데, 이것을 Boolean이라고 한다.
답이 참과 거짓으로 나오는 것을 의미한다.
마지막으로 강조된 부분을 loop라고 하며, 반복하며 순환하는 부분을 의미한다.
참고자료
네이버 부스트코스 모두를 위한 컴퓨터 과학 (CS50 2019)
https://www.boostcourse.org/cs112/lecture/118999
