입력한 자료를 출력하려면 어떤 과정이 필요할까요? 🤔
컴퓨터는 단순하다 input을 받으면 Output으로 출력하는 과정이라고 생각하면 되는데
그 안에서 입력받은 내용을 출력값으로 처리하는 과정을 '알고리즘'이라고 한다. 📌
좀 더 정확하게 말하자면
🧞♂️ 알고리즘이란 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열입니다.
그렇다고 다 똑같은 알고리즘일까?
NoNo!🥸
알고리즘에도 종류가 있다는 사실! 종류에 대해서 알아보기 전에 오늘은
알고리즘의 정확성, 효율성에 대해서 짚고 넘어가보자!
1. 정확한 알고리즘 (정확성)
알고리즘은 위에서 정의했다시피 입력을 출력으로 바꾸기 위해 컴퓨터가 따르는 일련의 절차이고 우리의 실생활에서 일어나는 상황도 알고리즘으로 표현할 수 있습니다
예를들어, 전화번호부에서 Mike Smith를 찾는 일을 한다고 가정했을 때
위 코드의 알고리즘을 살펴보면 전화번호부를 집어들고 첫페이지를 펼친후 Mike Smith가 그 페이지에 있는지를 찾습니다. 만약에없다면 그 다음페이지에서 찾고 Mike Smith를 찾을 때까지 혹은 전화번호부가 끝날때까지 위 과정을 반복합니다.
이 알고리즘 방식은 정확하게 Mike Smith를 찾기위한 알고리즘 방식이라고 볼 수 있습니다. 실제로 전화번호부에 찾고자 하는 Mike Smith가 있닥면 찾아낼 수 있을 것입니다.
그렇지만 한장한장 처음부터 끝까지 찾아야한다니 시간이 너무 오래걸리지 않을까요??
그래서 알고리즘을 평가할 때는 정확성도 중요하지만 효율성도 따져야합니다 (코딩테스트 문제에 그래서 시간효율이 나오나보군🙁)
2. 효율적인 알고리즘 (효율성)
효율성은 작업을 완료하기까지 얼마나 시간과 노력을 덜 들일 수 있는지에 대한 척도 입니다.
우린 여기서 더 직관적이고 효율적인 알고리즘이 뭐가 있을 지 생각해 볼 수 있습니다.
위 두번째 코드를 살펴볼까요?
먼저 전화번호부 가운데를 폅니다. 만약 Mike Smith가 그 페이지에 있다면 알고리즘이 끝납니다.
만약 없다면 전화번호부가 이름순으로 정렬되어 있으므로 우리는 Mike Smith가 지금 페이지보다 앞부분에 있는지 뒷부분에 있는지 알수있습니다. 그러므로 책의 절반을 버릴 수 있게 되고 나머지 절반에 대해 똑같은 알고리즘을 수행합니다. 한페이지가 남을 때까지 계속 수행합니다. 마지막에 남은 한페이지에는 Mike Smith의 이름이 있거나 없거나 둘 중 하나일 겁니다.
이 알고리즘은 기존 알고리즘보다 더 효율적입니다. 만약 500폐이지가 추가되었다고 가정해 봅시다. 첫 번째 알고리즘을 사용한다면 추가된 500페이지에 대해 절차가 500번 더 수행될 것이지만 두번째 알고리즘을 사용한다면, 단 1번만 추가로 수행하면 될 것입니다.
이렇게 알고리즘의 정확성 뿐만아니라 효율성도 따져봐야하는 이유에 대해서 정리해보았습니다!
무조건 정확한 알고리즘이 좋지 않다는 것! 시간의 효율성도 꼭 따져봐야 최적의 알고리즘을 찾을 수 있을 것입니다.
