[Python] 알고리즘 개념1 퀴즈 - 시간복잡도 & 공간복잡도

 

📌 퀴즈 개요

이 퀴즈는 "시간복잡도 & 공간복잡도" 개념을 이해하고 있는지 확인하기 위한 문제들로 구성되어 있습니다. 각 문제의 답을 선택하거나 직접 작성해보세요!

---

 

 

🧩 1. 시간복잡도 관련 문제

 

❓ 문제 1

다음 코드의 시간복잡도는 얼마일까요?

for i in range(n):
    print(i)

1. O(1)
2. O(n)
3. O(n^2)
4. O(log n)

 

❓ 문제 2

다음 코드의 시간복잡도를 올바르게 분석한 것은?

for i in range(n):
    for j in range(n):
        print(i, j)

1. O(n)
2. O(n^2)
3. O(log n)
4. O(n!)

---

 

 

🧩 2. 공간복잡도 관련 문제

 

❓ 문제 3

다음 코드의 공간복잡도는 얼마일까요?

arr = [0] * n

1. O(1)
2. O(n)
3. O(n^2)
4. O(log n)

 

❓ 문제 4

다음 코드에서 추가적으로 사용되는 공간은?

x = 10
y = 20
z = x + y

1. O(1)
2. O(n)
3. O(n^2)
4. O(log n)

 

❓ 문제 5

2차원 리스트(행렬)를 선언할 때 필요한 공간복잡도는?

1. O(n)
2. O(n log n)
3. O(n^2)
4. O(1)

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🏆 정답 및 해설

✅ 문제 1 (시간복잡도) 정답: 2. O(n)

for i in range(n):
    print(i)  # 이 루프는 n번 실행되므로 O(n)

• 반복문이 한 번 실행되므로 O(n)입니다.

✅ 문제 2 (시간복잡도) 정답: 2. O(n^2)

for i in range(n):
    for j in range(n):
        print(i, j)  # 내부 루프가 n번 실행됨

• 이중 반복문이 있으므로 총 n * n = O(n^2)입니다.

✅ 문제 3 (공간복잡도) 정답: 2. O(n)

arr = [0] * n  # 리스트를 생성하는 데 n개의 원소가 필요함

• 리스트의 크기가 n이므로 O(n)입니다.

✅ 문제 4 (공간복잡도) 정답: 1. O(1)

x = 10
y = 20
z = x + y  # 추가적인 메모리 공간을 거의 사용하지 않음

• 변수 선언과 간단한 연산이므로 O(1)입니다.

✅ 문제 5 (공간복잡도) 정답: 3. O(n^2)

matrix = [[0] * n for _ in range(n)]  # n x n 크기의 리스트 생성

• 2차원 리스트는 n x n 크기의 공간을 필요로 하므로 O(n^2)입니다.

---