[문제 해결 기초] 빅오표기법과 시간복잡도....! 내가 다 해결해줄게!

해결사 우기 등장..!

 

안녕하세요 우기의 정신차린 취준일기입니다. 삼성 코딩테스트에서 떨어진걸 직감했지만 저의 부족함을 알게되는 계기가 되었습니다. 바로 ... 시간복잡도와 빅오표기법을 계산하여 문제를 해결하는 능력이 부족했다고 생각합니다. 하반기를 위해서라면 이런 기초적인 문제들을 빨리 해결하는것이 낫겠죠? 지금 한번 해결하러 가봅시다 !

 

❤ 점근적 표기법

점근적 표기법 부터 알아봅시다. 

점근적 표기법에는 간단하게  O, Ω, Θ 가 존재합니다.  빅-오, 빅-오메가, 빅-세타라고 표현을 하지만 저희는 빅-오만을 다루겠습니다. 

O는 간단하게 가장 높은 차수보다 같거나 높은 식을 의미합니다.

 

O는 가장 높은 차수를 의미하는게 아니야? 난 항상 그렇게 배웠는데요? 

* n3+n2+n−1  (n뒤에있는 숫자를 제곱이라고 생가해주세요)  를 예시로 들어보겠습니다. 가장 높은 차수는 n3이라고 해봅시다. 그렇다면 O(n3), O(n4), O(n100) 이든 다 맞은 의미가 됩니다. 즉 가장 높은 차수의 숫자 혹은 그 이상을 의미하는것이 빅-오 표기법이라고 하는것입니다. 그러나 우리는 좀 더 tight하게 O(n3)이라고 다들 부르는것입니다. 

 

간단한 문제풀이를 해볼까요? 

 

🧡점근적 표기법 문제풀이

 

간단한 식이 주어졌습니다. 

 

💛1. O(f1) = logx ?

O(f1) = logx 는 참이라고 할수있을까요? O(x2) = logx 라고 전환한다고 가정한다면, O(g(x))= f(x)가 성립이 되어야하겠죠? 

x를 무한대로 증가시킨다면 항상 x2는 logx보다 크기 마련입니다. f(x)가 무엇이 되었든 O(g(x))는 f(x)보다 커야된다는 성지릉ㄹ 이용한다면 정답이 맞습니다. 

 

💛2. O(f2) = xlogx ? 

이또한 x!-xlogx +(x(x))은 도 똑같이 xlogx보다 크면 된다는 이야이기입니다. xlogx보다  x(x)이 크기 때문이 이또한 참이 될수 있다는 말이죠. 

 

지금까지 빅오표기법을 알아보았습니다. 빅-세타, 빅-오메가도 있기마련이지만 우리는 문제를 해결하기위해서 잠시 뒤로 미룬다는 가정하에 빅오표기법을 통한 시간복잡도를 이해해볼 가치가 존재합니다.

 

 

❤시간복잡도란?

시간복잡도를 알아보겠습니다

간단히 말해 프로그램이 잘 짜였는지, 비효율적으로 짰는지 알아보기위해 코드를 분석하여 효율성을 따져야합니다. 그리하여 코드를 시간적으로 분석할지, 공간적으로 분석할지 많은 고민들을 하게됩니다. 시간적으로 분석한다는 가정하에 얼마나 적은 연산으로 코드를 짰는지 더 중요하지않을까요? 코딩테스트에서도 마찬가지입니다. 답을 맞추었지만 문제의 제한적인 시간이 주어진다면 그 시간대에서 효율적으로 코드가 돌아갈수있게끔 개발자가 작성해야된다는것입니다.

 

그런데 중요한건 그건 어떻게 하냐는것입니다. 어떻게 내가 이걸 알까...? 문제 푸는것도 복잡해죽겠는데 내가 왜해야됩니까? 라는 질문을 할수도있습니다. 당연히 어렵습니다 맨처음은. 우리에게 중요한건 1솔 그 이상입니다. 1제출은 의미가없죠. 

자, 이제부터 어떻게 해결해야하는지 조그마한 TIP을 드리겠습니다.

