선형·계층·그래프·해시 구조의 선택

이어 읽을 선수 설명: 배열·연결·스택·큐·트리·그래프·해시, 시간·공간 복잡도와 Big-O. 각 설명의 전제를 확인한 뒤 아래의 단계 풀이와 자체 문제를 연결한다.

자료가 같아도 빠르게 해야 할 일이 다르다

회원 100만 명을 가입 순서대로 훑는 일, 회원번호 하나로 찾는 일, 점수가 높은 회원부터 꺼내는 일은 같은 데이터를 다루지만 필요한 연산이 다르다. 가입 순서가 중요하면 순차구조가 자연스럽고, 정확한 키 조회가 중심이면 해시 구조가 유리하다. 우선순위가 계속 바뀌면 정렬된 배열을 매번 다시 만드는 것보다 우선순위 큐를 검토해야 한다.

따라서 자료구조론은 배열·연결리스트·트리의 이름을 외우는 과목이 아니다. 표현할 관계와 자주 수행할 연산을 먼저 정하고, 시간·공간·변경·실패 비용을 감당할 수 있는 구조를 선택하는 이론이다. 선택한 구조는 이어지는 알고리즘의 가능성과 비용까지 바꾼다.

한 문장으로 말하면

자료구조(data structure)는 데이터와 그 관계를 저장하고 다루는 방식이며, 좋은 자료구조 선택은 필요한 연산을 허용된 시간·메모리·복잡성 안에서 수행하게 만든다.

자료구조의 이름만으로 성능이 자동 결정되지는 않는다. 배열도 정렬 여부와 크기 변경 방식에 따라 비용이 달라지고, 해시 테이블도 해시 함수·충돌 처리·적재율에 따라 지연이 달라진다. 그러므로 답안에는 구조의 정의 → 지원 연산 → 비용이 생기는 원리 → 적합한 조건 → 실패조건을 연결한다.

정확히 말하면: 추상 자료형과 구현을 구분한다

추상 자료형(Abstract Data Type, ADT)은 값의 집합과 허용 연산, 각 연산이 만족해야 할 규칙을 특정 저장방식과 분리해 정의한 것이다. 예를 들어 스택 ADT는 push, pop, top, isEmpty와 마지막 입력이 먼저 나온다는 규칙을 정의한다. 스택을 배열로 만들지 연결구조로 만들지는 별도의 구현 선택이다.

자료구조는 ADT의 규칙이나 문제의 데이터 관계를 실제 메모리 배치와 연결로 구현한 표현이다. 하나의 ADT를 여러 구조로 구현할 수 있고, 하나의 구조를 여러 ADT의 기반으로 쓸 수도 있다. 이 구분이 없으면 큐이므로 연결리스트여야 한다처럼 인터페이스와 구현을 혼동한다.

자료구조 선택은 다음 다섯 요소를 함께 정하는 결정이다.

1. 관계: 순서, 계층, 임의 연결, 키–값 대응 중 무엇을 보존하는가.
2. 연산: 접근·검색·삽입·삭제·최솟값·순회를 얼마나 자주 하는가.
3. 비용: 평균과 최악 시간, 추가 공간, 데이터 이동량은 얼마인가.
4. 제약: 순서·중복·동시성·지연상한·저장장치 특성을 어떻게 지켜야 하는가.
5. 변화: 크기와 연산 비율이 바뀔 때 재배치·재해시·균형복구를 감당할 수 있는가.

전체에서 어디인가: 문제에서 구조와 알고리즘까지

문제의 목적·입출력·제약을 먼저 고정한 뒤, 보존할 순서·계층·연결·키–값 관계와 접근·검색·삽입·삭제·순회·최소·최대 연산을 정한다. 배열·연결, 스택·큐, 트리·힙, 그래프, 해시 후보마다 시간·공간 비용과 순서·중복·동시성·복구 제약을 함께 비교한다. 대표·경계·최악 입력으로 후보를 검증한 다음 그 구조 위에서 동작할 알고리즘을 선택한다. 단계별 산출물은 아래 선택 절차, 후보의 동일축 비교는 연산별 비용표를 사용한다.

화살표의 방향이 중요하다. 유행하는 구조를 먼저 정한 뒤 문제를 끼워 맞추지 않는다. 문제의 경계와 연산을 정하고 후보를 비교한 뒤, 실제 입력 분포와 최악 조건으로 선택을 검증한다.

먼저 알아둘 것

