[딩코딩코 2025 코딩테스트 필수 알고리즘] - 2. 시간복잡도,공간복잡도

본 글에 사용된 코드와 이미지의 일부는
딩코딩코 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 강의를 참조하여 발췌·활용하였습니다.

[본 게시물은 파트너스 활동의 일환으로 소정의 수수료를 받을 수 있습니다.] https://inf.run/tXMrp

---

시간 복잡도

시간복잡도란?

시간 복잡도란 “입력값에 비해 얼마나 일을 수행해야 하는가” 라고 할 수 있다.

예를 들어보자.
내가 반에 있는 사람들 중에서 이성에게 호감이 높은 사람을 뽑는다고 해보자.
반에 있는 사람들은 N 명이 라고 하면
A 방식은 N 번 만큼의 연산이 필요하고, B 방식은 N^2 만큼의 연산이 필요하다.
N 이 30 이라면 A 방식은 30번, B 방식은 900 번의 연산이 필요하다.

이처럼 시간복잡도는 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계 를 말한다.

최댓값 찾기 알고리즘의 시간 복잡도 판단해보기

시간복잡도에 대한 개념을 살펴봤으니 , 최댓값 찾기 알고리즘의 시간 복잡도를 판단해보자.

그럼 함수가 시간이 얼마나 걸리는지 어떻게 분석할 수 있을까?
각 줄이 실행되는 걸 1번의 연산이 된다고 생각하고 계산하면 되고, 입력값의 길이는 보통 N 이라고 표현한다.

여기서 입력값이란 함수에서 변경될 수 있는 값이다.

코드로 살펴보자

    for number in array:                 # array 의 길이만큼 아래 연산이 실행
        is_max_num = True                # 대입 연산 1번 실행
        for compare_number in array:     # array 의 길이만큼 아래 연산이 실행
            if number < compare_number:  # 비교 연산 1번 실행
                is_max_num = False       # 대입 연산 1번 실행
        if is_max_num:                   # 비교 연산 1번 실행
            return number

위에서 연산된 것들을 더해보면

1. array 의 길이(첫번째 for문) * array 의 길이(두번째 for문) * (비교 연산 1번 + 대입 연산 1번) 으로 표현할 수 있으므로 N * N * 2
2. array 의 길이(첫번째 for문) * 비교 연산 1번(마지막 if 문) 으로 표현할 수 있으므로 N * 1

그러면 이 함수는 2*N^2 + N 만큼의 시간이 걸린다고 말할 수 있다.

다음 코드를 살펴보자.

def find_max_num(array):
    max_num = array[0]        
    for num in array:      
        if num > max_num:  
            max_num = num
    return max_num

print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

여기서의 시간 복잡도는 어떻게 될까?

max_num = array[0] 의 대입 연산자 1번

array의 길이(for문) * (비교 연산 1번 + 대입 연산 1번) = N * 2

즉 1 + 2N 번으로 시간 복잡도를 표현할 수 있다.

시간 복잡도 비교

그러면 두 가지 방법을 시간 복잡도로 비교해보자.

N	2*N^2+N	2*N+1
1	3	3
10	210	21
1000	2001000	2001

이 표를 보면 , 두 가지를 알 수 있다.

1. N 과 N^2 은 N 이 커질수록 더 큰 차이가 난다.
2. N 의 지수를 먼저 비교하면 된다.

우리가 매번 코드를 몇 번의 연산이 발생하는지 확인하는 것은 불가능하다.
따라서 상수는 신경쓰지말고, 입력값에 비례해서 어느 정도로 증가하는지만 파악하면 된다.

---

공간 복잡도

공간 복잡도란?

공간 복잡도란 입력값과 문제를 해결하는 데 걸리는 공관과의 상관관계를 말한다. 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것이다.

공간 복잡도를 파악하는 방법은 저장하는 데이터의 양이 1개의 공간 을 사용한다고 계산하면 된다.

최빈값 찾기 알고리즘의 공간 복잡도 판단하기

최반값 찾기 알고리즘의 코드로 공간 복잡도를 살펴보자.

