06 · 자료구조와 알고리즘

← 챕터 목록

자료구조·알고리즘 면접의 핵심은 복잡도 표를 외우는 게 아니라, 왜 그 복잡도가 나오는지와 iOS 런타임(값 타입·Copy-on-Write·해시 시딩)이 그 이론을 어떻게 비트는지를 함께 말하는 것이다. 아래 7문항을 그 두 축으로 답한다.

Q1. Array, Set, Dictionary의 평균·최악 시간 복잡도는 무엇인가?

CS 원리

배열은 원소가 연속된 메모리에 놓이므로 주소 = base + i × stride 계산 한 번으로 임의 인덱스에 O(1)로 닿는다. 끝에 추가할 때 용량이 남으면 O(1)이고, 꽉 차면 더 큰 버퍼를 새로 잡아 전체를 복사하므로 그 한 번은 O(n)이다. 다만 용량을 대개 2배씩 늘리기 때문에 이 비싼 복사가 드물게 일어나 여러 번의 append에 비용을 나누면 평균 O(1)이 된다(amortized). 중간 삽입·삭제는 뒤 원소를 한 칸씩 밀어야 해 O(n)이다.

해시 테이블은 키를 해시 함수로 정수로 바꿔 버킷 인덱스를 정한다. 충돌이 없다면 위치가 바로 나오므로 O(1), 반대로 모든 키가 같은 버킷으로 몰리면 사실상 선형 탐색이 되어 O(n)이다.

iOS에서는

Swift의 Array·Set·Dictionary는 모두 값 타입이며 Copy-on-Write로 구현된다. 저장소를 고유하게 참조 중이면 변경이 제자리에서 일어나지만, 다른 곳과 공유 중이면 첫 변경에서 저장소 전체를 복제하므로 그 순간 O(n)의 숨은 비용이 든다.

Apple 문서는 append(_:)를 "같은 배열에 여러 번 호출할 때 평균 O(1)"로 명시한다. Set/Dictionary의 조회·삽입·삭제 평균 O(1)은 원소가 Hashable이어야 성립한다. 또한 Swift의 Hasher는 기본적으로 프로세스마다 무작위 시드를 쓰기 때문에(뒤 Q4 참고), 순회 순서가 실행마다 달라질 수 있고 그 순서에 의존하면 안 된다.

실험 · 도구

reserveCapacity(_:)를 준 배열과 안 준 배열에 대량 append를 돌려 재할당 횟수 차이를 본다. 큐처럼 removeFirst()를 반복하는 코드와 removeLast()를 반복하는 코드를 XCTest의 measure {}로 재면, 앞의 것만 입력 크기 제곱으로 느려지는 걸 관찰할 수 있다. Instruments의 Time Profiler로 어느 프레임이 오래 걸리는지, Allocations로 COW 복사가 튀는지 확인한다.

var a = [Int]()
a.reserveCapacity(10_000)          // 재할당 제거 → append가 진짜 amortized O(1)
for i in 0..<10_000 { a.append(i) }

// ❌ 배열을 큐처럼 쓰면 removeFirst가 매번 O(n) → 전체 O(n^2)
while !a.isEmpty { _ = a.removeFirst() }

프로젝트 적용

• 끝에서만 넣고 빼면 Array로 충분하다. 앞에서 빼야 하면 swift-collections의 Deque(양 끝 O(1))나 head 인덱스 방식을 쓴다.
• 같은 컬렉션에 멤버십 검사를 반복하면 Array.contains(O(n)) 대신 Set(O(1))로 바꾼다.
• 대략적인 최종 크기를 알면 대량 삽입 전에 reserveCapacity로 재할당·복사를 없앤다.
• 하지 말 것: Set/Dictionary의 순회 순서에 로직을 의존하는 것, 큰 배열에서 removeFirst()를 반복 호출하는 것.

꼬리 질문

• 배열을 큐로 쓰면 왜 O(n²)이 되고, 어떻게 O(n)으로 되돌리나?
• Hashable을 잘못 구현해 모든 값이 같은 해시를 내면 Set의 복잡도는 어떻게 변하나?
• COW가 있는데 배열을 inout으로 넘기면 복사가 일어나나?

Q2. 시간 복잡도와 공간 복잡도는 무엇이며 실제 입력 크기와 어떻게 연결되는가?

CS 원리

