알고리즘과 시간복잡도

백준 시간복잡도 파트 풀다가 오셨다면 어서오십쇼.

---

일단 알고리즘 알고리즘 들어는 봤는데 이게 뭐임? 알고리즘은 '문제를 해결하기 위한 절차나 방법'을 뜻한다. 뭐 예를 들자면 방에 형광등이 나갔으면 갈아야 할 거 아님? 가는데 절차 있잖아요. 무작정 형광등 떼내고 교체하는 게 아니라 불이 꺼졌는지 확인하고(안그러면 피카츄 10만볼트 맞고 날아가는 로켓단 간접체험한다), 고장난 형광등을 떼고, 새 형광등 포장을 뜯고, 끼운다. Profit? 이런 느낌이다. 그러니까 우리가 자각하지 않더라도 어떤 문제를 해결하는 데에는 논리게이트와 알고리즘이 쓰이고 있다. 물론 CPU는 당신 두개골 안에 있는 세레브럼이고요.

 

유기체의 4대 조건이 있다. 살아있는 생물이고 유기체라면 다 가지고 있어야 하는 필요조건인데, 바로 탄수화물, 지질(lipid), 단백질(아미노산), 핵산(DNA, RNA). 생각해봅시다. 우리 포도당 어디다 저장해요? 근육이나 간에서 뭘로 저장함? 그죠 글리코겐으로 저장합니다. 지질 하면 잘 와닿지 않겠지만 지방산(대둘레햄)과 스테로이드가 지질의 하위 카테고리다. 세포를 구성하는 세포막도 지질인데, 인지질 이중층으로 이루어져 있어서 세포의 안과 밖을 구별하는 경계 역할을 한다. 왜 세균을 조사버릴때 세포벽을 깨버리는지 잘 생각해보면 아실 것이다.

 

단백질은 뭐 다들 아시잖아요? 아이 왜그래요 이맘때쯤 몸 만든다고 찌찌살 먹잖아... 우리 몸에서 단백질은 그냥 안 들어가는데를 찾는 게 빠를 정도로 광범위한 곳에 쓰이는데, 근육은 물론 항체(150KDa정도), 호르몬(인슐린/글루카곤 등), 머리카락(케라틴) 등... 온갖가지 곳에 다양한 형태로 쓰인다. 핵산은 우리 몸에 있는 DNA, RNA가 핵산이다. 영칭은 뉴클레익 애시드.

 

뜬금없이 생물학이라니 무슨 빌드업이죠! 아잇 들어봐요. 알고리즘에도 조건이 있다 이 얘깁니다. 유기체의 4대 조건처럼, 알고리즘도 어떤 조건을 만족해야 된다. 근데 막 어려운 건 아니고...

 

1. 입력: 0 또는 그 이상의 외부 입력
2. 출력: 돌려서 최소 하나 이상의 결과가 나와야 한다.
3. 명확성: 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다. 
4. 효과성: 알고리즘의 모든 연산들은 사람이 수기로 유한한 시간에 정확히 수행할 수 있어야 한다. 
5. 유한성: 알고리즘의 각 단계는 유한한 횟수여야 한다. 

 

이건 5대 조건인감... 아무튼. 엥? 입력이 없는데 출력이 나올 수 있어요? 당장 꺼무위키 들어가서 언어별 Hello, World! 예시만 봐도 입력 없이 실행하면 헬로 월드 출력해준다. 참고로 명확성은 단계별로 명확해야 하는거지 뉴비가 보자마자 이게 무슨소리야를 외칠 수는 있다. 실력차이에 따라 이해 못 하는건 정상이다. 그래서 개발자는 끊임없이 공부하지 않으면 도태된다.

---

