3) 알고리즘
알고리즘
알고리즘은 입력(input)에서 받은 자료를 출력(output)하는 처리과정을 뜻합니다.
즉, 알고리즘이란 처리과정을 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열입니다.
정확한 알고리즘
예를 들어 전화번호부에서 사람을 찾는다고 해봅시다.
앞에서부터 한 장 한 장 펼치는 걸 반복한다면 좋은 알고리즘이라고 할 수 있을까요?
언젠가는 찾아내고 말겠지만 시간은 오래 걸릴 것입니다.
이처럼 알고리즘은 정확성도 중요하지만 효율성 또한 중요합니다.
정확하고 효율적인 알고리즘
2진 트리 알고리즘을 사용해봅시다.
1000페이지를 계속해서 반으로 가르며 확인해나가는 처리 과정입니다.
1024 -> 512 -> 256 -> 128 -> ... 1
이 알고리즘을 사용한다면, 1000페이지의 문서라도 많아야 10번의 탐색을 거치게 됩니다.
log n의 시간복잡도
비록 페이지 수가 2배가 되더라도 1번의 탐색만을 더 하면 되겠죠.
보셨다시피 알고리즘은 효율성을 중요시 여겨야 합니다.
의사코드
의사코드란 프로그래밍 언어로 변환이 가능하고, 사람이 이해할 수 있는 코드입니다.
위의 정확하고 효율적인 알고리즘을 의사코드화 시켰습니다.
1) 친구와 1부터 100까지 숫자 중 1가지 숫자를 맞추는 스무고개 게임을 하려고 합니다. 이 때 사용할 알고리즘을 의사코드로 표현하면 어떻게 될까요?
1. 생각한 번호를 부른다.
2. 답을 기다린다.
3. 만약 정답이면
4. 게임을 끝낸다.
5. 만약 Up이면
6. 더 큰 번호를 생각하고 1번으로 간다.
7. 만약 Down이면
8. 더 작은 번호를 생각하고 1번으로 간다.
9. 그렇지 않으면
10. 1번으로 돌아간다.
1. 번호를 생각해 정한다.
2. 번호를 받길 기다린다.
3. 만약 받은 번호가 생각한 번호와 같으면
4. 정답이라고 답한다.
5. 만약 받은 번호가 생각한 번호보다 크면
6. Up이라고 답한다.
7. 만약 받은 번호가 생각한 번호보다 작으면
8. Down이라고 답한다.
9. 그렇지 않으면
10. 올바른 숫자가 아니라고 답한다.
11.2번으로 돌아간다.
note
written by CaesiumY