Overview

• PS시 시간초과가 나지 않으려면 ?
• for문 안에 while문이 있으면 이중 loop이니 무조건 O(n^2)일까 ?

PS시 시간초과가 나지 않으려면 ?

• 보통은 대략 1억번(10^8) 정도의 연산이 일어나면 TLE (시간초과) 에러가 난다고 생각하시면 됩니다.
  • 즉, input이 10^4 개 라면 O(n^2)의 풀이로는 풀리지 않겠죠.
• 그치만 보수적으로 잡으면 대략 1천만(10^7)정도라고 생각하시는게 좋습니다.
  • 즉, 내 풀이가 1천만 이하의 연산을 한다면, 시간초과 걱정은 안 해도 되는것이고
  • 그 이상의 연산을 한다면 뭔가 잘못된게 있진 않을까 합리적 의심을 해볼 필요가 있습니다.

💡 왜 10^8번의 연산 횟수가 limit인데 보수적으로는 10^7번 정도로 생각하라고 했을까?

→ 그것은 O(n)이 사실상 O(k*n)이기 때문입니다. (k는 상수) : O(N) O(2N) 이나 둘다 O(N)이죠. 제 풀이가 O(N^2) 이라고 했을때, 1억번까지니 N이 10,000 까지 가능할 수 있겠다 생각할 수 있으나, 좀더 정밀하게 시간복잡도를 계산했을때 O(4N^2)가 나온다면 실제로는 N을 5,000까지만 받을수 있겠죠.

결국 이것은 O(N) 이라는 Big-O notation이 근사값이라서 발생하는 문제입니다.

• O(N) = O(2N)
  • N의 값이 2배가 되면 N도 2배 2N도 2배.
  • 반면, N^2은 4배, N^3은 8배 → 그만큼의 자원(컴퓨터)가 필요하다는 의미
    • 컴퓨터 1대로 지금의 일(task)가 겨우겨우 돌아간다.
    • 내가 돌리는 코드의 시간복잡도가 O(N^2)이다.
    • 이제 돌려야될 데이터의 양이 3배가 되었다.
    • 그럼 나는 컴퓨터가 총 몇대 필요할까?? → 9대
    → Big-O는 위와 같은 상황에서 필요한 자원을 계산하기 위해 나온 표기법이라, 결국 중요한건 곱해지거나 더해지는 상수가 아니라 변수N의 성장률이 어떠한가 입니다.

for문 안에 while문이 있으면 이중 loop이니 무조건 O(n^2)일까 ?

→ 답은 “아니다” 입니다.

아래 예시를 봅시다. 프로그래머스의 주식가격 문제에 대한 풀이입니다.

def solution(prices):
    answer = [0]*len(prices) # 미리 자리 확보
    
    # 규칙 : 요기서 stack은 value가 오름차순인 애들만 존재할 수 있다고 하자.
    stack = [] # (idx, price) 형태의 튜플로 넣어주기
    
    now_time = 0
    for idx, price in enumerate(prices):
        now_time += 1   
        while (stack and (stack[-1][1]>price)): # <------ 이곳에 집중합시다~!     
            top_idx = stack.pop()[0]
            lasting_time = now_time - (top_idx+1)
            answer[top_idx] = lasting_time
        stack.append((idx,price))
    
    while stack:
        top_idx = stack.pop()[0]
        lasting_time = now_time - (top_idx+1)
        answer[top_idx] = lasting_time

    return answer

for 문 안에 while loop이 있습니다. 대부분의 stack을 사용하는 문제 풀이가 이와 비슷한 형태죠. 각각의 Input에 대해 for loop을 돌면서 각 loop 안에서 while문을 통해 기존에 스택에 쌓아놓았던 요소들에 대한 비교 및 pop 등의 연산을 진행합니다. 보통 이중 loop이 있는 알고리즘은 O(n^2)이라고 생각하기 쉬운데요, 위 풀이의 시간복잡도는 O(n)입니다. 그 이유는 결국 while문 안에 있는 저 구문이 총 최대 O(n)밖에 실행될 수 없기 때문입니다.

(저 stack에는 인풋에 대한 요소들이 하나씩 append되어있는 상태인데 while loop 안에서 하나씩 pop됨. 아무리 많이 pop해도 결국 n번보다 더 pop할 수는 없음.)

비슷한 또다른 예시로, 프로그래머스의 더 맵게 문제의 풀이를 살펴볼 수 있습니다.

아래 풀이의 시간복잡도는 어떻게 될까요?

import heapq

def solution(scoville, K):
    # 스코빌 지수가 가장 낮은 애 + 두번째로 낮은애를 찾아야함. - min heap
    heapq.heapify(scoville)
    
    cnt = 0
    while len(scoville)>=2 and scoville[0] < K:
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        new = first + second*2
        heapq.heappush(scoville,new)
        cnt+=1
    
    # 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
    if scoville[0] < K:
        return -1
    else:
        return cnt

heap에 len(scoville) 만큼의 요소들이 들어가있겠죠. 그 상태에서 while문 안에서 어떤 일들이 벌어지는가를 보면, 기존요소 2개를 pop하고 새로운 요소 1개를 append 합니다. 그럼 이 while문은 아무리 많이 돌려져도 n보다 많이 실행될 수 없겠죠. 즉, 저 while 구문이 도는 횟수에 대한 시간복잡도는 O(n)이 됩니다.

다만 그 안에 heappush() 연산이 O(logn) 이므로 이 알고리즘의 최종 시간복잡도는 O(n*logn)이 됩니다.