앞에서 문제 명세는 입력·출력·제약·성공조건을 고정하고, 알고리즘은 그 명세를 만족하는 유한한 절차이며, 자료구조는 그 절차가 데이터를 읽고 바꾸는 표현이라고 배웠다. 시간·공간 복잡도와 배열·연결, 스택·큐, 트리·그래프, 해시의 기본 의미도 이미 살펴봤다. 여기서는 연산계약과 메모리 배치, 평균·최악 비용, 가까운 데이터를 묶어 읽는 지역성까지 연결해 선택근거를 구체화한다.

먼저 연산계약과 비용모형을 만든다

연산 이름은 모호하지 않게 고정한다. 접근(access)은 알려진 위치의 원소를 얻는 것, 검색(search)은 조건에 맞는 위치를 찾는 것, 삽입(insert)과 삭제(delete)는 관계를 보존하며 원소를 더하고 빼는 것, 순회(traverse)는 필요한 원소를 정한 순서로 방문하는 것이다. 최소·최대, 선행·후행, 이웃, 경로처럼 문제 고유 연산도 추가한다.

비용표에는 최소한 다음을 함께 적는다.

• n: 현재 원소 수, 그래프라면 정점 수 V와 간선 수 E처럼 입력 크기를 분리한다.
• 최선·평균·최악 중 어떤 경우인지 표시한다.
• 한 번의 비용뿐 아니라 여러 연산을 묶은 상환 비용(amortized cost)이란 무엇인지 구분한다. 이는 가끔 발생하는 큰 비용을 연속된 여러 연산에 나누어 연산당 비용으로 계산한 값이며, 개별 연산의 최악 비용과는 다르다.
• 입력 외에 추가로 쓰는 공간, 참조·인덱스·빈 버킷 비용을 포함한다.
• 구조를 유지하는 재배치, 균형복구, 재해시와 보조 인덱스 갱신을 포함한다.

Big-O는 증가율을 비교하는 언어이지 실제 지연의 보증서가 아니다. 같은 O(n) 순회라도 연속 메모리를 읽는 배열과 흩어진 노드를 따라가는 연결구조는 캐시 적중과 할당비용이 다를 수 있다. 반대로 작은 n에서는 단순한 선형 탐색이 복잡한 인덱스보다 충분히 빠르고 검증하기 쉽다.

배열과 연결구조: 위치 접근과 연결 변경의 교환

배열(array)은 정수 인덱스로 원소 위치를 계산할 수 있는 순차구조다. 원소 크기와 시작 위치를 알면 i번째 원소에 직접 접근할 수 있어 보통 O(1)이다. 원소가 연속적으로 놓이면 순회 지역성도 좋다. 그러나 중간에 원소를 넣거나 빼면서 순서를 유지하려면 뒤 원소를 이동하므로 O(n)이 될 수 있다.

동적 배열(dynamic array)은 여유 용량을 두고 원소를 추가하다가 공간이 차면 더 큰 배열을 만들고 복사한다. 확장 한 번은 O(n)이지만 충분한 비율로 용량을 늘리면 많은 끝 삽입의 상환 비용은 원소당 O(1)로 설명할 수 있다. 이 말은 개별 삽입의 최악 지연이 항상 일정하다는 뜻이 아니다.

연결리스트(linked list)는 각 노드가 다음 노드, 필요하면 이전 노드의 참조를 가진다. 삽입 위치와 필요한 참조를 이미 알고 있으면 연결 변경은 O(1)이다. 삭제도 이중연결리스트에서 해당 노드를 알거나, 단일연결리스트에서 삭제할 노드의 선행노드까지 확보했을 때 O(1)이다. 단일연결리스트의 삭제 대상만 알아서는 일반적으로 선행노드 탐색을 생략할 수 없으며, i번째 노드나 특정 값을 찾으려면 앞에서부터 따라가므로 O(n)이 걸릴 수 있다. 노드마다 참조와 할당 정보가 필요하고 메모리가 흩어져 순회 지역성이 나빠질 수 있다.

따라서 중간 삽입이 많다는 말만으로 연결리스트를 고르지 않는다. 삽입 위치를 찾는 비용, 실제로 이동해야 할 원소 크기, 순회 비율과 메모리 배치를 함께 비교한다.

스택·큐·덱·우선순위 큐: 접근 순서를 계약으로 만든다

스택(stack)은 마지막에 넣은 원소를 먼저 꺼내는 후입선출(Last-In, First-Out, LIFO) ADT다. 함수 호출 복귀, 괄호 짝 검사, 실행 취소처럼 최근 문맥을 먼저 복원하는 문제에 맞는다. 배열 또는 연결구조로 구현할 수 있으며 빈 스택의 pop을 어떻게 처리할지 계약에 포함한다.

