[프코문] chpater2. 시간 복잡도

시간 복잡도란?

• 어느 알고리즘이 더 나은지 비교할 수 있는 기준이 필요함
• 프로그램이 동작하고 결과를 만들어내는 데 걸리는 정도를 복잡도라고 함
  • 시간 복잡도: 얼마나 오래 걸리는지
  • 공간 복잡도: 얼마나 많은 메모리를 사용하는지
• 코딩 테스트에서는 두 복잡도에 대한 조건이 함께 제시됨 → 몇 초/몇 MB 이내
  • 문제나 언어마다 주어진 시간이 다르지만 프로그래머스는 특별히 언급하지 않으면 제한 시간이 10초임
  • 10초??? … 이를 이해하려면 먼저 우리가 짠 코드를 어떻게 시간으로 나타낼 수 있는지 알 필요가 있음

빅오(Big-O) 표기법

• SW나 HW적 변수가 많아 똑같은 코드라도 환경에 따라 실행 시간이 조금씩 다름
  • 이 때문에 시간을 정확한 수치로 나타내긴 어렵지만, 문법이나 구성에서 발행하는 비용을 수치화해 문제를 푸는데 필요한 총 연산의 수를 수학적으로 표기할 수 있음 ⇒ 점근 표기법
    • 3가지 표기법 중 가장 흔하게 사용. 최악의 경우를 생각하는 빅오(Big-O) 표기법에 대해 알아보자.
• 빅오 표기법: 알고리즘이 해당 차수이거나, 그보다 낮은 차수의 시간 복잡도를 가지는 점근적 상한 표기 방법을 의미함
  • 쉽게 ‘최악의 경우 이 정도의 시간이 걸린다’로 이해하면 됨
• n² + 2n + 1의 시간 복잡도: O(n²)
• 99n의 시간 복잡도: O(n)
  • 연산 횟수가 최고 차항에 비례하는 흐름을 보인다면 부가적인 연산은 신경 쓸 필요 없음(많은 데이터를 입력하면 연산횟수가 차이나기 때문에 작은 수는 상대적으로 무시할 수 있음)
    • 4n²과 4n을 비교: 10만개 입력 → 연산 횟수: 400억, 40만 정도로 차이 남

시간 복잡도 그래프

 

• 표: 입력 데이터 수에 따른 연산 횟수
• 1, 2, 3, 4, 8, 16, 32, 64, 1000 .. : 입력 데이터 수 n
• 연산횟수가 표 아래로 향할수록 기하급수적으로 늘어남
• 만약, 문제에 주어진 데이터 수가 10만 개고, 사용하는 알고리즘의 시간 복잡도가 O(n²)이라면 10만 x 10만으로 100억 번 연산을 수행하게 됨
  • 컴퓨터는 보통 1초에 1억번 연산하므로 이 프로그램은 동작하는데 100초가 걸린다는 결론을 낼 수 있음
• 문제에서 주어진 입력값의 최대 크기가 10만 개라면 시간 복잡도가 O(nlogn) 정도인 알고리즘으로 풀어야 한다는 것을 알아야 함 → O(n²) 시간 복잡도인 알고리즘으로 풀면 높은 확률로 시간 초과가 발생해 테스트에 실패함
  • 🤔 왜??
    💡 입력 크기가 n=10⁵인 상황에서 시간 복잡도를 비교해보자
    

    • O(nlogn) 알고리즘:
      • logn은 대략 log₂(10⁵) ≈ 17 정도
      • 따라서 O(nlogn)의 경우 실행 시간이 10⁵ × 17 ≈ 1,700,000 정도의 연산 횟수로 추정됨
    • O(n²) 알고리즘 :
      • 만약 O(n²) 알고리즘을 사용한다면, 실행 시간이 10⁵ × 10⁵ = 10¹⁰ = 10,000,000,000 (100억) 번의 연산을 요구함
      • 이는 실제로는 매우 많은 시간이 걸려 성능에 큰 영향을 미치게됨

    • 시간 제한
      • 대부분의 컴퓨터는 초당 약 1억 번 정도의 연산을 처리할 수 있다고 가정  
        • O(nlogn) 알고리즘은 1,700,000번의 연산으로, 1초 안에 충분히 처리할 수 있음
        • 하지만 O(n²) 알고리즘은 10¹⁰번의 연산이 필요하여, 100초 이상 걸릴 수 있음