값을 대입하는것은 O(1) 이라는 시간복잡도, 반복문을 통해서 1부터 n까지 돌아가는것은 O(n)이라고 합니다. 

보통 반복문 (for,while)을 사용할때 1억번을 사용하면 시간이 1초정도 걸립니다 (컴퓨터 기준) 

코딩테스트에서 N의 범위를 항상 주어질 것입니다. 그 N의 범위를 계산하는것이 제일 낫겠죠? 

제한시간 1초인 경우에 대해 떠올린 솔루션의 시간복잡도를 O로 계산했다고 가정하에 생각해봅시다. N의 범위에 따라 우리는 제한 시간안에 올바른 답이 나오는 솔루션인지를 생각해보면 됩니다. 

 

🧡 기초적인 시간복잡도 예시 

 

기본적인 시간복잡도

외우라는 의미가 아닙니다. 왜 그런지 생각을 해보고 문제를 접해보자는것입니다. 이렇게만 이해한다면 우리는 분명히 1솔이아닌 1제출도 가망이 없습니다. 

 

왜냐면 나의 코드는 N2인지 N3인지 logN인지 내가 판단해야하기 때문입니다. 나의 코드를 분석하기위해서 이또한 예시를 들어봐야 될것같습니다.

 

🧡시간복잡도에 대한 나의 코드 해석  O(NM2) 이 맞을까요?

 

예시 수도.

언뜻보면 for문은 3개로 인하여 NM2이라고 생각하기 마련입니다. 

 

set num = 0  : 대입이라 O(1)

set visited = [n][m] : 시간복잡도가 아닌 공간복잡도에 더 가깝다고 생각합니다. 

for i= 1 ...i <=n  : 1부터 n+1까지 점차 증가합니다 1..2..3..4..5..N...N+1 <- O(N+1) 이지만 상수값을 버려  O(N)

for j= 1 ... j<=m : 1부터 m+1까지 점차 증가합니다 1..2..3...M+1 <- O(M+1)이지만 상수값을 버려 O(M)

그렇다면 O(N) 안에 O(M)이 증가합니다. 이 둘은 O(NM)이 됩니다.

if(visited[i][j]==0) : O(1) 그 범위만 확인하면되는 부분

for k =j .... k<=m : 여기가 관건입니다. j가 1일때, 모든 visited[i][k]는 1로 만들것입니다. 즉 j가 2이상 m이하일때 k-for문은 작동하지 않으며, 다음 i값으로 넘어가야만 k-for문이 실행될것입니다. 즉 k-for문은 j가 1일때에만  동작합니다. 그 시간 복잡도는 O(M)이 되는것입니다.  그 외 k - for문은 j가 1일때에만 동작합니다. O(1)이 걸린다는 소리입니다.

 

결국 다시말해 for j는 O(M)이 아니라  O(M) + O((M-1)*1) = O(M)이 된다는것입니다. 이해가 되지않는다면 추가설명 드리겠습니다.  j-for문은 1~m까지 반복문을 돌지만 case가 2개 라는 소리입니다. 

case 1 : j가 1일때

case 2 : j가 2이상일때

case 1 : j가 1일때에는 j는 1번, k는 M번만큼 돈다 (1*M)

case 2:  j가 2일때에는 j는 1번을 제외한 M번 ( M-1)번, k는 if만 확인한다 (1)    (M-1)*1

case 1,2는 각각 다른상황에서 일어나는 일이기에 (1*M) + (M-1) *1 = O(M)이 되는것입니다. 

 

눈으로 얼추보면 NM2이겠지만 조건과 case를 나누게된다면 O(NM)입니다. 

 

❤ 마무리하며

 

시간복잡도 N의 크기를 생각하고, 나의 코드를 조금만 더 분석하여 지켜본다면 우리 모두 1제출이 아닌 1솔을 하지않을까 생각이 듭니다. 여러분들 저처럼 시간초과나서 코테 떨어지지 마시구요 ㅠㅠㅠㅠㅠ... 이정도면 기본적인 시간복잡도, 빅오표기법이 되지않을까 생각이 듭니다. 

추가적인 질문이나 추가적인 내용이 필요하시면 항상 말씀해주세요 이상 우기의 정신차린 취준일기였습니다.