큐(queue)는 먼저 넣은 원소를 먼저 꺼내는 선입선출(First-In, First-Out, FIFO) ADT다. 도착 순서를 보존하는 작업 대기열과 너비우선 탐색에 맞는다. 배열로 구현할 때 앞 원소를 매번 이동하지 않고 머리·꼬리 인덱스를 순환시키는 원형 큐를 사용할 수 있다.

덱(double-ended queue, deque)은 양 끝에서 삽입·삭제할 수 있다. 스택과 큐를 모두 표현하거나 최근 작업창을 관리하는 데 쓸 수 있다. 우선순위 큐(priority queue)는 도착 순서가 아니라 우선순위가 가장 높은 원소를 꺼내며, 흔히 힙으로 구현한다.

이 구조들은 값을 저장하는 모양보다 허용하는 접근 순서가 핵심이다. FIFO가 필요한데 우선순위 큐를 쓰면 먼저 온 요청이 계속 밀릴 수 있고, 우선순위가 필요한데 단순 큐를 쓰면 긴급 작업을 제때 처리하지 못한다.

트리와 힙: 계층·정렬·최솟값 요구를 분리한다

트리는 뿌리에서 하위 노드로 이어지는 계층을 표현한다. 파일 경로와 조직도처럼 부모–자식 관계 자체가 의미일 수도 있고, 검색 비용을 줄이기 위한 인덱스 구조일 수도 있다.

이진 탐색 트리(Binary Search Tree, BST)는 한 노드의 왼쪽에는 더 작은 키, 오른쪽에는 더 큰 키가 오도록 순서를 유지한다. 트리 높이가 h이면 검색·삽입·삭제 비용은 보통 O(h)다. 균형이 유지되면 h가 log n 수준이지만 정렬된 입력이 한쪽으로만 이어지면 h=n이 되어 선형으로 악화될 수 있다. 균형 트리는 회전이나 분할로 높이를 제한하는 대신 갱신 로직이 복잡해진다.

힙(heap)은 부모가 자식보다 우선한다는 힙 속성을 가진 완전트리 기반 구조다. 최솟값 또는 최댓값 확인은 빠르고 삽입·삭제 뒤 위아래로 속성을 복구한다. 그러나 전체가 정렬된 것은 아니므로 임의 키 검색을 O(log n)이라고 말하면 안 된다.

디스크나 페이지 단위 저장에서는 한 노드에 여러 키와 자식을 두어 트리 높이와 입출력 횟수를 줄이는 다진 탐색트리를 검토한다. 핵심은 비교 횟수만이 아니라 한 번에 읽는 블록과 데이터 이동량까지 비용모형에 넣는 것이다.

그래프: 같은 연결도 표현에 따라 빠른 질문이 달라진다

그래프 G=(V,E)는 정점 집합 V와 정점 사이 간선 집합 E로 관계를 표현한다. 방향, 가중치, 중복간선과 자기루프 허용 여부를 먼저 정해야 한다. 서비스 호출, 도로, 권한 상속처럼 문제에 따라 간선 의미가 다르다.

인접 행렬(adjacency matrix)은 정점 쌍마다 간선 여부나 가중치를 2차원 배열에 둔다. 두 정점이 직접 연결됐는지 O(1)에 확인하기 쉽지만 정점 수에 비례한 제곱 공간이 필요하다. 간선이 조밀하거나 정점 쌍 질의가 매우 많을 때 유리할 수 있다.

인접 리스트(adjacency list)는 각 정점마다 연결된 이웃 목록을 둔다. 공간은 대체로 O(V+E)이고 한 정점의 이웃을 순회하기 좋다. 반면 특정 두 정점의 직접 연결 여부는 해당 정점의 이웃 수에 영향을 받는다. 키 조회용 보조 해시를 결합하면 조회를 줄이는 대신 갱신·공간·일관성 비용이 생긴다.

희소 그래프와 조밀 그래프의 경계는 고정 숫자가 아니다. 실제 V, E, 질의 비율, 메모리 표현, 갱신 빈도로 두 후보를 측정한다.

해시 테이블: 빠른 키 조회는 충돌과 적재율을 관리한 결과다

해시 테이블은 키를 해시 함수로 배열 위치 후보인 버킷에 대응시킨다. 서로 다른 키가 같은 버킷에 대응하는 충돌(collision)은 정상적으로 발생할 수 있으므로 반드시 해결 규칙이 필요하다.

