시간복잡도(Time Complexity)

Y좌표는 실행 횟수, X좌표는 데이터 수라고 보면 되겠다.

위의 사진은 구글에 시간복잡도 혹은 Time Complexity로 검색하면 가볍게 찾을 수 있는 사진이다. 사실 이 개념에 대해서 명확히 알지 못했고, 또 전문적인 용어나 수식이 잔뜩나와 읽어보는 것을 항상 두려워했다. 그 이전에 알고리즘이라는 것을 푼다라는 것에 대한 생각도 거의 없었기 때문이다. 시간 복잡도, 즉 Time Complexity라는 것은 어떠한 Operation을 할 때에 얼마나 시간이 걸리는 지를 대강 파악하기 위해서 만들어진 추측값이다. 함수를 만들고, 그를 실행시켜서 걸리는 시간을 명확히 계산하기 어렵다.(프로그래밍을 본격적으로 공부하기 시작했지만, 거기에 대한 생각을 해본적도 없다. 근데 아마 방법은 있는 것 같다.) 그렇기 때문에 가장 단순한 방식으로 내부의 구동방식을 가지고 일종의 수식을 이용해서 시간예측값을 만들어 효율성을 판단하는 것이다. 비단 알고리즘 뿐 아니라, 어떤 프로그램을 작성하던간에 효율성을 따지는데에 가장 좋은 예측값이다.

시간복잡도는 결국, '배달의 민족'

배달은 속도가 제일 중요하다. 치타배달이니, 로켓배송이니 하는 것들이 나오게 된 것은 실제로 상품을 구입하고 소비자에게 오기까지의 시간을 줄여서 만족도를 올리는 것이 가장 큰 목적이다. 그렇다면 프로그램에서 만족도라고 하면 역시 퍼포먼쓰다. ㅋㅋ 얼마나 빠른 시간안에 얼마나 많은 데이터를 처리했느냐가 성능의 관건이다. 그렇다면 "효율쩌는 프로그램을 만들었다."라는 이야기는 곧 시간복잡도가 낮은 프로그램을 작성했다는 뜻이 되겠다.

시간 복잡도의 정의?

문제를 해결하는 알고리즘에 대한 로직을 작성할 때, 시간 복잡도를 고려한다는 것은 무슨 의미일까?

입력값의 증가/감소함에 따라 시간이 얼마만큼 비례하여 증가/감소하는가?

즉, 효율적인 알고리즘을 구현한다는 것은 바꿔말하면 입력값이 오지게 커져도 빠르게 문제를 해결할 수 있는 알고리즘을 만들었다는 이야기고, 이건 곧 시간복잡도가 낮은 프로그램을 구현해냈다고 볼 수 있다. 예를 들어보자.. 확 와닿는 주제를 가져오면 좀 더 빠르게 이해할 수 있으니까. 예를 들어 1부터 10까지 덧셈하는 간단한 함수를 짠다고 생각해보자.

let add = (el)=>{
  let sum = 0;
  for(let i = 1; i <= el; i++){
    sum += i;
  }
  return sum;
}

정말 기본적으로 자바스크립트로 작성할 수 있는 함수인데, add(10)을 하면 10까지의 합을 구할 수 있다. 근데 만약 이 데이터의 양이 243억이라면? 혹은 2000조라면? 2000조까지 for문만으로 감당할 수 있을까? 아마 어려울 것이다. 이걸 약간 응용해서 코드를 짜 본다면, 등차수열 공식 등을 이용해서 조금은 연산시간을 낮출 수 있을것이다. 시간복잡도를 낮춘다는 것은 결국 내가 짠 기능이 원활하게, 개빠르게 돌게하기 위한 삽질!이라고 생각해야겠다.

Big-O 표기법

시간 복잡도를 표기하는 방법엔 여러가지가 있는데
대표적으로,

• Big-O(최악) < !!important
• Big-Ω(최선)
• Big-θ(중간)

정도만 생각하면 되는 것 같다. 아무래도 내가 하고 있는 범위 내에서는 이정도 선인 것 같다. 그중에 가장 중요하게 생각해야 될 것은 Big-O인데 분명히 위에 적어 놓은 것처럼 최악(edge case)의 시간복잡도를 추측해보는 것이다. 최선의 경우나 평균적인 성능에 대해서 고려하지 않아도 된다는 이야기보다는 edge case의 극악무도함 때문인데, 위에 썼던 코드를 기준으로 생각해본다면 덧셈 코드가 반드시 '100정도 수에서만 계산하면 된다.'라는 법이 없기 때문이다. 애당초 OOP의 지향점을 생각해보면 쉽다. 확장성, 재사용성, 기타 등등.. (사실 잘 기억이 안 난다.) 객체 지향 프로그래밍에서 특정 case에 해당되는 기능을 구현한다는 건 마치

내 한계점은 여기까지니까, 추가적으로 필요하면 니(다른 개발자)가 만드세요! 앜ㅋㅋㅋㅋㅋ

