이 글을 쓰게 된 이유
- 취업준비를 하며 개발자는 자신의 역량을 나타내기 위하여 코딩테스트를 치룬다. 그러므로 알고리즘/자료구조는 빠질래야 빠질 수 없는 항목이기에 공부하게 되었다.
알고리즘이란?
어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공식화한 형태로 표현한 일종의 문제의 풀이 방법, 해를 의미한다.
알고리즘의 속성
예시 : 횡단보도 옆에 신호등이 있습니다. 현재는 빨간불이지만 5분 뒤에는 초록불로 바뀔 것입니다.
5분이 지나고, 초록불로 바뀐 신호등은 10초 뒤 ‘30’이라는 숫자와 함께 1초에 한 번씩 점등하기 시작합니다.
총 30번을 점등한 신호등은 이어 빨간불로 바뀝니다.
- 입력(Input) : 알고리즘은 출력에 필요한 자료를 입력받을 수 있어야 합니다. 이 상황에서는 제일 먼저 빨간불인 신호등이 초록불이 되려면 5분이라는 시간을 입력 받아야 합니다. 하나 더 알아야 할 것은 신호등은 항상 시간을 입력받아야 알고리즘이 동작하지만 꼭 입력을 받지 않아도 되는 알고리즘도 있습니다. (ex. 원주율(pi)의 1조 번째 자리 수를 구하려는 경우 입력은 없지만 출력은 있다.)
- 출력(Output) : 알고리즘은 실행이 되면 적어도 한 가지 이상의 결과를 반드시 출력해야 합니다. 만약 알고리즘에 출력이 없다면 이 알고리즘은 끝이 났는지, 끝이 나지 않았는지 확인할 길이 없기 때문입니다. 출력은 알고리즘에서 “끝이 났다" 라는 표현이므로 반드시 존재해야 하며, 이는 유한성과도 연관이 있습니다. 이 상황에서 출력은 “초록불로 바뀐다" 입니다.
- 유한성(Finiteness) : 알고리즘은 유한한 명령어를 수행한 후, 유한한 시간 내에 종료해야 합니다. 이는 알고리즘은 실행된 후에는 반드시 종료되어야 한다는 말과도 같습니다. 알고리즘이 무한히 실행이 된다면 무한히 기다려야 할 것이며, 그것은 출력의 기약이 없는 알고리즘일 것입니다. 신호등이 빨간불인 상태에서 초록불로 변하는 과정에 대한 기약이 없다면 그 신호등은 제대로 된 알고리즘으로 동작하는 것이 아닐 것입니다.
- 명확성(Definiteness) : 알고리즘의 각 단계는 단순하고 명확해야 하며, 모호해서는 안 됩니다. 예를 들어 ‘신호등이 몇 분 뒤에 켜집니다’ 와 같이 표현한다면, 명확성이 떨어질 뿐더러 모호한 표현이라고 볼 수 있습니다. ‘신호등이 5분 뒤에 켜집니다‘ 와 같이 명확하게 표현을 해야만 합니다.
- 효율성(Efficiency) : 알고리즘은 가능한 한 효율적이어야 합니다. 모든 과정은 명백하게 실행 가능해야 하며, 실행 가능성이 떨어지는 알고리즘은 효율적이지 못한 알고리즘이라 볼 수 있습니다. 알고리즘은 시간 복잡도와 공간 복잡도를 통해 결정이 되므로, 시간 복잡도와 공간 복잡도가 낮을 수록 효율적인 알고리즘이라 볼 수 있습니다.
하잇