분리 연결(separate chaining)은 버킷마다 충돌한 항목의 목록이나 다른 검색구조를 둔다. 개방 주소법(open addressing)은 테이블 안에서 다른 빈 위치를 탐사한다. 개방 주소법은 메모리 지역성이 좋을 수 있지만 적재율이 높아지면 탐사 길이가 늘고 삭제 표식도 주의해야 한다.

적재율 α = 저장 원소 수 / 버킷 수는 충돌 가능성과 공간 낭비의 균형을 보여 준다. 임계값을 넘으면 더 큰 테이블을 만들고 원소를 다시 배치하는 재해시가 필요할 수 있다. 좋은 분포와 관리된 적재율 아래 검색·삽입의 기대 비용은 O(1)로 설명할 수 있지만, 충돌이 한곳에 몰리는 최악 경우는 O(n)까지 악화될 수 있다.

해시는 정확한 키 동등성 조회에 강하지만 키 순서·범위검색·가장 작은 키를 자동 제공하지 않는다. 순서가 필요하면 정렬구조를 쓰거나 별도 인덱스를 결합하고 두 구조의 갱신 원자성을 관리한다.

여기까지의 결론

구조 이름보다 먼저 관계와 연산을 고정한다. 배열·연결구조는 위치 접근과 변경, 큐·스택·힙은 꺼내는 순서, 트리·그래프는 관계와 순회, 해시는 키 조회를 각각 빠르게 만드는 대신 다른 비용을 지불한다. 이제 이 작동원리를 같은 비교축에 놓고 실제 요구에 맞는 구조를 고른다.

주요 구조를 같은 축으로 비교한다

다음 비용은 전형적 구현의 판단 출발점이다. 실제 답안에서는 평균/최악, 균형 여부, 위치를 이미 아는지, 그래프 표현처럼 필요한 전제를 함께 적는다.

표에서 가장 작은 Big-O 하나만 고르지 않는다. 순서·중복·경계값·동시성 요구를 만족하지 못하는 구조는 빠르더라도 후보에서 제외한다.

선택은 일곱 단계로 기록한다

복합 구조를 쓰면 각각의 장점뿐 아니라 동시에 갱신해야 할 사본이 늘어난다. 예를 들어 작업을 도착순서 큐와 작업번호 해시에 함께 두면 빠른 취소가 가능하지만, 추가·완료·취소 때 둘 중 하나만 바뀌지 않도록 연산 경계와 복구를 설계해야 한다.

없앨 수 없는 교환관계

자료구조는 한 번 정하면 영구적인 설계가 아니다. 데이터 규모와 질의 비율이 바뀌어 선택 전제가 깨지면 측정값을 근거로 재구성한다.

어디서 실패하는가

답안에서 적절한 자료구조를 사용한다고 끝내지 않는다. 실패 원인을 구조의 작동원리와 연결하고, 어떤 측정·불변조건·복구로 막는지 쓴다.

자료구조론의 핵심 학습 논점

자료구조론을 공부할 때는 구조 이름과 평균 복잡도에 그치지 않고, 어떤 관계와 연산을 보존해야 하는지까지 설명해야 한다. 다음 다섯 가지를 스스로 점검하자.

1. 추상 자료형의 연산계약과 실제 자료구조의 구현표현을 구분한다.
2. 선형·계층·그래프·해시 구조가 관계를 표현하고 연산을 수행하는 원리를 설명한다.
3. 평균·최악·상환 시간과 공간·지역성·변경비용을 같은 조건에서 비교한다.
4. 입력 규모와 연산 비율, 순서·범위·중복·동시성 요구로 구조를 선택한다.
5. 충돌·편향·재구성·경계값과 복합 구조 불일치를 검증·복구 논점으로 연결한다.

다음 절에서는 여기서 선택한 자료구조 위에서 탐색·정렬·그래프 알고리즘이 어떻게 실행되는지 살펴본다. 같은 문제라도 자료표현을 바꾸면 연산 비용과 검증할 불변조건이 달라진다.

실무에서는 이렇게 보인다: 작업 처리기

한 서비스가 다음 요구를 가진다고 하자.

• 일반 작업은 도착순서대로 처리한다.
• 긴급 작업은 일반 작업보다 먼저 처리하되 같은 등급에서는 도착순서를 지킨다.
• 작업번호로 대기 작업을 빠르게 조회하고, 취소 요청을 일관되게 처리한다.
• 아직 끝나지 않은 선행 작업이 있는 작업은 실행하지 않는다.

단순 FIFO 큐 하나는 우선순위와 의존성을 표현하지 못한다. 모든 작업을 정렬 배열에 두면 최고 우선순위는 쉽게 찾지만 작업이 들어올 때마다 이동비용이 생긴다. 다음과 같이 역할을 나누어 조합할 수 있다.