Big-O는 상한, Θ는 위아래로 딱 맞는 한계, Ω는 하한을 뜻한다. 점근 표기는 n을 무한대로 보낼 때의 기준이라 상수 배와 낮은 차수 항을 무시한다. 그래서 3n + 100도, 0.5n도 모두 O(n)이다. 성장률만 놓고 보면 O(1) < O(log n) < O(n) < O(n log n) < O(n²) 순서로 나빠진다. 한 번은 비싸지만 평균으로 싸지는 경우를 분할상환(amortized)으로, 최악의 한 번을 worst-case로 따로 말한다. 공간 복잡도는 보통 입력을 뺀 추가(auxiliary) 메모리를 재며, 재귀 호출이 쌓는 스택 깊이도 여기에 포함된다.

iOS에서는

화면에 보이는 행처럼 n이 작을 때는 점근 등급보다 상수가 지배한다.

• ARC: 참조 타입 원소를 담은 배열을 순회하면 원소마다 retain/release가 붙어, 같은 O(n)이라도 값 타입 배열보다 눈에 띄게 느리다.
• COW: 공유 중인 배열을 무심코 변경하면 O(n) 복사가 숨어든다.
• 캐시 지역성: 연속 메모리인 Array는 포인터를 따라 흩어진 노드를 도는 자료구조보다 상수가 훨씬 작다.
• 스택 공간: 재귀 깊이가 곧 스택 사용량이다. 너무 깊으면 스택 오버플로로 크래시가 나며, iOS 메인 스레드 기본 스택은 1MB, 보조 스레드는 더 작다(Thread.stackSize).

실험 · 도구

입력 크기를 2배씩 늘리며 measure {}로 시간을 재면, 실측 곡선이 이론 등급과 맞는지 볼 수 있다(2배 늘렸을 때 O(n)은 2배, O(n²)은 4배). Instruments의 Time Profiler로 CPU 시간, Allocations로 메모리 증가, os_signpost로 특정 구간의 지속 시간을 계측한다.

프로젝트 적용

• 먼저 n의 실제 범위를 확인한다. 화면 20행과 10만 개 무한 스크롤은 완전히 다른 문제다.
• 작은 n에서는 상수가 좋은 O(n)(연속 메모리 선형 처리)이 O(n log n)보다 빠를 수 있다. 벤치로 확인하고 고른다.
• 재귀는 깊이 한계를 의식하고, 깊어질 수 있으면 반복문 + 명시적 스택으로 바꾼다.
• 하지 말 것: 상수만 다른 두 O(n) 코드를 "둘 다 O(n)이니 똑같다"고 판단하는 것.

꼬리 질문

• 평균 O(1) 해시 조회와 O(log n) 이진탐색 중 실제로 뭐가 더 빠를 수 있고, 왜 그런가?
• 재귀 깊이는 공간 복잡도에 어떻게 잡히며 iOS에서 어떤 크래시로 나타나나?
• amortized O(1)과 average O(1)은 어떻게 다른가?

Q3. Stack과 Queue는 어떤 문제에 적합한가?

CS 원리

Stack은 한쪽 끝(top)에서만 push/pop/peek 하며 셋 다 O(1)이다. Queue는 뒤에서 enqueue, 앞에서 dequeue 하며 역시 O(1)이다. 선택 기준은 단순하다. "가장 최근 것을 먼저 처리"하고 싶으면 LIFO, "먼저 온 것을 먼저 처리"하고 싶으면 FIFO다.

iOS에서는

• UINavigationController의 viewControllers는 화면 스택이다. push/pop이 곧 스택 연산이다.
• UndoManager는 undo/redo 두 개의 스택으로 되돌리기를 구현한다.
• 함수 호출 자체가 콜 스택이다. 재귀 DFS가 여기에 얹힌다.
• DispatchQueue는 제출을 FIFO로 받는다. 다만 직렬(serial) 큐만 실행 순서가 FIFO이고, 동시(concurrent) 큐는 시작만 순서대로일 뿐 끝나는 순서는 보장되지 않는다.
• Swift 표준 라이브러리에는 Queue 타입이 없다. Array를 스택으로 쓰는 건 자연스럽지만(append/removeLast가 O(1)), 큐로 쓰면 removeFirst가 O(n)이라 swift-collections의 Deque를 쓰는 게 낫다.

프로젝트 적용

• LIFO/FIFO 요구를 코드에서 명시적 타입(Deque 등)으로 드러내 의도를 못 박는다.
• 트리·그래프·뷰 계층 탐색에서 깊이 우선이면 스택(또는 재귀), 너비 우선이면 큐를 쓴다.
• 하지 말 것: 큰 배열에서 removeFirst()를 반복해 큐를 흉내 내는 것.