라고 말하는 것과 똑같다. 만약의 가능한 한 상상할 수 있는 선에서 최악의 케이스까지 대응되도록 작성해둔다면 차후에 다른 기능에 동일한 함수나 모듈을 사용하게 된다고해도 알고리즘 수정없이 그대로 사용할 수 있을 것이다. 물론 좀 극단적으로 예를 들었지만, 사실 사용자(라고 쓰고, 나라고 읽는다.)는 예상범위 밖에서 움직이는 사람이 너무 많다. 나는 분명히 여기까지만 하라고 의도를 하고 기능을 구현하더라도, 어떤 사람은 그 기능의 한계점까지 몰아붙이는 변태(?)들이 많기 때문이다. Big-O 표기법을 중요시하는 이유를 알았으니 종류를 좀 알아보자.

Big-O 표기법 종류

1. 즉발즉딜, O(1)

즉발 즉딜이라고 쓴거는, 그냥 바로 쓰고 딜들어간다라는 얘기를 하고 싶어서다. 이름에 이미 constant라고 나와있는데 무슨말이 더 필요할까? 입력값이 증가하든, 말든 간에, 단박에 실행된다. 그게 O(1)이다. 그냥 뭘 넣던간에 바로 끝나는 것이라는 건데, 간단하게 예를 들어보면 arr[index]를 가지고 바로 값을 찾아오는 함수라던지 자기 자신의 값을 그대로 가지고 오는 underbar library의 identity()와 같은 것이 있겠다. 그냥 실행시키는 즉시, 답을 낼 수 있는 것들이 O(1)이며 복잡도를 계산할때 산입하지 않아도 되는 상수이므로 그냥 지나가면 된다.

2. 즉발은 아닌데, 갯수만큼 딜박는거임 O(n)
   

O(n)은 linear Complexity라고 부른다는데, 영어로는 감흥이 없다. 그냥 입력 값만큼 시간이 늘어나는 것을 의미한다. 아까 덧셈 예시도 마찬가진데, 범위가 n개 늘어나면 n회 더 실행해야되는 구조를 가진 것들이 전부 O(n)이다. for문으로 뭔가를 한다던지, 완전순회하는 것들이 그렇다. 100번 돌아야되면, 100번 실행하고 50번 돌아야되면, 50번 실행한다. 횟수만큼 시간이 늘어나는 것들이 O(n)이다.
순회가 몇개 있든간에 O(n)이다. 그냥 전체적으로 상황을 보는 것이기 때문에 순회가 늘어난다고 n이 늘어나는게 아니다. 그냥 전반적으로 이렇다를 이야기하는거다.

3. 가면서 딜이 약해지는 O(log n)
   

로그나왔다. 그렇다고 별거는 아니고, 그냥 넣는 값이 많아지면 늘어나는 시간이 적어지는 놈을 뜻한다. 알고리즘이나 함수가 실행되면서 순회케이스를 삭제하는 애들이 그런데, 예를 들어보자면 BST(Binary Search Tree)같은 탐색방법들이 그렇다. 탐색할 때 범위를 줄여주면서 값을 탐색하는데 범위가 넓어질수록 그 효과는 극대화 된다. 100만개를 찾아야될게, 10만개도 안찾고 답을 구할수도 있기 때문이다.
(BST : 이진탐색, 이분탐색, 이후에 다시 블로깅할 것. 어떤 데이터를 검색하는 과정에서 전부 순회하는 것이 아니라 유사한 부분을 추려내고 유사하지 않은 부분은 탐색하지 않도록 범위를 변화시키며 검색하는 방법)

4. 두 배로 느려지는 O(n^2)
   
   입력값이 늘어나면 제곱으로 시간이 늘어난다. 이 얘기는 순회속의 순회, 이중 순회를 도는 기능을 구현했다는 이야기가 된다. 삼중이든 사중이든 상관없이 O(n^2)로 표기한다. 순회를 돌면서 안에서 순회를 또 돌게되면 입력값이 증가하면 훨씬더 많이 증가하기때문에 데이터가 많을 경우 효율이 떨어진다. 일반적으로 주어진 데이터를 제곱해서 야 이게 내가 머릿속으로도 안그려지는 숫자다. 라는 생각이 들면 그냥 겹겹이 순회는 포기하는게 맞다. (물론 알고리즘을 푸는게 아니라면 상황에 따라서 할 수도 있겠지만,) 250조 이런 데이터를 처리할 일은 없겠지만 알고리즘에서는 잘 파악하고 적용하는 것이 좋다.

5. 2의 제곱으로 늘어나는 O(2^n)
   

exponential complexity라고 부르는데, 가장 가장 느린 최악의 시간복잡도다. 예전에 고등학교 수학을 공부했다면 아는 당연한 이야긴데, 쪽지를 무한대로 접을 수 있다면 길이를 무한으로 증가시킬 수 있다는 이야기가 있듯이, 정해진 상수를 n번 제곱한다는 이야기다. 2의 30제곱을 하게되면 10억번해야되고, 2의 40제곱은 이미 1조가 넘어버린다. n이 오를수록 미친듯이 느려지게되는데, 가능하면 어떤 상황에서도 이건 고려하지 않는게 좋겠다.
재귀를 여러 마리 부르면 이런 상황에 처할 수 있는데, 재귀 두마리가 엄청나게 많은 데이터를 처리하게끔 fibonacci를 구현하면 구하는 피보나치 숫자의 순번이 엄청나게 크다면 시간은 제곱만큼 걸린다.(연산이 계속 늘어나게 되니까..) 그래서 재귀를 쓸땐 항상 값을 저장해놓고 쓰는 방식을 기억해야한다. 그냥 쌩으로 두마리가 미친듯이 트리타고 내려가는 알고리즘은 절대 최악이다.