O(1)	입력 데이터 수 크기와 복잡도 상관없이 항상 상수(고정된 시간)을 가지는 알고리즘 ex) 내림차순, 오름차순 정렬 데이터, 해시 테이블의 삽입, 삭제, 검색
O(logn)	크기가 커질수록 처리 시간이 짧아지는 알고리즘 아주 많은 데이터가 존재하더라도 매우 짧은 시간에 끝나기 때문에 이상적인 알고리즘이라 할 수 있음 ex) 이진탐색 → 탐색 범위가 ½씩 줄어듬
O(n)	입력 데이터 수만큼 정직하게 시간을 소모하는 알고리즘 O(n) 알고리즘이 2번 중첩되도록 유도하는 문제에서 이 알고리즘을 사용하면 O(n²)가 되어 시간이 매우 길어지므로 항상 조심해야 함  ex) 배열 탐색이나 초기화, for문 1개 사용, 문자열 탐색, 데이터 재구축 등 입력 데이터를 다루는 동작 대부분
O(nlogn)	입력 데이터 수에 비례해서 연산이 추가로 필요한 알고리즘 정렬을 사용한다면 무조건 이 정도의 시간이 걸린다고 봐도 무방함 주어진 데이터를 ‘정렬’하라는 문제라면 이 시간 복잡도로 끝내야 통과할 수 있음 O(n) × O(logn) 처럼 조합되는 알고리즘 또한 이 경우에 해당하므로 생각보다 자주 보게 될 것임
O(n²)	입력 데이터 수의 제곱만큼 시간을 소모하는 알고리즘 입력 데이터가 제법 큰(10만 개 이상) 문제에서 이 알고리즘을 사용하면 높은 확률로 시간이 초과됨 자주 만들고 사용하는 알고리즘이 대부분 여기에 속함 ⇒ 이 정도 시간 복잡도라면 괜찮겠지 라고 생각하면 안됨 → n²기반으로 연산하면 다른 부가 연산이 필요할 경우 부담되므로, 전략적으로 사용해야 함 ex) for문 2개 중첩, 배열끼리 값 비교or조작, 2차원 배열
O(2ⁿ) 이상	입력 데이터 수가 정말 저거나 특수한 조건이 있을 때만 사용하는 시간 복잡도 구해야 하는 숫자가 커질수록 이전 결괏값을 전부 계산해야 하기 때문에 연산 횟수가 기하급수적으로 늘어남 ex) 피보나치의 수

시간 복잡도 선택 시 참고할 만한 사항

1. 최대 시간이 1초일 때 입력 데이터 수에 따른 시간 복잡도
   • 1,000개라면 → O(n²) 이하
     • 1000*1000=100만
   • 10,000개라면 → O(n²) 미만(최대한 적게 사용하는 방향으로)
     • 10000*10000=1억
   • 100,000개라면 → O(nlogn) 이하
     • logn은 대략 log₂(10⁵)≈17 정도
     • 100000*17=1700000=백 칠십만
     • O(n²)을 사용하게 되면, 10000000000으로 백억..!
   • 1,000,000개라면 → O(nlogn) 미만(가급적 O(n) 정도로)
     • logn은 대략 log₂(10⁵)≈17 정도
     • 1000000*17=17000000=천 칠백만
   • 그 이상이라면 → 입력 데이터 수가 백만 개 이상이라면 문제의 조건을 유심히 살펴봐라. 특정 알고리즘을 사용하도록 요구할 가능성이 큼
2. 자주 사용하는 자료 구조의 시간 복잡도

시간 복잡도 계산하기

어림짐작해보기