꼬리 질문

• 큐를 두 개의 스택으로 amortized O(1)에 구현하려면 어떻게 하나?
• DFS를 재귀 대신 명시적 스택으로 바꾸면 무엇이 좋아지나?
• "먼저 온 순서"가 아니라 "중요도 순서"가 필요하면 Queue 대신 무엇을 쓰나?

Q4. Hash table은 어떻게 동작하며 collision은 어떻게 처리하는가?

CS 원리

이상적인 해시 함수는 키를 버킷에 고르게 흩뿌리고, 입력이 조금만 달라도 결과가 확 바뀐다(애벌런치). 그래도 버킷 수는 유한하므로 충돌은 반드시 생긴다. 처리 방식은 두 갈래다.

• 체이닝(separate chaining): 버킷마다 리스트를 두고 충돌한 항목을 이어 붙인다. 부하율이 1을 넘어도 버티지만, 포인터로 흩어져 캐시에 불리하고 메모리를 더 쓴다.
• 개방 주소법(open addressing): 충돌하면 정해진 규칙(선형·이차 탐사, 이중 해싱)으로 다음 빈 슬롯을 찾아 저장한다. 연속 메모리라 캐시에 유리하지만, 부하율을 1 미만으로 유지해야 하고 클러스터링이 생기며 삭제 시 tombstone(삭제 표식)이 필요하다.

부하율(원소 수 ÷ 버킷 수)이 임계를 넘으면 버킷을 키우고 전부 다시 배치한다. 이 재해시는 O(n)이지만 드물게 일어나 amortized로 흡수된다.

iOS에서는

Swift의 Set·Dictionary는 Hasher(SipHash 계열)로 해시를 만든다. 이 해시는 기본적으로 프로세스가 실행될 때마다 무작위 시드를 쓴다(SE-0206). 그래서 (1) 악의적으로 충돌을 몰아 넣어 O(n)으로 떨어뜨리는 hash-flooding 공격을 막고, (2) 그 대가로 순회 순서가 실행마다 달라진다. 표준 라이브러리의 네이티브 해시 저장소는 구현 세부로는 개방 주소법을 쓰지만, 이는 공개 API 보장이 아니라 내부 구현이다.

Hashable 규약이 핵심이다. 같으면 해시도 같아야 한다(a == b ⇒ a.hashValue == b.hashValue). 이 규약이 깨지면 조회가 실패한다. 반대로 해시가 같아도 값이 다를 수 있고(정상적인 충돌), 최종 판정은 항상 ==가 한다. 키를 넣은 뒤 해시에 영향을 주는 속성을 바꾸면 그 키를 다시 찾지 못하게 된다.

struct BadKey: Hashable {
    let id: Int
    func hash(into hasher: inout Hasher) { }               // 아무것도 안 섞음 → 항상 같은 해시
    static func == (l: BadKey, r: BadKey) -> Bool { l.id == r.id }
}
// 규약(== 이면 hash 같음)은 지켰지만, 모든 키가 한 버킷에 몰려
// Set/Dictionary 조회가 평균 O(1)이 아니라 O(n)으로 떨어진다.

실험 · 도구

위 BadKey처럼 hash(into:)를 비운 타입과, 컴파일러가 자동 합성한 정상 타입을 각각 Set에 대량 삽입·조회해 시간을 비교하면 O(n) 퇴화를 눈으로 확인할 수 있다. 테스트에서 순회 순서를 고정하고 싶으면 환경변수 SWIFT_DETERMINISTIC_HASHING=1로 시드를 끌 수 있다(테스트 전용, 프로덕션 금지).

프로젝트 적용

• 커스텀 타입을 Set 원소나 Dictionary 키로 쓸 때는 Hashable을 ==와 일관되게 두되, 특별한 이유가 없으면 컴파일러 자동 합성을 쓴다.
• 해시에 넣은 속성은 삽입 후 변경하지 않는다. 가변 상태는 해시에서 빼거나 별도 저장한다.
• 대량 삽입 전 reserveCapacity(_:)로 재해시 횟수를 줄인다.
• 하지 말 것: hashValue를 직접 비교하거나 디스크에 저장하는 것(시드 때문에 실행 간 불변이 아니다).

꼬리 질문