상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.

번호 조회, 실행 순위, 선행 완료 판정은 각각 해시·힙·방향 그래프의 책임이다. 기준 저장소의 등록·취소·완료 상태가 세 표현에 일관되게 반영되어야 한다. 미완료 선행 수가 0인 작업만 실행 가능 힙에 넣고, 힙 원소를 교환할 때 번호 해시의 위치를 함께 갱신한다. 화살표는 책임과 갱신 관계이며 저장소가 자동 원자성을 제공한다는 보장은 아니다.

우선순위 큐의 비교키를 (긴급등급, 도착순번)으로 두면 등급 안의 FIFO를 보존할 수 있다. 해시는 관리된 충돌과 적재율에서 작업번호 조회를 기대 O(1)에 지원한다. 그러나 조회와 힙에서의 제거는 같은 연산이 아니다. 해시에 힙 위치를 함께 저장하면 마지막 원소와 교환한 뒤 위나 아래로 재정렬하여 취소할 수 있으므로 제거는 O(log n)이고, 힙에서 원소를 교환할 때마다 위치값도 갱신해야 한다. 다른 방법인 지연 삭제(lazy deletion)는 해시 상태만 기대 O(1)에 취소로 표시한 뒤 그 작업이 힙의 맨 위에 왔을 때 건너뛴다. 이 방법은 취소 요청은 빠르지만 취소된 항목이 한동안 공간을 차지하므로 주기적 정리가 필요하다.

방향 그래프에서 진출차수(outdegree)는 한 정점에서 나가는 간선 수다. 선행 작업 완료 때는 그 작업에서 나가는 후속 간선만 순회해 미완료 수를 줄이므로 미완료 수 갱신 자체는 후속 간선 수 d=outdegree에 대해 O(d)다. 그 결과 새로 실행 가능해진 작업이 k개라면 힙 삽입까지 포함한 완료·후속 해제는 O(d+k log n)이다. 여기서 n은 처리 중 힙 크기의 상한이며, 기준 저장소 기록비용은 이 메모리 연산 비용과 별도로 산정한다. 새 u → v 선행관계를 등록할 때는 기존 그래프에서 v가 u에 도달하는지 DFS나 BFS로 확인하여 순환을 막고, 최악에는 O(V+E)가 든다. 한 작업의 완료·취소가 세 구조에 걸치므로 최종 작업 상태를 기록하는 기준 저장소를 하나 정하고, 같은 요청을 식별하는 중복판별키(idempotency key)로 재시도가 상태를 두 번 바꾸지 않게 한다. 메모리의 큐·해시가 기준 저장소와 달라지면 다시 구성한다. 낮은 우선순위가 영원히 밀리는 기아(starvation)를 막기 위해서는 대기시간이 길수록 우선도를 올리는 에이징(aging) 규칙과 그에 따른 힙 키 갱신비용도 설계한다.

선행 작업을 취소할 때 후속 작업을 어떻게 처리할지도 계약이어야 한다. 이 사례에서는 선행 작업의 취소를 완료로 간주하지 않고 해당 후속 작업을 blocked 상태로 남긴다. 운영자가 대체 선행작업을 연결하거나 후속 작업도 명시적으로 연쇄취소해야만 상태가 바뀌며, 이미 후속 작업이 실행 중이면 선행 취소를 거절한다. 다른 정책도 가능하지만 차단·연쇄취소·완료 간주를 섞어 쓰면 같은 입력에서 결과가 달라진다.

작은 입력으로 세 구조가 함께 바뀌는 과정을 따라가 보자. 다음은 메모리 안의 동작을 설명하는 자체 교육 예제이며, 작업은 하나씩 실행하고 긴급 등급이 일반 등급보다 앞선다고 가정한다. A는 일반·도착순번 1·선행 없음, B는 긴급·순번 2·선행 A, C는 긴급·순번 3·선행 없음이다. 아래 힙 칸은 배열의 물리 배치가 아니라 유효 작업을 꺼낼 순서를 표시한다.

따라서 실행 순서는 C→A→B다. B를 긴급이라는 이유만으로 처음부터 힙에 넣으면 아직 필요한 결과를 받지 못한 작업이 실행된다. 반대로 완료된 A를 해시에서 계속 대기로 보이게 두면 복구 때 A가 다시 실행될 수 있다. 조회·우선순위·선행관계는 별개의 질문이지만 같은 작업 상태를 기준으로 함께 갱신해야 한다.