• 해당 구구단만 연산하는 경우와, 해당 구구단부터 9단까지 전부 연산하는 경우
  • for문을 1번 썼으니 O(n)이고 for문을 2번 썼으니 O(n²)일까? → 아니
  • 주어진 숫자의 9단까지만 출력하는 함수의 경우 1번 입력하고, 9번 연산을 수행함
    • 입력이 10만 개라면 10만 개 × 9이고, 이는 곧 9n이므로 O(n)이라고 나타낼 수 있음
  • 주어진 숫자부터 9단까지 출력하는 함수의 경우 1~9 중 하나의 값만 필요하므로, 최악의 경우를 상정하여 1이 입력이라면 10만 개 × 9(1단부터 9단) × 9가 되어 81n이 되므로 역시 O(n)이라 할 수 있음
• 기본적으로 구구단의 경우 항상 동일한 연산량을 가지므로 입력 개수에 영향을 받고, 따라서 O(n) 알고리즘의 오차 범위 이내로 귀결된다는 점을 알 수 있음
  • 반복문이나 좀 복잡한 연산을 했더라도 섣부르게 O(n²)이라 단정 지을 필요 없음 → 빅오 표기법은 코드가 얼마나 복잡하게 돌아가는지에 대해 빠르게 감을 잡기 위한 정돌 사용되는 것이지, 정확한 측정 시간을 위해 사용하는 표기법이 아님

내장 함수 시간 복잡도

리스트(list; [ ])

※ b-a라서 O(n) ‘미만’임. 최악의 경우를 상정하여 O(n)으로 표기함

집합(set; { })

딕셔너리(dictionary; { })

시간 복잡도 줄이기

• 지금까지 배운 시간 복잡도 줄이는 방법
  1. 입력 개수를 보고 그에 맞는 적절한 알고리즘을 선택하기
  2. 자료형이나 자료 구조를 적극적으로 사용하기
  3. 반복문을 줄이기

readline(): 입력 속도를 빠르게

• 프로그래머스의 경우 입력값을 모두 주고, 원하는 기능만 구현하면 되는 함수 형태로 시작 코드가 주어지지만, 실제 테스트를 볼 때는 입력 값을 받는 코드도 직접 구현해야 하는 경우가 있음
• sys 모듈의 readline()을 활용
  • input() 함수는 데이터가 많을수록 효율이 떨어짐

  import sys
  data = sys.stdin.readline()
  

리스트 곱셈: 초기화와 할당을 빠르게

• 기본적으로 배열(리스트)을 다룰 때 동적으로 다루지만, 가끔 미리 할당해 놓은 고정 배열에다가 계산해야 하는 경우가 있음
  • 이럴 때 리스트에 곱셈 연산을 하여 초기화와 할당을 동시에 진행하도록 만들 수 있음

  data1 = [0 for _ in range(1000)]
  data2 = [0] * 1000
  

  • data1의 경우 for 문을 1,000번 반복하면서 리스트에 0을 집어넣기 때문에 O(n)만큼 소모되지만, data2의 경우 [0]을 1,000번 반복하는 것이 전부이므로 O(n) 시간으로 동일한 작업을 수행할 수 있음

문자열 합치기: ‘ ’.join()을 쓰고 +는 사용하지 말

• +로 합칠 경우 각각의 문자열을 새로운 메모리에 복사하여 새 문자열을 만들기 때문에 사실상 시간 복잡도가 O(n²) 정도가 됨

조건문 연산 줄이기: 짧은 것부터 먼저 계산하자

• if 조건문에서 다중 조건을 사용하면 두 조건 중 빨리 실행되는 쪽을 앞쪽으로 배치하는 것이 유리함
  • and 연산을 할 때 앞의 연산 결과가 False라면 뒤의 연산을 실행하지 않고 바로 넘어감
  • or 또한 앞의 연산 결과가 True라면 뒤의 연산을 실행하지 않음

슬라이싱: 불필요한 연산을 최소로