• 체이닝과 개방 주소법은 삭제 처리가 어떻게 다른가(왜 tombstone이 필요한가)?
• Swift가 해시 시드를 무작위화하는 이유와 그로 인한 부작용은?
• Equatable과 Hashable이 서로 어긋나게 구현되면 구체적으로 어떤 버그가 나나?

Q5. Binary search를 적용할 수 있는 전제 조건은 무엇인가?

CS 원리

이진탐색은 정렬된 구간의 가운데를 보고 목표와 비교해 절반을 통째로 버린다. 매번 후보가 반으로 줄어 비교는 O(log n)이다. 성립 조건은 정렬 순서와 비교 술어가 일치하는 것이다(이름순으로 정렬해 두고 날짜로 이진탐색하면 안 된다). 중복이 있으면 "처음 위치"와 "마지막 위치"를 구분해 찾아야 한다(lower/upper bound). 그리고 가운데 계산은 (lo + hi) / 2 대신 lo + (hi - lo) / 2로 오버플로를 피한다.

iOS에서는

Swift 표준 라이브러리에는 binarySearch가 없다(주목할 만한 공백). 직접 구현하거나 swift-algorithms의 partitioningIndex(where:)를 쓴다. Array는 RandomAccessCollection이라 인덱스 이동이 O(1)이지만, Collection만 만족하는 타입에선 index(_:offsetBy:)가 O(k)라 이진탐색의 이점이 사라진다. 또 Swift는 Int 오버플로 시 조용히 넘어가지 않고 트랩(크래시)한다. 다만 64비트에서 배열 인덱스 합(lo + hi)이 넘칠 일은 사실상 없고, 큰 정수 값 구간을 이진탐색할 때 (lo + hi) / 2가 실제로 위험해진다. 어느 쪽이든 lo + (hi - lo) / 2가 안전한 습관이다.

func binarySearch<T: Comparable>(_ a: [T], _ target: T) -> Int? {
    var lo = 0, hi = a.count - 1
    while lo <= hi {
        let mid = lo + (hi - lo) / 2       // (lo+hi)/2 는 오버플로 위험(Swift는 트랩)
        if a[mid] == target { return mid }
        else if a[mid] < target { lo = mid + 1 }   // 정렬 기준과 같은 비교여야 함
        else { hi = mid - 1 }
    }
    return nil
}

실험 · 도구

정렬 안 된 배열에 이진탐색을 돌리면 크래시가 아니라 조용히 틀린 결과(있는 값을 없다고 하거나 그 반대)를 낸다는 걸 확인한다. 반복 횟수를 로그로 세면 정렬된 n개에서 ⌊log₂ n⌋ + 1번을 넘지 않는다.

프로젝트 적용

• 같은 데이터를 여러 번 조회하면 한 번 정렬해 두고 이진탐색한다. 삽입이 잦으면 정렬 배열 유지 비용(삽입 O(n))과 Set/Dictionary(평균 O(1))를 저울질한다.
• 정렬 기준과 탐색 기준을 반드시 동일하게 맞춘다.
• 하지 말 것: 조회할 때마다 재정렬하는 것(그러면 조회당 O(n log n)이라 이진탐색의 의미가 없다).

꼬리 질문

• 중복 값에서 "target 이상이 처음 나오는 위치"(lower bound)를 찾으려면 조건을 어떻게 바꾸나?
• 회전된 정렬 배열(rotated sorted array)에서는 이진탐색을 어떻게 변형하나?
• 정렬 상태를 유지하면서 삽입도 잦다면 어떤 자료구조가 O(log n) 삽입·검색을 주나?

Q6. 정렬 알고리즘의 안정성은 UI 데이터에서 언제 중요한가?

CS 원리

안정 정렬은 같은 키를 가진 원소들의 입력 순서를 그대로 둔다. 그래서 다단계 정렬을 "덜 중요한 키 먼저, 더 중요한 키 나중"으로 안정 정렬을 연쇄하면 원하는 다중 기준이 완성된다. 병합정렬과 Timsort는 안정적이고, 일반적인 퀵정렬·힙정렬은 불안정하다.

iOS에서는

Apple 문서는 현재 sort(by:)/sorted(by:)에 대해 "정렬 알고리즘은 안정성이 보장된다"고 명시한다. 이 보장은 Swift 5에서 도입됐고, 그 전에는 introsort 기반이라 불안정했다. NSDiffableDataSourceSnapshot으로 목록을 갱신할 때는 항목 순서가 곧 애니메이션을 결정한다. 동점 원소의 순서가 스냅샷마다 흔들리면 실제로는 변한 게 없는데도 move 애니메이션이 남발된다. 즉 정렬 안정성이 애니메이션 안정성으로 직결된다.