def find_max_occurred_alphabet(string):
    alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s",
                      "t", "u", "v", "x", "y", "z"]
    max_occurrence = 0
    max_alphabet = alphabet_array[0]

    for alphabet in alphabet_array:
        occurrence = 0
        for char in string:
            if char == alphabet:
                occurrence += 1

        if occurrence > max_occurrence:
            max_alphabet = alphabet
            max_occurrence = occurrence

    return max_alphabet

print("정답 = i 현재 풀이 값 =", find_max_occurred_alphabet("hello my name is dingcodingco"))
print("정답 = e 현재 풀이 값 =", find_max_occurred_alphabet("we love algorithm"))
print("정답 = b 현재 풀이 값 =", find_max_occurred_alphabet("best of best youtube"))

위에서 사용된 공간들을 더해보면

1. alphabet_array 의 길이 = 26
2. max_occurrence, max_alphabet,occurrence 변수 = 3

즉, 29의 공간이 필요하다.

다음 코드를 살펴보자

def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')
        alphabet_occurrence_array[arr_index] += 1

    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index

    return chr(max_alphabet_index + ord('a'))

result = find_max_occurred_alphabet
print("정답 = i 현재 풀이 값 =", result("hello my name is dingcodingco"))
print("정답 = e 현재 풀이 값 =", result("we love algorithm"))
print("정답 = b 현재 풀이 값 =", result("best of best youtube"))

이 코드의 공간 복잡도는 아래와 같다.

1. alphabet_occurrence_array = 26
2. arr_index , max_occurrence,max_alphabet_index,alphabet_occurrence = 4

즉, 30만큼의 공간이 필요하다.

공간 복잡도 비교

두 코드의 공간 복잡도는 각각 29,30 이다.
그럼 어느것이 효율적일까? 더 적게 쓴 29가 더 효율적일까?

그렇지 않다. 29와 30 모두 상수라서 큰 상관이 없다.
공간 복잡도가 동일한 계수일 경우, 시간 복잡도로 비교하면 된다.

이처럼, 대부분의 문제에서는 알고리즘의 성능이 공간에 의해 결정되지 않는다. 따라서 공간 복잡도 보다는 시간 복잡도를 더 신경 써야 한다.

최빈값 찾기 알고리즘의 시간 복잡도 판단하기

그렇다면, 시간 복잡도는 어떨지 비교해보자.

첫번째 방법의 시간 복잡도는 아래와 같다.

1. alphabet_array 의 길이(첫번째 for문) * 대입 연산 1번 = 26 * 1 = 26
2. alphabet_array 의 길이 * string의 길이(두번째 for문) * (비교 연산 + 대입연산) = 26 * N * 2 = 52N
3. alphabet_array 의 길이 * (비교 연산 + 대입연산 + 대입연산) = 26 * 3 = 78

즉 , 52N + 104 의 시간이 걸리고, 상수의 연산은 계산하지 않아도 되기 때문에 N 만큼의 시간 복잡도를 갖는다.

두번째 방법의 시간 복잡도를 살펴보자.

1. string의 길이 * (비교 연산 + 대입연산2번) = N*3
2. 대입 연산 2번 = 2
3. alphabet_array의 길이 * (비교 1번, 대입 3번) = 26*4 = 104

즉, 3N + 106 의 시간이 걸리고, N 만큼의 시간 복잡도를 갖는다.

시간 복잡도 비교

표를 통해 비교해보자.

N의 길이	52N + 104	3N + 106	N^2
1	156	109	1
10	624	136	100
1000	52104	3106	1000000
10000	520104	30106	100000000

이 표를 보면, 다음을 알 수 있다.

1. 두 시간 복잡도는 N^2 에 비해 아무것도 아니다.
2. 공간 복잡도 보다는 시간 복잡도를 더 신경써야 한다.

즉, 첫번째 보다는 두번째 방식이 효율적이지만, N^2 과 같이 차수가 달라지는 알고리즘에 비해서는 둘 다 효율적인 방식이라고 할 수 있다.