그럼 이제 시간 복잡도 얘기를 해봅시다... 시간 복잡도는 빅 오, 빅 오메가, 빅 세타 표기법이 있는데 여기서는 빅 오만 다룰거다. 나머지 두개는 나도 모름. 예를 들어보자. 형광등을 갈 때 스위치가 꺼진 걸 확인하고, 형광등을 빼고, 포장을 뜯고, 끼운다. 이런 식으로 갈 수도 있지만 형광등 포장을 불 끄기 전에 미리 깔 수도 있다. 실험을 예로 들어보자. 배지에 대장균을 배양하기 위해서는 크게 배지를 만들고, 균을 배양한다음, 배양기에 넣는 절차를 거치는데 이 때 실험하기 전에 미리 필요한 배지를 파악하고 만들어둘 수 있다. 그러면 배양하고 인큐베이터에 넣기만 하면 끝이다.

 

이게 근데 왜 필요한가요? 위에서도 생각했지만 뭐든지 효율적으로 해야 한다. 형광등을 갈 때 포장을 미리 뜯은 다음 불이 꺼진 걸 확인하고 바로 형광등을 교체하듯이 말이지. 어떤 코드를 실행하는데 10분 걸리는거랑 1분 걸리는거랑, 후자가 더 효율적이다. 그죠? 이거 잘못하면 개적화 헬적화 발적화 폴제트 물리엔진 되는겁니다... 잘 생각해보면, 백준을 풀 때 분명 이렇게 해도 되는건데 시간초과 나서 틀린 경험이 있을 것이다.

 

세 가지 표기법 중 빅 오 표기법은 O(n) 이런 식으로 쓰고, 대충 얘가 암만 느려봐야 이게 최대로 느린거임! 이라는 의미로 쓴다. 천장같은건데... 이것도 여러가지가 있다. O(1), O(n), O(n log n) 뭐 이런 식으로. 저 괄호 안에 들어가는게 뭐냐에 따라 실행 시간이 달라진다. 언제? n의 값에 따라. 일단 위키피디아에 보면 뭐가 많은데, 자주 보는 것들 위주로 함 쓱 보고 가자. 일단 나도 예시를 그렇게 많이 아는 편은 아니라서, 1부터 10까지 이 시간 복잡도로 했을 때 어떻게 되는지 수치만 간단하게 보여주겠다. 

 

O(1): n의 값에 상관없이 항상 값이 일정하다.

가장 빠르고 이해하기 쉬운 예시는 검색엔진. 봐봐요 구글에 피카츄 치나 파라블레이즈 치나 중간에 서버 관리자가 서버실에 커피를 쏟거나 인터넷 먹통되는 것만 아니면 뜨는 데 걸리는 시간 똑같잖음?

 

O(log n): 로그

일단 뜬금없이 float로 나오는 것에 대해서는 양해 바람... 로그는 로그인데 밑이 2다. 이진 탐색 알고리즘의 시간 복잡도가 보통 이거인데, 이진 탐색은 대충 업앤다운 같은 개념으로 찾는거라고 생각하시면 된다. 다만, 이진 탐색 알고리즘을 쓰려면 먼저 '정렬이 되어 있어야'한다.

 

O(n): 선형

평범한 선형이다. y = x인가?

 

O(n log n): 선형로그

점점 값이 산으로 가는 것 같다면 기분탓이다. 젤나가도 맙소사 할 선형+로그의 혼종.

 

O(n^2): 다차

위는 2제곱(2차), 아래는 3제곱(3차). 당연한 소리지만 다 차라는 얘기가 아니다...

 

O(2^n): 지수

밑은 2의 n제곱, 아래는 3의 n제곱. 다차와의 차이가 뭐냐면 지수는 n이 위로 갔다. 블랙핑크 아니니까 그분 찾아 오신거면 들어가세요.

 

O(n!): 계승(팩토리얼)

사실 쌉고수들이 이 글에 들어올 리는 없고... 본인과 비슷한 수준이라는 전제하에, 빅 오 표기법과 시간복잡도에 대해 이미 어느정도 들어봤다면 다차에서부터 슬슬 이거 망조 아닌가 싶었을거다. 힙 정렬, 퀵 정렬같이 그나마 좀 빠른 알고리즘의 시간복잡도도 선형로그 선에서 끝나니까.

 

시간복잡도가 팩토리얼이면 그 알고리즘은 조졌다는 얘기니까 다시 짜시길 바란다.