슬슬 졸업하고 취업할 나이가 되어서 코테를 준비하기 위해 오랜만에 알고리즘 문제들을 풀어보았다.
그런데 PS를 좋아하는 내가 쉽게 풀 줄 알았으나 생각보다 많이 어려웠다.
그러다 고등학교 때부터 알고리즘이 뭔지 계속 물어보던 찬우(문과)가 생각났다.
늘 설명해도 비전공자 입장에서 직관적으로 설명되지 않은 것 같아서 찜찜했는데, 이 참에 알고리즘 개념에 대해 다시 한 번 정리하고 비전공자 입장에서 이해가 되도록 정리해보고자 한다.
(최대한 모두가 이해할 수 있도록 하였으나 논리에 오류가 있거나 이해가 안 되는 부분이 있다면 댓글로 알려주길 바란다.)
그래서 알고리즘이 뭔데?
위키피디아에 정의된 알고리즘은 다음과 같다.
- 문제 해결 방법을 정의한 일련의 단계적 절차이다.
- 계산을 실행하기 위한 단계적 절차를 의미하기도 한다.
- 문제 풀이에 필요한 계산 절차 또는 처리 과정의 순서를 뜻한다.
그동안 찬우에게는 위 내용들을 말하며 함수랑 비슷하다고 하였다.
이 말을 들은 찬우는 늘 "그래서 알고리즘이 뭐냐니깐?"이라는 말로 되물었다.
그래서 나는 "함수"에서부터 다시 한 번 생각해보려고 한다.
위 그림은 우리가 함수를 배울 때 봤던 그림이다.
X라는 값을 함수 f(x)에 넣으면 어떠한 계산과정을 뚝딱뚝딱 걸쳐서 Y라는 값을 반환하게 된다.
이러한 함수의 예시로 bmi 공식을 떠올려보자
자신의 몸무게(kg)를 키(m)의 제곱으로 나눈 값이
18.5 이하면 저체중
18.5 ~ 22.9 사이면 정상
23.0 ~ 24.9 사이면 과체중
25.0 이상이면 비만
이 bmi 공식을 위의 (그림1) 처럼 표현하면 어떻게 될까?
바로 위 그림처럼 된다.
실제로는 bmi가 비만의 절대적인 척도가 되지는 않지만, 단순 키와 몸무게만으로도 비만인지 아닌지를 얼추 짐작할 수 있게 되었다.
이처럼 우리는 가진 정보 X(키와 몸무게)를 이용하여, 계산(bmi)함으로써, 원하는 정보 Y(과체중)를 얻어냈다.
이 과정에서 사용한 계산 과정을 바로 알고리즘이라고 한다.
그렇다면 "알고리즘이라는 것은 bmi와 같은 공식들을 의미한다는 것인가?"라는 의문을 품을 수 있다.
얼추 비슷하지만 관점이 많이 다르다.
알고리즘은 우리가 원하는 정보를 얻기 위한 "과정"이고, 공식은 이 과정 속에서 사용하는 "도구"와 같다.
원하는 정보를 빠르고, 정확하고, 기성품처럼 만들 수 있는 것을 알고리즘이라고 생각하면 이해하기 편하다.
물론 위의 나온 내용만으로는 함수와 알고리즘에 대한 차이를 잘 못 느낄 수 있다.
그래서 알고리즘을 좀 더 직관적으로 이해할 수 있는 "볼록 껍질 알고리즘"을 예시로 들어보겠다.
볼록껍질 알고리즘이란?
스티로폼 위에 여러 개의 압정들이 꽂혀있다고 가정해보자.
여기에 고무줄도 있다고 가정해보자.
여기서 고무줄을 탁 놓는다면 어떻게 될까?
바로 이렇게 될 것이다.
이처럼 ①점들의 집합을 전부 포함하는 ②볼록 다각형 중에 ③가장 작은 볼록 다각형을 볼록 껍질이라고 부른다.
우리는 9개의 점들과 고무줄을 사용하여 볼록 껍질을 만들었지만, 만약 점의 개수가 10만, 100만 단위가 된다면 볼록 껍질을 어떻게 찾을까?
이때도 고무줄과 압정을 이용할 것인가?
이럴 때에는 우리는 사고 과정을 바꿔야 한다.
압정과 고무줄으로만 볼록 껍질을 찾기에는 매우 비효율적이고 복잡한 일이다.
그래서 1972년에 로널드 그레이엄(Ronald Lewis Graham)이라는 수학자가 한 가지 사고 과정을 고안하였다.
바로 그레이엄 스캔(Graham Scan)이다.
그레이엄 스캔(Graham Scan)이란?
갑자기 웬 어려운 단어들이 나오는가 싶지만 결국엔 알고리즘의 본질을 깨닫고자 예시를 드는 것임을 명심해야 한다.
우리는 위에서 언급하였듯이 모든 볼록 껍질을 압정과 고무줄만으로 찾기에는 매우 비효율적이다.
그래서 나온 것이 그레이엄 스캔이다.
일단 이 사고 과정에 대해 차근차근 읽어보고, 곰곰히 생각해보자.
0. 점들이 좌표평면에 있다고 가정해보자
1. 점들 중 y축이 가장 작은 점을 기준점 P로 잡는다.
2. 기준점을 제외한 모든 점들을 기준점 P와 연결하고, 동경을 측정한다.
3. 동경이 작은 순서대로 순서를 부여한다.
4. 기준점을 시작점으로 하여 각 점들을 순서대로 잇되, 2가지 규칙을 따른다.
4-1. 이전 선에서 반시계 방향으로 회전하면 선을 잇는다.
(시작점 ~ 1번점) 선에서 (1번점 ~ 2번점) 선으로의 관계를 보면, 반시계 방향으로 돈 것을 알 수 있다.
4-1 규칙을 통해 2번 점과도 선을 잇는다.
4-2. 이전 선에서 시계 방향으로 회전하면 이전 선을 삭제하고, 반시계로 회전할 때까지 반복한다.
(2번 점 ~ 3번 점) 선에서 (3번 점 ~ 4번 점) 선으로의 관계를 보면, 시계 방향으로 돈 것을 알 수 있다.
4-2 규칙을 통해 (2번 점 ~ 3번 점) 선은 삭제한다.
5. 모든 점에 4번 규칙을 적용하여, 끝점과 시작점을 마지막에 잇는다.
마무리하며..
우리는 위 내용들을 통해 고무줄과 압정이 아닌 좌표평면을 사용하여 볼록 껍질을 효율적으로 찾는 방법을 알아냈다.
위 내용에서 정렬 알고리즘, CCW 알고리즘 등 다루지 않은 과정들이 있지만 그 부분들은 생략하였다.
사실 이것만 봐서는 고무줄과 압정을 이용하여 볼록 껍질을 구하는 방법이 더 빠르지 않냐고 생각할 수 있다.
하지만 이 과정을 컴퓨터로 진행한다는 것을 인지해야 한다.
컴퓨터 내에서 압정을 박고 고무줄을 놓는 것을 "시뮬레이션" 돌릴 바에야, 그레이엄 스캔으로 "연산"만 하는 것이 컴퓨터 입장에서 훨씬 빠르기 때문이다.
이처럼 어떠한 문제를 해결하기 위해 효율적이고, 정확하고, 유한하게 연산하여 원하는 정보를 얻어내는 과정을 알고리즘이라고 한다.
최근 우리는 "유튜브 알고리즘", "음악 알고리즘" 등과 같이 "알고리즘"이라는 단어를 굉장히 많이 접해왔다.
이 알고리즘들은 "볼록 껍질 알고리즘"과는 비교가 안 될 정도의 복잡한 연산과 입력값을 다룬다.
그래서 좀 더 좋은 알고리즘을 위해 개발자들은 연산 과정을 계속해서 검토하고 수정한다.
이러한 과정들을 있기에 소비자들은 좀 더 좋은 서비스를 누릴 수 있는 것이다.
자, 알고리즘에 대해 많은 예시를 들며 설명해보았다.
알고리즘에 대한 막연한 궁금증이 이 글을 통해 어느 정도 해소되었으면 좋겠다.