Python_#3

hyena_lee·2025년 10월 4일

자료구조

목록 보기

6/15

🧩 공간복잡도란?

입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말함!
입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것.
우리는 공간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘!!?
프로그램이 실행될 때 “얼마나 많은 메모리를 쓰는가” 를 나타내는 개념!!
즉, 프로그램이 실행될 때
변수, 배열, 리스트, 함수 호출, 임시 저장값 등
모든 데이터를 저장하기 위해 필요한 공간(메모리) 의 양을 말해요

🧮 시간복잡도 vs 공간복잡도

구분	뜻	예시 질문
⏱️ 시간복잡도	얼마나 오래 걸리나	“이 코드가 얼마나 빨리 끝날까?”
💾 공간복잡도	얼마나 많은 메모리를 쓰나	“이 코드가 얼마나 많은 메모리를 차지할까?”

📘 공간복잡도 계산에 포함되는 것

고정 공간 (Fixed part)
→ 입력 크기와 관계없이 항상 필요한 공간
(예: 변수, 상수, 고정 배열 등)
가변 공간 (Variable part)
→ 입력 크기에 따라 달라지는 공간
(예: 리스트, 재귀 함수 스택 등)

즉, 총 공간복잡도 = 고정 공간 + 가변 공간

🧠 예시로 이해해보기

🔹 예제 1) O(1) — 상수 공간

def sum_numbers(a, b):
    result = a + b
    return result

➡️ 이 코드는 변수 a, b, result 세 개만 사용.
데이터 크기(N)가 커져도 추가로 메모리를 안 씀.
👉 공간복잡도 = O(1) (상수 공간)

🔹 예제 2) O(N) — 선형 공간

def make_list(n):
    arr = []
    for i in range(n):
        arr.append(i)
    return arr

➡️ arr 리스트 안에 n개의 값이 저장.
입력 크기 n이 커질수록 메모리도 비례해서 커짐.
👉 공간복잡도 = O(N)

🔹 예제 3) 재귀 함수의 공간복잡도


def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

➡️ 이 함수는 자기 자신을 계속 호출?
각 호출이 스택(stack) 에 쌓이기 때문에
n=5라면 호출이 5번 쌓임.
👉 공간복잡도 = O(N) (재귀 깊이만큼 공간 필요)

🔹 예제 4) 최빈값 찾기 공간복잡도



```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 choarmy"))
print("정답 = e 현재 풀이 값 =", find_max_occurred_alphabet("we love algorithm"))
print("정답 = b 현재 풀이 값 =", find_max_occurred_alphabet("best of best youtube"))

이 해결 방법은 각 알파벳마다 문자열을 돌면서 몇 글자 나왔는지 확인함.
만약 그 숫자가 저장한 알파벳 빈도 수보다 크다면, 그 값을 저장하고 제일 큰 알파벳으로 저장함. 이 함수가 공간을 얼마나 사용하는지 어떻게 분석해본다면?
바로 저장하는 데이터의 양이 1개의 공간을 사용한다고 계산하면 됨.
아래와 같이 계산할 수 있다.

    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"]
# -> 26 개의 공간을 사용합니다
    max_occurrence = 0 # 1개의 공간을 사용    
    max_alphabet = alphabet_array[0]   # 1개의 공간을 사용.

    for alphabet in alphabet_array:
        occurrence = 0  # 1개의 공간을 사용

위에서 사용된 공간들을 더해보면,
1. alphabet_array 의 길이 = 26
2. max_occurrence, max_alphabet, occurrence 변수 = 3
```
$$
29
$$

만큼의 공간이 필요.
그러면 우리는 이제 이 함수는 $29$ 만큼의 **공간이 사용되었구나**! 라고 말할 수 있다.

            max_occurrence = number     # 대입 연산 1번 실행
```
위에서 연산된 것들을 더해보면,
alphabet_array 의 길이 X 대입 연산 1번 26
alphabet_array 의 길이 X string의 길이 X (비교 연산 1번 + 대입 연산 1번) 26 N 2
alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 2번) 26 * 3
만큼의 시간이 필요합니다. 여기서 string 의 길이는 보통 N이라고 표현함.
그러면 위의 시간을 다음과 같이 표현할 수 있다.
그러면 우리는 이제 이 함수는
52
N

104
52N+104 만큼의 시간이 걸렸겠구나! 라고 말할 수 있다.

#### 두번째 방법

```python

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"))

이 해결 방법은 각 알파벳의 빈도수를 저장한 다음에, 빈도 수 중 가장 많은 알파벳의 인덱스 값을 반환합니다. 다시 한 번 공간복잡도를 분석해본다면?

		alphabet_occurrence_list = [0] * 26 # -> 26 개의 공간을 사용

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')  # 1개의 공간을 사용
        alphabet_occurrence_list[arr_index] += 1

    max_occurrence = 0                   # 1개의 공간을 사용
    max_alphabet_index = 0               # 1개의 공간을 사용
    for index in range(26):
        alphabet_occurrence = alphabet_occurrence_list[index] # 1개의 공간을 사용
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index

위에서 사용된 공간들을 더해보면,
1. alphabet_array 의 길이 = 26
2. arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
$30$

만큼의 공간이 필요합니다.

그러면 우리는 이제 이 함수는 $30$ 만큼의 공간이 사용되었구나! 라고 말할수있다.
- 위에서 연산된 것들을 더해보면,
1. string의 길이 X (비교 연산 1번 + 대입 연산 2번)
2. 대입 연산 2번
3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번)
만큼의 시간이 필요함. 여기서 string 의 길이는 보통 N이라고 표현함.
그러면 위의 시간을 다음과 같이 표현할 수 있다.

N * (1 + 2) + 2 + 26 * (1 + 3) = 3N + 106

그러면 우리는 이제 이 함수는 $3N+106$ 만큼의 시간이 걸렸겠구나! 라고 말할 수있다.

🧩 비교

$52N + 104$ 든 $3N+106$ 이든 $N^2$ 에 비해서 아무것도 아니구나.
공간 복잡도보다는 시간 복잡도를 더 신경 써야 한다!

🧩 대표적인 공간복잡도 비교

복잡도	의미	예시
O(1)	일정한 메모리만 사용	단일 변수 계산
O(N)	입력 크기만큼 메모리 필요	리스트 저장
O(N²)	2차원 배열(리스트 안에 리스트)	행렬 계산
O(log N)	재귀 호출에서 절반씩 줄어드는 경우	이진 탐색 (재귀 버전)

💬 시간복잡도와의 관계

✅ 현실에서는 시간복잡도와 공간복잡도는 트레이드오프(trade-off) 관계.
| 상황 | 설명 |
| ------------------- | ----------------------- |
| 시간 줄이려면 → 공간 더 써야 함 | 미리 계산한 값을 저장 (메모이제이션 등) |
| 공간 줄이려면 → 시간 더 걸림 | 매번 다시 계산해야 함 |
👉 그래서 “빠르면서 메모리도 적게 쓰는 코드”가 좋은 알고리즘.

🌱 주의 포인트

리스트, 딕셔너리, 문자열 등은 메모리를 많이 쓴다.

재귀 함수는 호출될 때마다 스택에 쌓이므로 조심!

파이썬은 변수 하나만 만들어도 메모리 사용량이 은근히 큼
(그래서 대량 데이터는 numpy 같은 라이브러리로 다룸)

구분	시간복잡도	공간복잡도
뜻	실행 속도	메모리 사용량
단위	O(1), O(N), O(N²)...	O(1), O(N), O(N²)...
목표	빠르게	적게
예시	for문 몇 번 도는가	리스트, 재귀 깊이 등