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

 

📌 퀴즈 개요

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

---

 

 

🧩 1. 개념 이해 문제

 

❓ 문제 1

다음 중 공간복잡도가 가장 낮은 연산은?

1. 크기가 n인 리스트를 선언하고 초기화하기
2. 크기가 n인 리스트를 정렬하기
3. 크기가 n인 리스트를 한 번 순회하기
4. 크기가 n인 리스트를 사용하지 않고 단일 변수로 계산하기

 

❓ 문제 2

Big-O 표기법에서 가장 비효율적인 시간복잡도는?

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

---

 

 

🧩 2. 실전 문제

 

❓ 문제 3

다음 코드에서 get_sum(n) 함수의 시간복잡도는?

def get_sum(n):
    total = 0
    for i in range(n):
        total += i
    return total

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

 

❓ 문제 4

다음 코드에서 리스트의 특정 요소를 삭제하는 연산 del arr[k]의 시간복잡도는?

arr = [1, 2, 3, 4, 5]
del arr[2]

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

 

❓ 문제 5

공간복잡도를 최적화하는 가장 좋은 방법은?

1. 중복 데이터를 여러 번 저장한다.
2. 리스트 대신 딕셔너리를 사용한다.
3. 제너레이터(generator)를 사용하여 데이터를 한 번에 하나씩 처리한다.
4. 모든 데이터를 한 번에 메모리에 로드한다.

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🏆 정답 및 해설

✅ 문제 1 정답: 4)

• 단일 변수를 사용하는 것이 가장 적은 공간을 차지합니다.

✅ 문제 2 정답: 4)

• O(n!)은 가장 비효율적인 복잡도로, 입력 크기가 커질수록 연산량이 기하급수적으로 증가합니다.

✅ 문제 3 정답: 2)

for i in range(n):  # n번 반복 수행
    total += i  # O(1) 연산

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

✅ 문제 4 정답: 2)

del arr[2]  # 리스트 요소 삭제 시 나머지 요소들이 이동해야 하므로 O(n)

• 리스트 중간에서 삭제하면 뒤의 요소들을 이동해야 하므로 O(n)입니다.

✅ 문제 5 정답: 3)

def generate_numbers():
    for i in range(100):
        yield i  # 데이터를 한 번에 하나씩 처리하여 메모리 사용 절약

• 제너레이터를 사용하면 메모리를 절약하면서 데이터를 처리할 수 있습니다.

---