// 방법1: 안정 정렬 연쇄 — 덜 중요한 키(이름) 먼저, 중요한 키(날짜) 나중
items.sort { $0.name < $1.name }
items.sort { $0.date < $1.date }   // 같은 날짜끼리 이름순 유지(안정성 보장에 의존)

// 방법2: 튜플 비교 — tie-breaker를 명시(결정적, 안정성에 덜 의존)
items.sort { ($0.date, $0.name) < ($1.date, $1.name) }

프로젝트 적용

• 다단계 정렬은 안정 정렬 연쇄 또는 튜플 비교 중 하나로 한다. 튜플 비교는 tie-breaker가 코드에 드러나 결정적이라 더 견고하다.
• 동점 순서가 UI 정체성(셀 애니메이션, 선택 유지)에 영향을 주면, 안정성에 기대기보다 명시적 tie-breaker(예: 고유 id)를 넣어 순서를 완전히 결정적으로 만든다.
• 하지 말 것: 동점 순서가 중요한데 tie-breaker 없이 "정렬이 알아서 유지해 주겠지" 가정하는 것.

꼬리 질문

• 안정 정렬 없이도 다단계 정렬을 결정적으로 만들려면 어떻게 하나?
• 튜플 비교와 안정 정렬 연쇄는 각각 언제 더 낫나?
• diffable data source에서 같은 identifier가 중복되면 무슨 일이 벌어지나?

Q7. Pagination 데이터를 중복 없이 효율적으로 병합하려면 어떻게 하는가?

CS 원리

병합의 핵심은 "이미 봤는지"를 싸게 판정하는 것이다. 매번 배열 전체를 훑어 contains로 확인하면 O(n) × n = O(n²)이 된다. 해시 집합으로 판정하면 O(1)이라 전체가 O(n)으로 떨어진다. 두 페이지가 같은 키로 정렬돼 있다면, 병합정렬의 merge 단계처럼 앞에서부터 훑으며 O(n+m)에 합치고 동일 키를 걸러낼 수도 있다.

iOS에서는

Set.insert(_:)는 (inserted: Bool, memberAfterInsert)를 돌려주므로, 삽입 성공 여부로 "처음 본 것"을 바로 가릴 수 있다. 순서를 보존해야 하면 swift-collections의 OrderedSet/OrderedDictionary가 삽입 순서 유지 + O(1) 유일성을 함께 준다. Diffable data source는 item identifier가 유일해야 하며, 중복 identifier를 append하면 런타임 경고나 크래시가 난다. 그래서 클라이언트 dedup은 선택이 아니라 필수다. ID는 Identifiable의 서버 id처럼 안정적이고 유일한 값이어야 하며, 배열 인덱스나 객체 주소를 쓰면 안 된다.

var items: [Feed] = []
var seen = Set<Feed.ID>()

func merge(_ page: [Feed]) {
    for item in page where seen.insert(item.id).inserted {
        items.append(item)          // 처음 본 id만 추가 → 페이지 크기에 비례(O(page))
    }
}

실험 · 도구

같은 페이지를 일부러 두 번 주입한 뒤 diffable 스냅샷을 apply 해, dedup이 없을 때 콘솔에 뜨는 중복 identifier 경고와 dedup을 넣은 뒤의 정상 동작을 비교한다. contains로 매번 전체 배열을 훑는 O(n²) 버전과 Set 기반 O(n) 버전을 measure {}로 재면 페이지가 쌓일수록 차이가 벌어진다.

프로젝트 적용

• 가능하면 백엔드에 cursor 페이지네이션을 요청한다. offset은 목록이 중간에 바뀌면 중복·누락을 만든다.
• 클라이언트는 Set<ID> 또는 OrderedSet로 방어적 dedup을 한다. 서버가 완벽해도 재시도·경합으로 중복이 올 수 있다.
• identifier는 안정적이고 유일해야 한다. 인덱스·주소·순번을 쓰지 않는다.
• 하지 말 것: 병합할 때마다 contains로 전체 배열을 훑는 것(O(n²)).

꼬리 질문

• offset과 cursor 페이지네이션은 중복·누락 특성이 어떻게 다른가?
• 두 페이지가 각각 정렬돼 있을 때 O(n+m)에 병합하려면?
• 아이템이 실시간으로 수정·삭제될 때 병합 로직은 무엇을 더 처리해야 하나?

출처 · 참고자료