이제 일부를 스스로 바꿔 보자. C를 실행 전에 취소하면 첫 실행 작업과 그다음 작업은 무엇인가? 이 사례의 즉시 삭제 방식에서는 C를 해시로 찾아 힙에서 제거하므로 첫 작업은 A, A 완료 후에는 B다. B→A라고 답했다면 우선순위 판단 전에 선행 수를 확인하는 단계를 놓친 것이므로 위 표의 B 등록 행으로 돌아간다. A를 완료 대신 취소하면 B의 선행 수를 0으로 줄여도 되는가? 여기서 정한 정책은 취소를 완료로 간주하지 않으므로 B를 차단 상태로 유지한다. 단순히 숫자를 줄이는 것이 아니라 어떤 상태전이가 선행조건을 충족하는지 먼저 확인해야 한다.

이 사례의 결론은 자료구조를 많이 쓰자가 아니다. 하나의 구조가 서로 다른 계약을 억지로 맡을 때보다 역할을 분리할 수 있지만, 조합 수만큼 일관성 비용도 증가한다는 것이다.

시험에서는 어떻게 묻는가: 10점

다음은 자료구조 선택과 검증을 연습하기 위한 자체 제작 문제다. 실제 기출이나 공식 배점 기준을 뜻하지 않는다.

추상 자료형과 자료구조의 관계를 설명하고, 배열·연결리스트·균형 탐색트리·해시 테이블의 특징과 선택기준을 비교하시오.

관계는 연산계약과 구현표현을 구분하라는 요구다. 특징은 구조 설명뿐 아니라 비용이 생기는 원리를 포함한다. 선택기준은 Big-O 목록이 아니라 관계·연산 비율·평균/최악 지연·공간·순서 요구를 같은 축으로 비교해야 한다.

답안 목차·풀이·교정 근거 보기

10점 답안 목차

1. 정의와 경계
   • ADT: 값·연산·규칙, 자료구조: 실제 배치·연결 구현
2. 구조별 작동원리와 비용
   • 배열: 인덱스·연속배치 / 연결: 참조 변경
   • 균형트리: 높이 제한 / 해시: 키–버킷·충돌 처리
3. 비교·선택기준
   • 관계, 주요 연산, 평균·최악, 순서·범위, 공간·지역성
4. 실패통제와 결론
   • 편향·충돌·재해시·경계값·복합 갱신 일관성

답안 도식

관계·연산·규모·제약에서 ADT 연산계약과 불변조건을 먼저 정한다. 구현 후보인 배열·연결, 트리·힙, 그래프 표현, 해시를 동일축 비용표에 정렬하고 평균·최악 시간, 공간·지역성, 변경·복구를 함께 판단한다. 대표·경계·최악 입력의 검증 절차를 통해 선택을 확인하고 전제가 바뀌면 재평가한다. 아래 완성 답안은 이 관계를 구조별 작동원리와 실패조건으로 풀어 쓴다.

10점 모범답안

추상 자료형은 값의 집합, 허용 연산과 그 규칙을 구현과 분리해 정의한 계약이고, 자료구조는 그 계약과 데이터 관계를 메모리 배치·참조·인덱스로 실현한 표현이다. 따라서 같은 스택을 배열이나 연결구조로 구현할 수 있으며 선택은 인터페이스 이름이 아니라 실제 연산과 제약으로 한다.

배열은 인덱스로 위치를 계산해 접근이 O(1)이고 연속 순회 지역성이 좋지만 중간 삽입·삭제에는 원소 이동이 필요하다. 연결리스트의 연결 변경은 필요한 참조를 이미 알면 O(1)이다. 삭제에는 이중연결 또는 선행노드를 확보한 단일연결이라는 조건이 필요하며 위치 검색과 i번째 접근은 O(n)이다. 균형 탐색트리는 높이를 log n 수준으로 제한해 검색·삽입·삭제와 정렬·범위질의를 지원하지만 균형복구와 참조공간이 든다. 해시 테이블은 키를 버킷에 대응시켜 관리된 충돌·적재율 아래 기대 O(1) 조회를 제공하지만 최악 O(n), 재해시 지연과 순서·범위질의 부재가 있다.

선택 시 보존할 관계와 순서·중복 계약, 읽기·쓰기·범위·순회 비율, 현재·최대 크기, 평균·최악 지연, 추가 공간·지역성, 변경·복구 비용을 비교한다. 평균 비용만 믿거나 연결리스트의 위치 탐색, 해시 충돌·재해시, 트리 편향과 복합 인덱스 일관성을 누락하면 실패한다. 대표·경계·최악 입력으로 불변조건과 실제 비용을 확인하고 전제가 바뀌면 구조를 재평가한다.

