동적 배열: 스택의 한계를 넘어서

자료구조, 알고리즘 중요하다고들 하지만

아직까지 앱을 구현할 때 해당 개념들이 엄청나게 도움이 된 적이 없다 보니 필요성을 못 느꼈는데요. 

 ( 기업들에서 코딩 테스트를 요구하니 공부를 하긴 해야 하는데...... )

실질적인 필요를 못 느끼니 어지간히 하기 싫더군요. 

으앙 하기 싫어~~~~

그래도 하긴 해야 하니까. ( 굶어 죽지 않으려면 )  

이왕이면 좀 더 쓸모있고 재미있게 정리를 해보려고 합니다. 

가봅시다. 레츠기릿

그래 한다 해~~

---

동적 배열이 뭐고, 어떻게 쓰고를 알기 전에 

이놈이 '왜' 필요하게 되었는지를 먼저 알아야하지 않을까요?

등장 배경 : 스택의 한계

우리가 작성한 프로그램이 실행되기 위해서는 운영체제로부터 메모리를 할당받은 뒤 

목적에 따라 메모리 영역을 구분하여 앱을 실행하는 데 필요한 데이터들을 다루는데 사용합니다. 

프로세스는 뭘까?

그 중 프로그래밍을 할때 가장 많이 다루는 영역이 두군데가 있는데 

입니당.

 

"프로그램은 기본적으로 함수 호출의 연속으로 이루어집니다."

그리고 프로그램의 이러한 실행 구조는 "호출 스택(call stack)"이라는 메모리 구조로 통해 관리되는데 

이때 나온 호출 스택을 줄인 말이 '스택'이죠. 

프로그램이 시작되면 진입점(entry point)이라고 하는 특정 함수나 지점에서 실행이 시작됩니다.

다양한 프로그래밍 언어에서 이 진입점은 다음과 같이 정의됩니다

 

C/C++: main() 함수가 프로그램의 진입점입니다. 운영체제는 프로그램을 로드하고 이 함수를 호출하면서 실행을 시작합니다.

int main(int argc, char *argv[]) {
    // 프로그램 시작
    return 0;
}

Java: 마찬가지로 main() 메서드가 진입점입니다. 자바 가상 머신(JVM)이 이 정적 메서드를 찾아 실행을 시작합니다.

public class MyProgram {
    public static void main(String[] args) {
        // 프로그램 시작
    }
}

Swift: iOS 앱에서는 AppDelegate나 SceneDelegate에서 애플리케이션 시작점이 정의되며, 커맨드라인 애플리케이션에서는 @main 속성이 있는 타입이나 전역 범위의 코드가 진입점이 됩니다.

@main
struct MyProgram {
    static func main() {
        // 프로그램 시작
    }
}

이 진입점에서 시작하여 프로그램은 함수 호출의 연속으로 실행됩니다. 각 함수는 다른 함수를 호출할 수 있으며, 이러한 호출은 스택 프레임을 생성합니다. 함수 호출이 완료되면 제어는 호출한 함수로 돌아갑니다. 이런 방식으로 프로그램은 함수 호출의 트리 또는 그래프를 형성하고 진행합니다.

프로그램 실행의 이러한 구조는 "호출 스택(call stack)"이라는 메모리 구조를 통해 관리됩니다. 함수가 호출될 때마다 새로운 스택 프레임이 생성되고, 함수가 반환될 때 해당 프레임이 제거됩니다. 이 스택 기반의 실행 모델은 대부분의 명령형 프로그래밍 언어의 기본입니다.

프로그래밍 패러다임에 따라 함수 호출 방식이 달라질 수 있지만(비동기 프로그래밍, 이벤트 기반 프로그래밍 등), 그 기본 구조는 여전히 함수 호출의 연속이라는 개념에 기반합니다.

스택 메모리는 함수 호출 시 지역변수, 매개 변수, 반환 주소등을 저장하는 영역으로써 

콜 스택 동작을 통해 알아보는 함수 호출

"스택에 할당되는 메모리는 컴파일 타임에 그 크기가 결정되어야합니다."

위와 같은 특징은 다음과 같은 제약을 가져오는데요.

• 크기가 고정되어야한다 : 프로그램 실행 중에 스택에 할당된 메모리 크기를 동적으로 변경할 수 없어 배열과 같은 자료 구조 크기가 미리 결정되어야하며, 실행시간에 크기를 조정할 수가 없습니다. 
• 스택 오버 플로우 위험 : 컴파일 타임에 할당된 스택 공간보다 더 많은 메모리가 필요한 경우 스택 오버 플로우가 발생합니다. 
• 메모리 낭비 : 최악의 경우를 대비해 크게 메모리를 할당해야하므로 메모리 낭비가 심합니다. 
• 가변 크기 자료 구조 제한 : 런타임에 크기가 결정되는 가변 길이 배열이나 동적 자료구조를 스택에 직접 구현하기 어렵습니다. 

