진짜 너무 쉬운 알고리즘 원리
비전공자도 이해하는 알고리즘 기초 개념
동영상으로도 보러오세요 ^0^
1. 알고리즘이란 무엇일까?
여러분 혹시 알고리즘이 무슨 뜻인지 정확히 알고 계신가요? 요즘은 어디를 가도 이 알고리즘이라는 단어를 쉽게 들어볼 수 있는데요. 근데 실제로 이 알고리즘이 무엇인지, 그리고 이 알고리즘은 대체 어떤 원리로 작동하는지에 대해 알고 계신 분들은 생각보다 많지 않으실 것 같습니다. 그래서 준비했습니다. 오늘은 이 알고리즘이 뭔지에 대해 누구나 이해하기 쉽게 한 번 설명드리겠습니다.
우선 알고리즘이 뭔지에 대해 알아보려고 하는데요. 하버드 대학교 데이비드 말란 교수의 말에 따르면 알고리즘은 그저 문제를 해결하는 단계적인 방법에 불과하다고 합니다. 쉽게 말해 문제가 주어지면 그 문제를 해결하기 위해 여러 가지 방법을 사용하게 되는데, 이때 문제를 해결하는 방법이 바로 알고리즘입니다.
알고리즘이란 문제를 해결하는 단계적인 방법이다.
이걸 정말 쉽게 설명드리자면, 만약 제가 수원에서 강남까지 가야 하는 상황이라고 가정했을 때, 저는 버스를 탈 수도 있고, 지하철을 탈 수도 있고, 아니면 택시를 타고 갈 수도 있는데요. 심지어 조금 오래 걸리겠지만 걸어서 강남까지 갈 수도 있습니다.
여기서 우리에게 주어진 문제는 수원부터 강남까지 간다는 것인데요. 이 문제를 해결하기 위해 앞서 말씀드린 것처럼 우리는 다양한 방법을 활용할 수 있습니다. 그리고 이때 활용되는 모든 방법들을 우리는 알고리즘이라고 부르는 것이죠.
근데 알고리즘 같은 경우에도 좋은 알고리즘이 있고, 안 좋은 알고리즘도 있다고 하는데요. 예를 들어, 제가 택시를 타고 강남에 가게 되면 다른 방법들보다 조금 더 빨리 갈 수 있을 텐데요. 그럼 택시를 타는 알고리즘은 다른 알고리즘에 비해 더 좋은 알고리즘이라고 볼 수 있는 것입니다.
물론 요금이 많이 든다는 게 단점이긴 한데, 이걸 컴퓨터에 비유하자면 메모리를 많이 차지한다고 볼 수 있습니다. 어쨌든 단순히 걸리는 시간만 측정한다면, 택시를 타고 가는 게 가장 좋은 알고리즘이라고 볼 수 있습니다. 반대로 걸어가는 알고리즘 같은 경우에는 문제를 해결할 수는 있지만, 그 시간이 너무나도 오래 걸리기 때문에 딱히 좋은 알고리즘이라고는 볼 수 없을 텐데요. 이런 식으로 작용하는 게 바로 알고리즘입니다.
문제를 얼마나 더 효율적으로 해결하는지에 따라 알고리즘의 효용성이 나뉘게 된다.
- 한 줄 요약 : 문제를 해결하는 다양한 단계적인 방법들을 알고리즘이라고 부른다.
2. 알고리즘 이해하기
이제 알고리즘의 원리에 대해 어느 정도 이해가 되셨나요? 그렇다면 이제부터는 조금 더 알고리즘다운 예시를 한 번 들어보겠습니다. 여러분들에게 전화번호부가 있다고 한 번 가정해볼건데요. 전화번호부 안에는 엄청나게 많은 이름과 전화번호가 적혀있습니다. 그리고 이 전화번호부는 가나다 순서대로 이름이 정렬되어 있는데요.
이제 이 수많은 사람들 가운데 내가 원하는 사람의 연락처를 찾아낼 수 있는 알고리즘을 한 번 만들어 보겠습니다. 마크라는 이름을 한 번 찾아볼건데요. 이 전화번호부를 한 페이지씩 넘겨가며 마크를 한 번 찾아보겠습니다.
만약 첫 페이지를 넘겼는데 마크가 없으면 어떻게 할까요? 그럼 다음 페이지를 확인해보겠죠? 근데 만약 다음 페이지에도 마크가 없다면, 또 그다음 페이지를 확인할 텐데요. 이렇게 한 페이지씩 넘기는 과정도 바로 알고리즘입니다. 이 방법을 사용하면 시간이 오래 걸릴지는 몰라도, 결국 마크라는 이름을 찾을 수 있기 때문인데요.
여기서 마크를 찾는 것이 문제이고, 마크를 찾는 방법이 알고리즘이다.
다시 한 번 정리해보자면 전화번호부에서 마크의 연락처를 찾는 게 주어진 문제이고, 이 문제를 해결하기 위해 한 페이지씩 넘겨 마크가 있는지 확인하는 것이 바로 알고리즘인데요. 하지만 앞서 말했듯이 한 페이지씩 넘겨서 마크를 찾는다면 여기에 소요되는 시간은 진짜 오래 걸릴 것입니다. 예를 들어, 여러분이 핸드폰 연락처를 켜서 친구의 이름을 검색했는데, 검색 결과가 한 30분 뒤에 나온다면 어떤 생각이 드실 것 같나요? 뭐 이런 폰이 다 있지 라고 생각하실 텐데요.
이처럼 한 페이지씩 넘겨 확인하는 알고리즘을 사용한다면, 이건 마치 수원에서 강남까지 걸어간다는 것이나 마찬가지입니다. 그렇다면 이 알고리즘을 어떻게 효율적으로 바꿀 수 있을까요? 만약 한 페이지가 아니라 두 페이지씩 넘겨보면 어떨까요? 그럼 속도가 두 배로 빨라지지 않을까요?
물론 이렇게 하면 첫 번째 알고리즘보다는 빨라지겠지만, 그래도 여전히 그렇게 빠른 속도는 아닐 것 같습니다. 근데 여기서 질문이 생길 수도 있는데요. 만약 두 장씩 넘기다가 마크가 있는 페이지를 그냥 지나쳐버리면 어쩌지? 라고 생각하실 수도 있는데, 이런 문제 같은 경우에는 알고리즘을 구성하는 코딩으로 이 문제를 해결할 수 있습니다. 마크라는 이름이 안 나왔는데 ‘마’에 해당하는 부분이 끝난다면 다시 되돌아서 확인해라 이런 식으로 코딩을 짤 수 있는데요.
한 페이지가 아니라 두 페이지를 넘기는 방식으로 알고리즘을 수정할 수 있다.
어쨌든 오늘은 이런 디테일적인 부분 말고, 정말 알고리즘이 어떤 식으로 작동되는지에 대해 조금 더 집중해서 한 번 알아보겠습니다. 그럼 다시 알고리즘으로 돌아와서, 아까 말한 두 번째 알고리즘을 사용하면 속도가 두 배 정도 빨라지긴 하지만 그래도 여전히 엄청나게 빠르지는 않을 텐데요. 그렇다면 이제 가장 효율적인 알고리즘을 한 번 구성해보겠습니다.
아까 이름이 가나다 순서대로 정렬되어 있다고 했잖아요? 그러니까 적당히 중간쯤부터 시작하는 게 빠를 텐데요. 예를 들어, 페이지의 중간을 폈는데 ‘ㅇ’이 나왔다고 가정하면, 마크는 ‘ㅁ’으로 시작하니까 ‘ㅇ’보다 앞쪽에 있겠죠? 가나다 순서이니까요. 그럼 저는 페이지를 한 번 폈을 뿐인데, 문제를 절반으로 줄일 수 있게 되었습니다.
‘ㅁ’이 ‘ㅇ’보다 앞에 있으니까 뒤에 있는 절반의 페이지는 그냥 쓰레기통에 버리면 되는 것이죠. 전화번호부가 총 1,000페이지라고 가정한다면, 이 전화번호부는 단 한 번의 실행 만에 500페이지로 줄어들게 되는 것인데요. 그럼 이제 이 방법을 계속해서 진행하게 된다면 어떻게 될까요?
다시 500페이지의 절반을 펴서 해당 페이지의 자음이 어디인지를 확인한 뒤 나머지 절반을 버리게 되면 이제는 250페이지만 남아있게 될 텐데요. 그렇게 되면 단 두 단계 만에 1,000페이지에서 250페이지로 그 페이지 수가 줄어들게 된 것입니다.
그리고 이 과정을 계속해서 반복하다 보면 결국 한 페이지만 남게 될 텐데요. 그럼 그 페이지에는 마크라는 이름이 있거나 혹은 없을 것입니다. 만약 마지막 페이지에도 마크가 없으면 이 전화번호부에는 마크라는 이름 자체가 없는 것이기 때문이죠.
만약 마크가 있다면 저는 마크에게 전화를 걸면 되고, 반대로 마크가 없다면 저는 이 탐색과정을 그만두면 됩니다. 이런 과정이 바로 알고리즘인데요. 이렇게 효율적인 알고리즘을 활용하면 정답을 훨씬 더 빨리 찾을 수 있는 것입니다.
효율적인 알고리즘을 통해 정답을 훨씬 더 빨리 찾을 수 있다.
여러분도 생각해보시면 비슷한 프로그램인데도, 어떤 프로그램은 진짜 빨리 돌아가는 반면, 다른 프로그램은 천천히 돌아가고 중간중간 렉이 걸리기도 하는데요. 이게 바로 알고리즘의 차이입니다. 한쪽은 더 효율적인 알고리즘을 통해 문제를 해결한 것이고, 다른 한쪽은 조금 부족한 알고리즘을 사용한 것이죠.
알고리즘은 전혀 어려운 게 아닙니다. 문제가 있고 그 문제를 풀어 원하는 답을 도출하기 위해, 그 문제를 효율적으로 푸는 과정이 바로 알고리즘인데요. 여기서 잘 짜여진 알고리즘 같은 경우에는 다른 알고리즘에 비해 같은 문제를 풀어도 훨씬 더 빠르고 효율적으로 문제를 풀어내는 것이죠.
- 한 줄 요약 : 같은 문제를 풀어도 알고리즘의 구성방식에 따라 기능성의 차이가 존재한다.
3. 알고리즘의 실질적인 예시
그럼 이제 이 알고리즘에 대해 조금 더 자세하게 한 번 알아보겠습니다. 아까의 예시와 같이 전화번호부에서 마크라는 이름을 찾아내는 알고리즘을 만들어 볼 건데요. 이번에는 진짜 컴퓨터에서 쓰는 형식을 사용해 알고리즘을 한 번 만들어 보겠습니다. 물론 이해하기 쉽게 컴퓨터 언어가 아니라 한글을 사용해 볼건데요. 그럼 이렇게 구현할 수 있을 것 같습니다.
1단계, 전화번호부를 집어 든다
2단계, 전화번호부의 중간을 편다
3단계, 그 페이지를 살펴본다
4단계, 마크가 그 페이지에 있으면
5단계, 마크에게 전화를 건다
6단계, 만약 마크가 더 앞쪽 페이지에 있다면
7단계, 책 앞쪽의 중간을 펴서 살펴본다
8단계, 다시 3단계로 돌아간다
(여기서 3단계로 다시 돌아간다는 건, 앞서 말했던 “3단계 그 페이지를 살펴본다”라는 단계로 돌아가서 차례대로 다시 단계를 밟아간다는 뜻인데요. 근데 만약 앞쪽 페이지에 없다면 6단계는 아예 성립 자체가 불가능합니다. 그럼 이제 6단계를 건너뛰고 그다음 만약 단계로 이동하게 됩니다.)
9단계, 만약 마크가 더 뒤쪽 페이지에 있다면
10단계, 책 뒤쪽의 중간을 펴서 살펴본다
11단계, 다시 3단계로 돌아간다
(그리고 여기서 6단계도 해당하지 않고, 그다음에 나왔던 9단계도 해당하지 않는다면, 그다음 만약 단계로 넘어가게 됩니다.)
12단계, 만약 모든 상황에 맞지 않는다면
13단계, 이 탐색 행위를 종료한다
이런 식으로 알고리즘을 만들어낼 수 있습니다. 물론 앞서 말했듯이, 조금 더 쉬운 이해를 위해 우리가 사용하는 언어를 가지고 알고리즘을 구성해봤는데요. 이제 이 알고리즘을 컴퓨터의 언어로 변환만 한다면, 마크를 검색하는 빠른 알고리즘이 탄생하게 되는 것입니다.
해당 알고리즘의 방식을 컴퓨터의 언어로만 변환한다면 알고리즘이 탄생하게 된다.
이처럼 모든 알고리즘은 사전에 짜여진 특정 패턴을 가지고 작동하고 있는데요. 유튜브를 예로 들어 설명드리자면, 만약 사용자가 영상을 클릭하자마자 유튜브를 종료했다면, 해당 유튜버의 영상은 더이상 추천하지 않습니다. 혹은 영상을 클릭하고 오랫동안 시청했다면, 해당 유튜버의 영상을 추천 영상으로 띄우는 방식으로 알고리즘이 구성되어 있는 것입니다.
물론 실제 알고리즘은 이것보다 훨씬 더 복잡하고 정교하게 짜여져 있겠지만, 기본 방식은 이런 식으로 돌아가고 있습니다. 알고리즘은 어려운 게 아닙니다. 단순히 문제를 해결하는 단계적인 방법이 바로 알고리즘입니다.
- 한 줄 요약 : 알고리즘은 단순히 문제를 해결하는 단계적인 방법이다.
* 참고자료
모두를 위한 컴퓨터 과학 (CS50 2019) - David J. Malan
* 유튜브 : https://youtube.com/마크의지식서재
* 이메일 : marksknowledge@gmail.com