• 리스트, 튜플, 운자열과 같은 자료형에 범위를 지정해 일부분만 추출하는 기능
• ex) a[start : end : step] 형식으로 사용함
  • start: 시작 위치(자신 포함), 숫자 생략하면 가장 첫 번째부터로 인식
  • end: 끝낼 위치(자신 포함x), 숫자 생략하면 가장 마지막까지로 인식
  • step: 간격(기본은 1), 음수를 넣게 되면 맨 끝에서부터 인덱스를 탐색함
    • a[-1 : -3] : 맨끝에서부터 맨 끝에서 두 번째 요소까지 가져옴

# 문자열 슬라이싱
print('Python is awesome'[3::2])

# 2차원, 3차원 배열 슬라이싱
data = [[(0, 1), (2, 3), (4, 5)], [(6, 7), (8, 9), (0, 1)]]
print(data[1:][0][::2])

• 이 외에도 for 문에 사용 가능

표준 라이브러리 활용하기: 속도와 안정성 모두 잡기

• heapq
  • 이진 트리 기반의 최소 힙 자료 구조
  • 항상 정렬된 상태로 값의 추가/삭제가 이루어짐
  • 우선순위 큐나 최단 거리 알고리즘을 구현할 때 많이 사용됨
• collections
  • 연속되는 자료를 가지고 있는 자료형에서 동일한 원소가 몇 개 잇는지 확인 가능한 counter가 있기 때문에 해시 문제를 풀 때 유용함
  • 추가로 덱(dequeue) 자료 구조를 구현하는데 사용하는 deque도 있음
• itertools
  • 경우의 수 문제에 사용하며 순열, 조합, 중복순열, 중복조합 등에 사용함
• math
  • 복잡한 수학 연산을 대신하는 라이브러리
  • 최대공약수, 최소공배수, 팩토리얼, 제곱근, 로그 등을 계산하며, 파이, 자연상수와 같은 상수도 존재함
• bisect
  • 이진 탐색 기능을 제공함
  • 정렬된 데이터가 필요하며, 특정 범위 안에 원소가 있는지 검사하거나 몇 개가 존재하는지 확인하는데 유용함

리스트 컴프리헨션 vs 제너레이터: 편의선와 효율의 대결

• 리스트에 1부터 10까지 데이터 넣기
  • for 문
  • data = [] for i in range(1, 11): data.append(i)
  • 컴프리헨션(comprehension) 사용 → 코드 한 줄로 줄이기
  • [i for i in range(1, 11)]

 

💡 리스트 컴프리헨션 사용하기

• 선언 → 할당 → 재구성 과정을 한 줄에 모두 끝낼 수 있음
• 시간은 O(n)
• 여러 줄로 바꿔 써도 차이가 나지 않아서 간편하게 데이터를 준비할 수 있음

[(변수 표현식) for (사용할 변수) in (순회 가능한 연속적인 데이터)]

# 조건문 추가 - 짝수만 뽑기
[i for i in range(11) if i % 2 == 0]

# if문 중첩 (and로 취급) - 짝수와 5의 배수 동시 만족하는 숫자 구하기
[i for i in range(11) if i % 2 == 0 if i % 5 == 0]

 

• 그러나 컴프리헨션은 데이터가 10만 개, 100만 개 있을 때 이 데이터를 모두 생성하기 때문에 크게 신경 쓸 필요가 없다고 했던 공간 복잡도를 고려하게 하는 원인이 되기도 함
  • 편리한 기능은 대부분 공간 복잡도가 커지는 경우가 많음
  ⇒ 이에 대한 대응책으로 제너레이터(generator)를 사용함

 

💡 제너레이터

• 연속 가능한 자료형을 반환하는 함수
• 실행 중 yield를 만나면 값을 반환하고 더 이상 진행할 수 없는 상태가 아니라면 next()가 호출되기 전까지 대기함
  • 즉, 한 번에 모두 실행하고 그에 대한 결괏값을 반환하는 것이 아니라, 함수가 실행되었다가 다음 next()를 대기하면서 실행이 멈춤