시험에서는 어떻게 묻는가: 25점

대규모 작업 처리시스템의 자료구조를 설계하시오. 도착순서·우선순위·작업번호 조회·선행관계를 지원해야 한다. 요구 연산을 정의하고 구조 조합, 복잡도, 실패조건과 검증방안을 설명하시오.

요구어가 설계이므로 구조 이름을 나열해서는 안 된다. 요구를 연산계약으로 바꾸고, 각 구조의 책임과 상호작용, 복잡도와 불변조건, 부분실패 뒤 복구까지 연결한다. 이 절의 작업 처리기 사례만으로 답안을 만들 수 있다.

답안 목차·풀이·교정 근거 보기

25점 답안 목차

1. 문제 경계와 연산계약
   • enqueue, cancel(id), next(), complete(id), unlock(successor)
   • FIFO·우선순위·키 동등성·선행 완료 불변조건
2. 구조 조합과 작동흐름
   • 우선순위 큐, 해시, 방향 그래프와 미완료 선행 수
   • 등록 → 실행 가능 판정 → 선택 → 완료·후속 해제
3. 복잡도·공간·선택근거
   • 주요 연산별 평균·최악, V·E, 부가 인덱스 공간
   • 단순 큐·정렬 배열과 비교
4. 실패조건과 통제
   • 복합 갱신 불일치, 중복·재시도, 순환, 기아, 재구축
5. 검증과 결론
   • 대표·경계·최악 부하, 불변조건 검사, 전제 변화 시 재평가

25점 답안 도식

작업번호·힙 위치·선행 수와 기준 저장소의 갱신 관계는 작업 처리기 책임 도식을 재사용한다. 해시 조회는 관리된 충돌·적재율 아래 기대 O(1), 힙의 peek는 O(1), 삽입·제거는 O(log n)이며 실행 후보에는 미완료 선행 수가 0인 유효 작업만 들어간다.

상태 변경	유지할 관계와 복구
취소	번호 조회 뒤 힙 즉시 제거 또는 지연 삭제를 명시적으로 선택한다. 이 사례는 선행 취소를 완료로 세지 않으므로 후속 작업은 차단한다.
재시작·불일치	기준 저장소에서 해시·힙을 재구축하고 순환·기아·중복을 검증한다.
위치·집합 검사	즉시 삭제의 위치맵·실행 가능 집합 검사와 지연 삭제의 상태·버전·물리 힙 검사는 아래 완성 답안대로 구분한다.

25점 모범답안

대상은 대기 중인 작업과 선행관계이며, 처리 완료 이력 전체는 별도 저장경계로 둔다. 연산은 작업 등록, 작업번호 조회·취소, 다음 실행작업 선택, 완료와 후속작업 해제다. 같은 우선등급에서는 도착순서를 지키고, 미완료 선행 작업이 하나라도 있으면 실행하지 않으며, 완료·취소를 반복 요청해도 상태가 한 번만 전이돼야 한다.

실행 가능 작업은 비교키 (긴급등급, 도착순번)의 우선순위 큐에 둔다. 최고 우선순위 확인은 O(1), 삽입과 최우선 원소 제거는 O(log n)인 전형적 힙 구현을 사용할 수 있다. 작업번호 해시는 상태와 힙 위치를 보유해 관리된 충돌·적재율에서 기대 O(1) 조회를 지원한다. 위치를 찾은 뒤 힙에서 임의 원소를 제거하는 취소는 O(log n)이고, 모든 교환 때 해시의 위치도 갱신한다. 이 답안의 실제 선택은 위치맵을 사용하는 즉시 삭제다. 지연 삭제를 대안으로 선택한다면 취소 표시만 기대 O(1)이지만 물리 힙에는 무효 항목이 남으므로 집합 불변조건과 공간 예산도 아래처럼 바꿔야 한다. 선행관계는 방향 그래프의 인접 리스트와 작업별 미완료 선행 수로 표현한다. 후속 간선 수를 d, 새로 실행 가능해져 힙에 넣는 작업 수를 k라 하면 카운터 갱신은 O(d), 삽입을 포함한 완료·후속 해제는 O(d+k log n)이고, 새 u → v 간선의 순환 검사는 v에서 u로의 도달성을 확인하므로 최악 O(V+E)다. 전체 공간은 작업과 선행관계에 비례한 O(V+E)에 큐·해시 부가공간을 더한다.

