1 / 14강

자료구조와 연산 비용

메모장에 이름을 적으면 연락처 목록이 됩니다. 이름순으로 정리하면 찾기는 쉬워지지만, 새 이름을 알맞은 자리에 끼워 넣어야 합니다. 데이터를 저장하는 방식은 어떤 작업을 얼마나 빠르게 할 수 있는지에 영향을 줍니다.

먼저 구분할 세 가지

• 자료구조: 데이터를 저장하고 연결하는 방식입니다. 배열, 연결 리스트, 트리 등이 있습니다.
• 알고리즘: 원하는 결과를 얻는 절차입니다. 이름을 첫 줄부터 하나씩 비교하는 것도 알고리즘입니다.
• 추상 자료형(ADT): 사용할 수 있는 연산을 정한 약속입니다. 예를 들어 스택은 ‘넣기’와 ‘마지막에 넣은 것 꺼내기’를 약속합니다. 내부 구현은 배열일 수도, 연결 리스트일 수도 있습니다.

얼마나 오래 걸릴까요?

입력의 크기를 n이라고 할 때, 입력이 늘어남에 따라 연산량이 어떻게 커지는지 봅니다. **빅 오(Big O)**는 그 증가율의 상한을 나타냅니다. 정확한 실행 시간이나 초 단위의 값은 아닙니다.

• O(1): 배열에서 지정한 한 칸을 읽습니다. 항목 수가 늘어도 필요한 단계 수가 거의 일정합니다.
• O(n): 목록을 한 번 훑습니다. 최악에는 모든 항목을 확인합니다.
• O(log n): 정렬된 배열의 탐색 범위를 계속 절반으로 줄입니다.
• O(n²): 모든 항목을 다른 모든 항목과 비교하는 식으로 일이 늘어납니다.

항상 어떤 연산의 어떤 경우인지 함께 보세요. 첫 항목이 정답이면 순차 탐색은 한 번 만에 끝납니다. 마지막 항목이 정답이거나 정답이 없으면 n개를 살펴봅니다.

작은 문제로 나누는 재귀

재귀는 함수가 자기 자신을 호출하는 방법입니다. 아래 함수는 양의 정수를 하나씩 줄여 출력합니다.

def countdown(n):
    if n <= 0:
        return
    print(n)
    countdown(n - 1)

countdown(3)

출력은 3, 2, 1입니다. n <= 0은 멈추는 조건, n - 1은 문제를 줄이는 단계입니다. 둘 중 하나를 놓치면 호출이 끝나지 않을 수 있습니다.

이 예제의 시간은 O(n)이고, 돌아올 위치를 기억하는 호출 공간도 O(n)입니다. Python은 재귀 호출 깊이에 제한이 있으므로 큰 입력에는 반복문이 더 알맞을 수 있습니다.

확인 문제

정렬되지 않은 연락처 1,000개에서 이름을 첫 항목부터 찾습니다. 그 이름이 없다면 몇 항목을 확인할까요? 입력이 2배가 되면 최악의 연산량은 어떻게 바뀔까요?