• 장점: 함수가 실행할 것이 매우 많아도 메모리는 항상 고정된 값을 지님
• 만드는 방법
  1. 함수 정의할 때 return 대신 yield 사용
  2. 컴프리헨션 문구를 소괄호로 감싸줌

# 1부터 10까지 한 번에 진행하지 않고, 직접 next()를 호출해야 1, 2, 3의 값이 반환됨
# 이때 이전 값을 갖지 않고, 필요하다면 따로 list() 같은 함수를 통해 실행되는 값을 저장해야 함
(i for i in range(11))

 

데이터 돌려쓰기: 중복 피하기

• 불필요한 연산 낭비를 막기 위해 항상 의미 없는 데이터의 복사나 연산이 발행했는지 확인해야 함

# 수정 전
def solution(data):
	answer = data
	
	for i in range(len(answer)):
		temp = answer[i] * answer[i]
		answer[i] = temp
		
	return answer
	
# 수정 후
def solution(data):
	return [i * i for i in data]

여러 상황에서의 시간 복잡도 생각해보기

어쨌든 반복문이 가장 큰 핵심

• 가장 오래 걸리는 반복문을 찾는 것이 핵심이고, 이 반복문의 시간 복잡도를 구하는 것이 제일 먼저 해야 할 일임
  • 다르게 말하면 함수별로 걸리는 시간 복잡도를 예측해 가장 오래 걸리는 함수가 있다면 다른 작업을 줄일지, 아니면 해당 함수를 최적화할지 전략을 짜는 것임
  • 예)
    • A함수: 배열 정렬 - O(nlogn)
    • B함수: 배열 순회 - O(n)
    • C함수: 두 배열 함께 사용 - O(n²)
    • 만약 이 문제가 통과하지 못했다면, 오래 걸리는 작업이 C함수라는 사실을 알고 있으니 자료 구조를 바꿔 개선할지, 다른 함수의 논리를 변경해 작업량을 줄이는 방식으로 개선할지 선택하면 됨

차수의 계수 생략하지 않기

• 시간 복잡도 측정할 때 ‘O(n)네’, ‘O(nlogn)이네’,… 처럼 단정 짓지 말고 빅오 표기법에 의해 생략되는 차항의 계수도 꼼꼼하게 따져보자
• 여러 시간 복잡도가 엮이면 프로그램의 실제 실행 시간을 예측하지 못하는 일이 자주 발생하기 때문에 뭉뚱그려서 표현하기보단 차수의 계수까지 모두 계산하여 고려하자
• 예) 3n³ + 5n²의 시간 복잡도는 O(n³)임
  • 1초 제한 시간을 기준으로 한다면 O(n³)의 최대 입력 개수는 500개 정도가 됨 (500³ = 125,000,000 = 1억 2천 5백만 ) (1초에 1억번 연산 가능)
  • 문제에서 입력 개수가 500개 주어졌고, 코드를 빅오 표기법으로 계산해보니 O(n³)가 나와 제출했지만, 실패함..
  • 이유: 실제 3n³은 200개도 감당하기 어려움..

크기 N과 크기 M의 시간 복잡도 계산

• 크기가 N과 M인 두 데이터로 연산할 때 O(n²)? O(n³)?
  • ('시간 복잡도 계산하기 - 어림짐작해보기' 부분 참고)

  for i in N:
  	for j in M:
  		...
  

  • 경우의 수를 따져보자 - N의 값은 고정이고, M의 값이 변한다고 가정하자
    1. M이 매우 적은 숫자일 경우(~20)
       • M의 연산은 사실상 상수 시간 이내로 끝나기 때문에 조금 연산이 큰 O(n)으로 봐도 무방함
    2. M이 어느 정도 큰 숫자일 경우(~100)
       • N × M이 N²을 넘어서지 않는다면 N × M으로 계산해야함
    3. M이 N과 거의 비슷하거나 매우 큰 숫자일 경우
       • 입력 개수의 크기에 비례하는 것과 다름없으므로 이 시점부터는 O(n²)으로 취급해야 함
         • • 1. • • • 1. • • • 1. • • • 1. • • • 1. • • • 1. •