단순 FIFO 큐로는 긴급순위를 반영하기 어렵고, 매번 정렬하는 배열에는 잦은 삽입으로 이동비용이 발생한다. 인접 행렬은 희소한 대규모 선행관계에서 O(V²) 공간을 감당하기 어렵다. 반대로 작업 수가 매우 작고 변경이 드물면 단순 배열이 복잡한 조합보다 검증하기 쉬울 수 있으므로 최대 규모와 연산 비율을 근거로 선택한다.

핵심 실패는 큐·해시·그래프 일부만 변경되는 불일치, 재시도에 의한 중복, 선행 그래프의 순환, 낮은 우선순위 기아와 해시 재구성 지연이다. 기준 저장소의 한 상태전이 규칙과 요청별 중복판별키를 사용하여 재시도가 상태를 두 번 바꾸지 않게 하고, 불일치가 생기면 그 저장소에서 큐·해시를 재구축한다. 등록할 새 의존간선이 출발점으로 돌아오는 경로를 만드는지 검사해 순환을 막고, 대기시간이 길수록 우선도를 올리는 에이징 규칙과 갱신 임계값을 둔다. 선행 작업 취소는 완료로 처리하지 않고 후속 작업을 차단하며, 이미 후속 작업이 실행 중이면 취소를 거절한다는 정책을 상태전이에 포함한다.

검증은 빈 큐, 동일 우선순위, 존재하지 않는 취소, 중복 완료, 긴 선행사슬·순환·최대 부하를 포함한다. 각 변경 뒤 해시에서 실행 가능 상태인 작업 집합과 힙 원소 집합이 일치, blocked 작업은 힙 위치가 없고 미완료 선행 수가 0보다 큼, 각 힙 원소의 위치맵이 실제 인덱스와 일치, 완료 작업은 다시 실행되지 않음을 검사한다. 이처럼 상태별 집합과 위치 관계를 불변조건으로 분리하고 구조별 장점과 복합 갱신비용을 함께 통제해야 대규모에서도 설명 가능한 설계가 된다.

지연 삭제를 택한 대안에서는 실행 가능 작업 집합 = 물리 힙에서 현재 상태·버전과 일치하는 유효 항목의 작업 집합을 검사한다. 취소되거나 이전 버전인 항목은 물리 힙에 남아도 실행 후보에서 제외하고, 각 실행 가능 작업에는 정확히 하나의 유효 항목이 있어야 한다. 예를 들어 물리 힙이 [A, B취소, C]이면 실행 가능 집합은 {A,C}다. 유효 항목 수를 n, 물리 항목 수를 H라 하면 실제 push/pop 비용은 O(log H)이며 한 번의 다음 작업 선택이 여러 무효 항목을 버릴 수도 있다. 따라서 즉시삭제용 위치맵·집합 검사와 지연삭제용 상태·버전 검사를 혼용하지 않고, 무효 항목 비율에 따른 재구축 조건을 정한다.

근거와 표현 범위

추상 자료형, 배열, 연결리스트, 스택, 트리, 그래프와 해시 테이블의 경계는 미국 국립표준기술연구소(National Institute of Standards and Technology, NIST) 정보기술연구소의 Dictionary of Algorithms and Data Structures 항목을 대조했다. 확인한 항목은 abstract data type, array, dynamic array, linked list, stack, tree, graph, hash table, linear probing, separate chaining이다. NIST 사전의 사이트 DOI는 10.18434/T4/1422485이며 기준 확인일은 2026-08-31이다.

본문의 선택 절차, 비교표, 작업 처리기 사례와 모든 도식은 원문 그림이나 표를 옮기지 않고 이 교재의 설명을 위해 독자적으로 구성했다. 복잡도는 특정 언어·라이브러리의 보장값이 아니라 명시한 전형적 구현과 전제 아래의 이론값이다. 실제 제품의 메모리 배치·성장계수·충돌정책·동시성 보장은 해당 구현의 현행 문서를 별도로 확인해야 한다.

30초 정리

1. ADT는 연산계약이고 자료구조는 그 계약과 데이터 관계를 실제 배치·연결로 구현한다.
2. 관계·주요 연산·크기·평균과 최악 지연·공간·순서 요구를 먼저 정한 뒤 배열·연결·트리·그래프·해시 후보를 비교한다.
3. 평균 Big-O만 믿지 말고 충돌·편향·재구성·경계값과 복합 구조의 갱신 일관성을 검증해야 한다.

다음 절에서는 이 구조 위에서 탐색·정렬·그래프 알고리즘이 어떻게 움직이며, 구조의 전제가 알고리즘 비용과 정답을 어떻게 바꾸는지 살펴본다.