알고리즘 문제와 시간복잡도

사실 여기에 대한 얘기는 좀 길게하고 싶었는데 이미 졸리기 시작해서 글을 쓰기가 귀찮아지고 있다. 일단은 쓰는데까지 써보고 보충할 내용은 차후에 넣도록 하겠다.이틀간 페어분과 함께 알고리즘 문제를 풀었다. 스택, 큐, 트리 등의 선형적 자료구조를 공부하고 그를 이용한 알고리즘 문제, Graph로 최단거리 측정, BST로 입력인풋을 이용한 예측값을 빠르게 찾는 알고리즘, BFS/DFS를 통해서 케이스별로 사건을 잘게 쪼개서 답을 찾는 알고리즘, 그리디 알고리즘, 다이내믹 프로그래밍 기법부터 순열조합, 공약수와 소수까지. 다양한 문제들을 풀었다. 푸는 동안은 머리가 빠개지는 것 같았으나 진행되면서 조금 가닥이 잡힌 것은 있었다.

결국 모든 문제는 시간복잡도로 예상해서 Input Case를 처리하는 시간을 줄이는 가장 좋은 방법을 찾는 것

사실 어떤 문제를 봐도, 직관적인 판단으로는 문제를 풀 수 있겠다는 생각을 했는데 이건 인간인 내가 할 수 있는 생각이었다. 주어진 무게를 가지고 무게 제한에 맞는 짐들을 실어서 박싱해라 문제만 놓고보면 별게 아닌데, 컴퓨터에게 시키려고하니 피똥을 쌌다. 이게 무거운건지 이게 가벼운건지 조차 하나 하나 포인팅을 해줘야했고, 그걸 실어서 이게 맞는 무게인지까지 확인을 시켜줘야했다. 더불어 데이터의 갯수에 맞지 않는 알고리즘을 적용해서 시간 초과가 나거나 예외케이스를 잡아내지 못해서 무한루프에 빠지고는 했다.

그래서 뭘 느꼈지?

데이터와 아웃풋을 가지고, 범위를 예측하고, 시간복잡도로 적절한 방식을 대입해라.

내가 문제를 이틀간 집중해서 풀면서 느낀 것은 그거였다. 데이터와 아웃풋으로도 충분히 상황을 예측할 수 있다는 것과, 시간복잡도를 이용해서 데이터를 처리하는 방식이 어떤 것이라는 것 정도는 알 수 있다는 거였다. 그 상황을 파악할 수 있다는 것이 가장 중요하다고 느꼈는데, 아직 애매하게 다가오는 부분은 각 알고리즘들이 어떤 시간복잡도를 가지고 있는지 명확하게 판단하지 못하는 것과 input에서 벌어질 상황들을 예측하지 못하는 것이다. 이 얘기가 곧장 이어지는 건 여전히 인간적인 직관으로 문제를 접근한다는 점인데, 순차적으로 이루어져야하는 프로그래밍을 자꾸 내가 직접 해결한다고 생각하는 것이 가장 큰 문제인 것 같다. 예를 들어 1을 10번 더해서가 컴퓨터 과학적인 판단이라면 10이라는 아웃풋을 만들어야 한다.가 내가 노려보고 있는 명제인 상황이다.

그럼 뭘 해야 할까?

지금 당장 해야할 건, 순차적인 상황을 당연시하게끔 나자신을 개조해야한다.

1의 10개를 더하는 결과적인 이야기보다, 1을 10번 더한다는 것을 좀더 집중해서 생각해야한다. 10개의 숫자중 3개를 뽑아서 조합을 내가 만들어내야지라고 생각하는 것이 아니라, 어떻게 조합을 순차적으로 모든 조합을 만들어낼 수 있을까?라고 생각해야 한다는 이야기다. A->D 까지 가는건 내가 보니까 4개야.가 아니라 A에서 출발해서 D까지가려면 어디,어디,어디를 거쳐야 할까?를 생각해내야만 한다.

마치며

오늘 기록한 것은 알고리즘을 풀면서 느꼈던 것들에 대해서 적고 싶었다. 시간 복잡도에 대한 개념과 그게 알고리즘 풀이에서 얼마나 중요한 것인지, 현재 상황을 이해하는 잣대로서 얼마나 중요한 것인지 스스로가 깨닫기를 바라며 적었다. 차후에 어떤 문제를 만나더라도 티끌모아 태산이라는 표어는 잊지말자. 나는 뇌가 있어서 예측을 하고 순간 답을 만들어낼 수 있지만, 프로그래밍은 하나부터 열까지 순차적으로 만들어지는 것이라는 것을 잊지말자.