이러한 스택의 한계 때문에, 크기가 런타임에 결정 되거나 실행 중에 변경되어야하는 자료 구조를 위해 

힙 메모리를 활용하는 동적 배열이 필요하게 되었어요. 

힙 메모리와 동적 배열 

힙 메모리는 런타임에 크기를 결정할 수 있고, 필요에 따라 메모리를 할당하고 해제할 수 있는 영역이지요. 

동적 배열은 이러한 힙 메모리 특성을 활용하여 다음과 같은 이점을 제공할 수 있게 되었어요. 

• 런타임에 크기 결정 : 사용자 입력이나 파일 크기등 실행시점에 알 수 있는 정보에 따라 메모리 할당 가능합니다.
• 크기 조정 가능 : 요소가 추가되거나 제거됨에 따라 메모리 크기를 동적으로 조정 가능합니다. 

근데 뭐든지 좋기만 한것은 없죠?

동적 배열의 유연성은 성능 측면에서는 비용을 수반해요. 

• 메모리 단편화(Memory Fragmentation): 힙 메모리에서는 할당과 해제가 반복됨에 따라 메모리 공간이 작은 조각으로 나뉘는 단편화가 발생할 수 있습니다.
• 시스템 호출 오버헤드: 동적 메모리 할당(malloc/free 또는 Swift의 경우 내부적으로 사용되는 메모리 관리 함수)은 운영체제의 시스템 호출을 필요로 하며, 이는 스택 메모리 접근보다 상당히 느립니다.
• 캐시 효율성 저하: 메모리가 연속적이지 않을 경우 CPU 캐시 효율성이 떨어질 수 있습니다.

 

이러한 단점에도 불구하고, 동적 배열은 현대 프로그래밍에서 필수적인 자료구조가 되었어요. 

메모리 효율성과 프로그래밍 편의성이 주는 이점이 충분히 성능 저하를 상쇄할 수 있기 때문이지요. 

 

동적 배열의 등장 배경과 함께 장단점을 알아 봤으니 

이제 본격적으로 동적배열을 파해쳐 봅시다.

동적 배열 작동 원리 

동적 배열은 내부적으로는 정적 배열을 사용하며 다음과 같은 핵심 개념으로 구성됩니다.

• 용량(Capacity): 현재 할당된 메모리에 저장할 수 있는 최대 요소 수
• 크기(Size): 현재 배열에 저장된 실제 요소의 수

동적 배열의 작동 원리는 아래와 같습니다. 

 

1. 초기 용량으로 힙에 메모리 할당 (시스템 호출 발생)
2. 요소 추가 시, 크기가 용량보다 작으면 그냥 추가
3. 크기가 용량에 도달하면, 더 큰 용량(보통 2배)의 새 배열을 힙에 할당 (추가 시스템 호출 발생)
4. 기존 배열의 모든 요소를 새 배열로 복사
5. 기존 배열 메모리 해제 (시스템 호출 발생)
6. 새 배열을 현재 배열로 대체하고 요소 추가

초기 상태 (용량: 4, 크기: 3)
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │   │
└───┴───┴───┴───┘

pushback(4) 후 (용량: 4, 크기: 4)
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
└───┴───┴───┴───┘

pushback(5) 시도 - 용량 부족으로 resize() 호출
(1) 새 배열 할당 (시스템 호출) - 새 용량: 8
┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

(2) 기존 배열의 요소 복사
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

(3) 새 요소 추가
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

(4) 기존 배열 메모리 해제 (시스템 호출)

 

위에서 볼 수 있듯이 동작 과정에서 시스템 호출과 메모리 복사 작업이 발생하기 때문에 스택 메모리에 비해 성능 저하의 원인이 되요. 

 

Swift로 직접 동적 배열을 구현하면 

class DynamicArray {
    // 내부 저장 배열 (힙에 할당됨)
    private var array: [Int]
    // 현재 배열의 용량
    private var capacity: Int
    // 현재 배열에 저장된 요소 수
    private var size: Int
    
    // 지정된 용량으로 초기화
    init(capacity: Int) {
        self.capacity = max(capacity, 1) // 최소 용량은 1
        // 힙에 메모리 할당 (시스템 호출 발생)
        self.array = [Int](repeating: 0, count: self.capacity)
        self.size = 0
    }
    
