본문 바로가기
알고리즘

알고리즘(1). 코딩 테스트 준비- 시간복잡도

두설날 2024. 3. 27. 09:11

*이 글을 읽기전에 작성자 개인의견이 있으니, 다른 블로그와 교차로 읽는것을 권장합니다.*

코딩 테스트의 핵심 중 하나는 문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것입니다. 

1. 시간복잡도

1-1. 시간복잡도 정의와 종류

시간복잡도는 문제를 해결하기 위한 연산 횟수로, 보통 초당 2000만 번을 기준 횟수(N)으로 둡니다. 시간복잡도의 유형은 3가지가 있는데 각각 빅-오메가, 빅-세타, 빅-오로 부릅니다. 코딩 테스트에서는 다양한 테스트 케이스를 수행해 모든 케스를 통과해야 하지만, 빅-오 표기를 기준으로 수행시간을 계산합니다.

  • 빅-오메가(best case): 최선일때의 연산 표기, 횟수는 1번
  • 빅-세타(average case): 보통일때의 연산 표기, 횟수는 N/2번
  • 빅-오(worst case): 최악일 떄의 연산 표기, 횟수는 N번 
  • 참고: 빅-오일 경우, N번인 횟수는 보통 for i in range()로 N을 표시하는 경우가 가장 쉽다.
#시간복잡도 예제
import random
findNumber = random.randrange(1,101) #1~100값 int형으로 도출

for i in range(1,101): #1,..101
    if i == findNumber: # i가 1,2,...,101까지 나올때
        print(i)    # randrange(1,101)로 나온 랜덤정수값이 같을경우 print(i)로
        break   # 출력 후 break멈춤

1-2. 시간복잡도 활용

시간복잡도 분석으로 문제에서 알고리즘을 선택할 수 있고, 데이터의 크기(N)을 단서로 사용해야 하는 알고리즘을 추측할 수 있습니다. 수 정렬하기를 예시로 알고리즘 선택 기준을 알오봅니다. 버블 정렬( O(N^2))과 병합 정렬(nlog2n)이라고 할때, 다음 문제를 알아보겠습니다.

#시간제한이 2초일때, N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.
#입력
1번째 줄에 수의 개수 N(1=<N=<1000000), 2번째 줄부터는N개의 줄에 숫자가 주어진다.
이 수는 절댓값이 1000000보다 작거나 같은 정수다. 수는 중복되지 않는다.
#출력
1번째 줄부터 N개의 줄에 오름차순 정렬한 결과를 1줄에 1개씩 출력한다.

#예제입력1
5
5
2
3
4
1

#예제입력2
1
2
3
4
5

 

시간 제한은 2초이므로 연산 횟수는 2000만 * 2 = 4000만 번으로 생각해, 문제를 해결해야 합니다. N최댓값이 1000000일때, 버블정렬과 병합정렬 수식에 대입해 값을 구합니다. 

  • 버블 정렬 N최댓값 대입: 1000000^2=1000000000...
  • 병합 정렬 N최댓값 대입: 1000000log2(1000000)=2000만

위 정렬수식에 N최댓값을 대입했을 때, 버블 정렬 > 연산횟수 가 되고, 병합 정렬 < 연산 횟수 가 되므로, 병합 정렬이 적합한 알고리즘이 됩니다.

시간 복잡도 문제 푸는 순서:

  • N값 범위에서 최댓값 구하기
  • 알고리즘이 적합한지 정렬공식에 N최댓값 대입
  • 대입값 비교해서 정렬값과 연산시간 비교해서, 연산시간이 더 클 경우 알고리즘 적합

1-3. 시간 복잡도 도출 기준

시간 복잡도는 작성한 코드의 비효율적 로직을 개선하는 바탕으로 사용할 수 있습니다. 다음은 시간 복잡도 도출 원리 기준입니다.

  • 상수는 시간 복잡도 계산에서 제외합니다.
  • 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 됩니다.
#예제1: 연산횟수=N
N = 10000
cnt = 1

for i in range(N):
    print('연산 횟수' + str(cnt))
    cnt += 1

#예제2:연산횟수=3N
N = 10000
cnt = 1

for i in range(N):
    print('연산 횟수' + str(cnt))
    cnt += 1
for i in range(N):
    print('연산 횟수' + str(cnt))
    cnt += 1
for i in range(N):
    print('연산 횟수' + str(cnt))
    cnt += 1

위 연산에서 데이터의 크기는 N=10000, 3N=30000 이란 결과가 나오는데, 코딩 테스트에서는 일반적으로 상수를 무시하므로 N=3N으로, 두 코드의 시간복잡도는 O(n)으로 같습니다.

#예제3: 연산 횟수=N^2
N = 10000
cnt = 1
for i in range(N):
    for j in range(N):
        print('연산 횟수'+ str(cnt))
        cnt += 1

위 연산에서 데이터의 크기는 N^2=10000^2 으로 시간복잡도는 10000^2가 나옵니다. 시간복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 이중for문이라면 ^2, 삼중for문이면 ^3이 나옵니다. 실제 코딩 테스트에서 시간 초과가 발생할 때, 중첩된 반복문 원리를 바탕으로 더욱 효율적인 연산 구조로 수정하는 작업으로 문제를 해결할 수 있습니다.

티스토리툴바