Chapter 19. 공간 제약 다루기

Chapter 19. 공간 제약 다루기

하단의 목차를 클릭하여 이동할 수 있습니다 :)

1. 공간 복잡도의 빅 오
2. 시간과 공간 트레이드오프
3. 재귀에 숨겨진 비용
4. 연습 문제 정리

• 공간 복잡도(space complexity)란 알고리즘이 얼마나 많은 메모리를 소모하는지를 의미한다.

---

1. 공간 복잡도의 빅 오

• 공간 복잡도 또한 빅 오로 표기한다.
• 공간 복잡도의 핵심 질문은 "데이터 원소가 N개일 때 알고리즘은 메모리 단위를 얼마나 소모할까?" 이다.
  • 공간 복잡도는 추가로 소모되는 메모리만을 고려한다.
    • 추가로 소모되는 공간은 보조 공간(auxiliary space)이라 한다.
  • 다른 책에서는 원래 입력까지 포함하는 경우도 있다.

---

2. 시간과 공간 트레이드오프

• 공간 복잡도와 시간 복잡도 중 어느 것을 우선시할 것인지는 주어진 문제마다 다르다.
  • 빠른 수행 속도를 요구하지만 하드웨어의 메모리가 넉넉한 경우 시간 복잡도를 우선한다.
  • 하드웨어의 메모리가 적지만 수행 시간이 상관없다면 공간 복잡도를 우선한다.

---

3. 재귀에 숨겨진 비용

• 재귀 함수는 재귀 호출 횟수만큼 단위 공간을 차지한다.
  • 재귀는 호출할 때마다 호출 스택에 항목을 추가하기 때문이다.
• 재귀로 함수를 구현할 경우 대용량 데이터를 처리할 수 있는지 고려해야 한다.
  • 대안적으로 loop문을 사용할 수도 있다.

---

4. 연습 문제 정리

1 번 문제 코드 변환 (python)

def word_builder(array):
    collection = []
    
    for i in range(len(array)):
        for j in range(len(array)):
            if i != j:
                collection.append(array[i] + array[j])
    
    return collection

 

2 번 문제 코드 변환 (python)

def reverse(array):
    new_array = []
    
    for i in range(len(array) - 1, -1, -1):
        new_array.append(array[i])
    
    return new_array

 

3 번 답 (python)

def reverse(array):
    for i in range(len(array) // 2):
        # 배열 내 값을 교환하는 방법
        array[i], array[len(array) - 1 - i] = array[len(array) - 1 - i], array[i]
        
        # 다음과 같이 기존 방식으로 교환할 수도 있다.
        # temp = array[len(array) - 1 - i]
        # array[len(array) - 1 - i] = array[i]
        # array[i] = temp