    // 인덱스의 요소 반환
    func get(_ i: Int) -> Int {
        // 인덱스가 유효하다고 가정
        return array[i]
    }
    
    // 인덱스의 요소 설정
    func set(_ i: Int, _ n: Int) {
        // 인덱스가 유효하다고 가정
        array[i] = n
    }
    
    // 배열 끝에 요소 추가
    func pushback(_ n: Int) {
        // 배열이 가득 찼으면 크기 조정
        if size == capacity {
            resize()  // 시스템 호출 발생
        }
        array[size] = n
        size += 1
    }
    
    // 배열 끝 요소 제거 및 반환
    func popback() -> Int {
        // 배열이 비어있지 않다고 가정
        size -= 1
        return array[size]
    }
    
    // 배열 용량 2배로 증가
    func resize() {
        capacity *= 2
        // 새 메모리 할당 (시스템 호출 발생)
        var newArray = [Int](repeating: 0, count: capacity)
        
        // 기존 요소들을 새 배열로 복사 (메모리 복사 오버헤드)
        for i in 0..<size {
            newArray[i] = array[i]
        }
        
        // 기존 배열 메모리 해제 (시스템 호출 발생)
        // Swift에서는 ARC가 자동으로 처리
        array = newArray
    }
    
    // 현재 요소 수 반환
    func getSize() -> Int {
        return size
    }
    
    // 현재 용량 반환
    func getCapacity() -> Int {
        return capacity
    }
    
    // 배열 내용 문자열로 표현 (디버깅용)
    func description() -> String {
        var result = "["
        for i in 0..<size {
            result += "\(array[i])"
            if i < size - 1 {
                result += ", "
            }
        }
        result += "] (Size: \(size), Capacity: \(capacity))"
        return result
    }
}

 

동적 배열의 성능을 분석해 보면 

동적 배열 시간 복잡도 분석

1. get(i): O(1) - 인덱스를 통한 직접 접근
2. set(i, n): O(1) - 인덱스를 통한 직접 접근
3. pushback(n):
   • 일반적인 경우: O(1) - 배열 끝에 요소 추가
   • 용량 조정 필요 시: O(n) - n개 요소 복사 필요
4. popback(): O(1) - 배열 끝 요소 제거
5. resize(): O(n) - n개 요소를 새 배열로 복사
6. getSize(): O(1) - 단순 변수 반환
7. getCapacity(): O(1) - 단순 변수 반환

분할 상환 분석(Amortized Analysis)

pushback() 연산은 대부분의 경우 O(1)이지만, 용량 조정이 필요할 때는 O(n)입니다.

그러나 resize() 연산은 자주 발생하지 않습니다. 정확히는 요소 추가 시 n번의 연산 중 로그(n)번만 발생합니다.

이를 분할 상환 분석하면, n개 요소를 추가하는 데 필요한 총 연산은

• 일반적인 pushback: n번
• resize로 인한 복사: 1 + 2 + 4 + ... + n/2 ≈ n

따라서 총 2n번의 연산이 필요하므로, 분할 상환 시간 복잡도는 O(1)이 됩니다.

그러나 시스템 호출의 오버헤드를 고려하면, 스택 기반 배열보다는 느립니다.

 

동적 배열 공간 복잡도 분석

동적 배열의 공간 복잡도는 O(capacity)입니다. 용량이 증가함에 따라 메모리 사용량도 증가합니다.

실제로는 배열이 가득 찼을 때 용량을 2배로 늘리므로, 최악의 경우 사용률은 50%입니다(요소를 하나 추가한 직후 resize가 발생한 경우). 하지만 평균적으로는 75%의 공간 효율성을 보입니다.

 

Swift의 Array

동적 배열이 왜 등장했고, 어떻게 동작하는지를 자세히 알아봤는데요. 

실제 앱을 만들때 저 동적 배열을 직접 구현해서 사용하지는 않습니당.

 

이미 Swift의 표준 라이브러리에 있는 Array는 이미 최적화 된 동적 배열을 제공하고 있기 때문이죠. 

 

최적화 방법

• Copy-on-Write: 배열이 복사될 때 실제 데이터는 변경이 필요할 때까지 복사되지 않음
• Small Buffer Optimization: 작은 배열은 힙 할당 없이 스택에 직접 저장될 수 있음
• 용량 관리 최적화: 성장 인자와 축소 전략의 세밀한 조정

 

Array | Apple Developer Documentation

Swift야 고맙다.

 

이미 누군가 잘 만들어 뒀다고 하지만

이렇게 등장 배경부터 동작 원리까지 알아보니까 뭔가 개운하지요?? 그쵸? 

이제 문제 풀러가야겠지?? (시러~)

해야지 뭐..