분할 정복(Divide and Conquer)이란?

분할 정복(Divide and Conquer)이란?
말 그대로 나눠서 정복한다는 뜻으로
그대로 해결할 수 없는 문제를 작은 문제로 나눠 각각 해결하는 접근법을 말한다.

분할 정복 예시

10^11을 계산한다고 가정해보자
10*10을 11번해야한다.

백준 18258

https://www.acmicpc.net/problem/18258

import sys
from collections import deque 
input = sys.stdin.readline


N=int(input())
queue = deque()

for _ in range(N):
    commands = list(input().split())
    if commands[0]=='push':
        queue.append(commands[1])
    elif commands[0]=='pop':
        if queue:
            # print(queue.pop(0))
            print(queue.popleft())
        else:
            print(-1)
    elif commands[0]=='size':
        print(len(queue))
    elif commands[0]=='empty':
        if(len(queue)==0):
            print(1)
        else:
            print(0)
    elif commands[0]=='front':
        if queue:
            print(queue[0])
        else:
            print(-1)
    elif commands[0]=='back':
        if queue:
            print(queue[-1])
        else:
            print(-1)

print(queue.pop(0))로 풀었는데 '시간초과'가 났다.
그래서 원인을 봤더니 queue.pop(0)에서 pop연산이 O(N)이라
시간초과가 났다. 그래서 이걸 어떻게 시간복잡도를 줄여야하는 상황인데
queue를 deque로 선언해서 popleft로 선언하면 시간복잡도 O(1)로 연산이 가능해진다.

느낀 점

그냥 이용하던 기본 메서드에서도 시간 복잡도 차이로
실행시간 차이가 날 수 있다는 걸 알게되었다.