배열·연결·스택·큐·트리·그래프·해시
고객 100만 명을 가입 순서로 차례로 보여 주는 일과 고객번호 하나로 즉시 찾는 일은 같은 배치를 요구하지 않는다. 먼저 들어온 요청부터 처리하는 대기열과 마지막으로 연 화면부터 닫는 기록도 접근 순서가 다르다. 조직도는 계층이고 도로망은 여러 방향의 연결이다.
같은 데이터도 놓는 방식에 따라 빠른 일이 달라진다
고객 100만 명을 가입 순서로 차례로 보여 주는 일과 고객번호 하나로 즉시 찾는 일은 같은 배치를 요구하지 않는다. 먼저 들어온 요청부터 처리하는 대기열과 마지막으로 연 화면부터 닫는 기록도 접근 순서가 다르다. 조직도는 계층이고 도로망은 여러 방향의 연결이다.
자료구조는 데이터 모양을 외우는 과목이 아니다. 자주 할 연산과 표현할 관계를 먼저 정하고, 그 연산의 비용이 유리하도록 값과 연결을 배치하는 선택이다.
먼저 되짚기: 자료구조는 값과 값 사이 관계를 담는다
값은 프로그램이 저장·전달·계산하는 실제 데이터였다. 값 하나만 놓는 데서 끝나지 않고 순서, 부모–자식, 임의 연결, 키와 위치의 대응을 추가하면 자료구조가 된다. 어떤 관계를 보존할지와 어떤 연산을 빠르게 할지가 배치를 결정한다.
자료구조
자료구조는 필요한 연산의 비용을 고려해 데이터와 관계를 배치하는 방식이다. 조회·삽입·삭제·순회·최솟값 찾기 중 어느 연산이 중요한지에 따라 같은 값에도 다른 구조가 적합하다. 저장공간과 구현 복잡성도 비용에 포함된다.
순차구조 전에 되짚기
자료구조는 필요한 연산에 맞춰 값과 관계를 배치하는 방식이었다. 이제 그 관계가 앞뒤 순서일 때 어떤 배치가 필요한지 좁혀 본다.
먼저 네 장의 카드를 움직여 본다
카드 10, 20, 30, 40을 순서대로 놓자. 세 번째 값을 묻는 것은 위치 조회, 값 30이 어디 있는지 묻는 것은 값 검색, 20과 30 사이에 25를 넣는 것은 중간 삽입이다. 세 작업은 비슷해 보여도 필요한 정보와 작업량이 다르다. 순회는 정한 순서대로 원소를 하나씩 방문하는 일이다.
세 번째 칸의 위치를 바로 계산할 수 있어도 값 30이 몇 번째인지는 아직 모를 수 있다. 반대로 값 30을 빠르게 찾는 색인을 만들어도 앞뒤 순서가 자동으로 관리되는 것은 아니다. 아래 예제는 같은 네 값으로 이 차이를 확인한다. 표시한 이동·참조 횟수는 작은 교육용 계산이며 실제 장치의 실행시간이 아니다.
순차구조
순차구조는 원소가 앞뒤 순서를 갖도록 배치된 구조다. 배열은 원소를 연속된 위치에 두어 번호로 접근하고, 연결 구조는 각 원소가 다음 원소의 참조를 가져 순서를 나타낸다. 연결을 바꿀 위치와 필요한 앞 원소를 이미 알고 있으면 연결 수정은 작지만, 그 위치를 찾는 비용은 별도다.L1
배열: 위치를 계산할 수 있지만 중간 자리는 만들어야 한다
배열의 칸 번호를 인덱스라고 하며 여기서는 0부터 시작한다. [10,20,30,40]에서 세 번째 값은 인덱스 2의 30이다. 같은 크기 4바이트 원소를 주소 1000부터 연속 저장한 가정에서는 인덱스 2의 시작 주소가 1000+2×4=1008이다. 이 계산은 앞의 두 값을 읽어 보고 찾는 과정이 아니다. 실제 언어의 배열·목록은 값 대신 참조를 연속 저장할 수도 있으므로 구체 메모리 배치는 따로 확인한다.
이제 다섯 번째 빈칸이 이미 확보된 배열에서 인덱스 2에 25를 삽입하자.
| 순서 | 배열 상태 | 동작 |
|---|---|---|
| 0 | [10][20][30][40][빈칸] | 다섯 번째 빈칸이 이미 있음 |
| 1 | [10][20][30][40][40] | 오른쪽 끝 40을 뒤로 이동 |
| 2 | [10][20][30][30][40] | 30을 뒤로 이동 |
| 3 | [10][20][25][30][40] | 비운 위치에 25를 기록 |
기존 원소 이동은 2회이고 새 값 쓰기는 1회다. 오른쪽 끝부터 옮겨야 아직 필요한 값을 덮어쓰지 않는다. 첫 위치에 삽입한다면 기존 네 원소를 옮겨야 한다. 빈칸이 없으면 더 큰 공간 확보와 복사도 필요할 수 있어, 위의 2회는 여유 공간이 있는 이 예제의 값이다.
배열의 위치 접근이 빠르다는 말은 모든 연산이 빠르다는 말이 아니다. 순서를 유지하면서 중간에 원소를 삽입하거나 삭제하면 뒤 원소 이동을 고려한다. 번호 접근과 연속 순회가 주된 경우에는 이 배치가 유리할 수 있다.L1
연결: 값은 그대로 두고 다음 위치를 바꾼다
값과 다음 원소의 참조를 묶어 저장한 작은 단위를 노드라고 하자. 참조는 다음 노드를 찾아갈 수 있게 하는 정보다. 다음 연결은 메모리에서 나란히 놓여 있다는 뜻이 아니다.
B와 C 사이에 X를 연결하고 기존 값은 이동하지 않는다 · 상태 따라가기
A10→B20→C30→D40에 X25를 넣는다. 모든 단계에서 앞쪽 연결·새 노드·뒤쪽의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.
상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.
원래 순서는 A(10)→B(20)→C(30)→D(40)다. B와 C를 이미 아는 조건에서 X.next=C를 먼저 정하고 B.next=X로 바꾸면 A→B→X→C→D가 된다. 이 그림은 변경 후 next 연결이며 실제 메모리의 인접 배치가 아니다. B를 찾아가는 비용과 노드 확보는 별도다.
이 예의 조건
- 원래 순서는 A(10)→B(20)→C(30)→D(40)다. B와 C를 이미 아는 조건에서 X.next=C를 먼저 정하고 B.next=X로 바꾸면 A→B→X→C→D가 된다. 이 그림은 변경 후 next 연결이며 실제 메모리의 인접 배치가 아니다. B를 찾아가는 비용과 노드 확보는 별도다.
- 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.
관계도의 보충 설명
| 대상 | 원 설명 |
|---|---|
| A(10) | next: B |
| B(20) | next: X |
| X(25) | next: C |
| C(30) | next: D |
| D(40) | next: 끝 |
| 연결 | 원 라벨·방향 |
|---|---|
| A(10) → B(20) | 라벨 없는 연결 / 정방향 / 실선 |
| B(20) → X(25) | 라벨 없는 연결 / 정방향 / 실선 |
| X(25) → C(30) | 라벨 없는 연결 / 정방향 / 실선 |
| C(30) → D(40) | 라벨 없는 연결 / 정방향 / 실선 |
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| 삽입 전 A10→B20→C30→D40에 X25를 넣는다. |
|
|
| X 다음 준비 먼저 X.next=C로 연결한다. |
|
|
| B에서 공개 B.next=X로 바꾸면 X를 거쳐 C로 이어진다. |
|
|
| 전체 확인 A10→B20→X25→C30→D40으로 이어진다. |
|
|
B와 C 사이에 X를 연결하고 기존 값은 이동하지 않는다 · 상태 따라가기
A10→B20→C30→D40에 X25를 넣는다. 모든 단계에서 앞쪽 연결·새 노드·뒤쪽의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.
상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.
원래 순서는 A(10)→B(20)→C(30)→D(40)다. B와 C를 이미 아는 조건에서 X.next=C를 먼저 정하고 B.next=X로 바꾸면 A→B→X→C→D가 된다. 이 그림은 변경 후 next 연결이며 실제 메모리의 인접 배치가 아니다. B를 찾아가는 비용과 노드 확보는 별도다.
이 예의 조건
- 원래 순서는 A(10)→B(20)→C(30)→D(40)다. B와 C를 이미 아는 조건에서 X.next=C를 먼저 정하고 B.next=X로 바꾸면 A→B→X→C→D가 된다. 이 그림은 변경 후 next 연결이며 실제 메모리의 인접 배치가 아니다. B를 찾아가는 비용과 노드 확보는 별도다.
- 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.
관계도의 보충 설명
| 대상 | 원 설명 |
|---|---|
| A(10) | next: B |
| B(20) | next: X |
| X(25) | next: C |
| C(30) | next: D |
| D(40) | next: 끝 |
| 연결 | 원 라벨·방향 |
|---|---|
| A(10) → B(20) | 라벨 없는 연결 / 정방향 / 실선 |
| B(20) → X(25) | 라벨 없는 연결 / 정방향 / 실선 |
| X(25) → C(30) | 라벨 없는 연결 / 정방향 / 실선 |
| C(30) → D(40) | 라벨 없는 연결 / 정방향 / 실선 |
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| 삽입 전 A10→B20→C30→D40에 X25를 넣는다. |
|
|
| X 다음 준비 먼저 X.next=C로 연결한다. |
|
|
| B에서 공개 B.next=X로 바꾸면 X를 거쳐 C로 이어진다. |
|
|
| 전체 확인 A10→B20→X25→C30→D40으로 이어진다. |
|
|
B 바로 뒤에 새 노드 X(25)를 넣으려면 먼저 X.next=C, 그다음 B.next=X로 연결한다. next는 다음 노드 참조의 이름이다. 기존 C·D의 값은 이동하지 않고 결과는 A→B→X→C→D가 된다. 먼저 B의 다음 참조를 덮어쓰고 원래 C의 위치를 잃으면 뒤쪽 연결이 끊길 수 있으므로 순서도 중요하다.
그러나 처음에 시작 노드만 알고 ‘세 번째 위치에 넣어라’는 요청을 받으면 B까지 찾아가야 한다. 단일 연결에서 마지막 노드를 삭제할 때도 그 앞 노드를 모르면 앞에서부터 찾아야 한다. 연결 수정의 작은 비용과 위치 탐색의 비용을 합쳐야 전체 비용이다. 삭제한 노드의 저장공간 회수·다른 참조 처리도 구현에서 필요하다.L1
따라서 배열 대 연결을 ‘조회용 대 삽입용’ 두 단어로 외우지 않는다. 무엇을 이미 알고 있는지, 앞뒤 순서와 메모리의 대가를 확인한다. 입력 크기가 커질 때 작업 수를 표현하는 방법은 다음 절의 복잡도로 이어진다.
스택·큐 전에 되짚기
순차구조는 원소의 앞뒤 순서를 보존한다. 스택과 큐는 그 순서를 유지하면서 어느 끝에서 넣고 꺼낼지를 제한한다.
스택과 큐
스택과 큐는 최근 항목 우선 또는 먼저 온 항목 우선으로 접근을 제한한 구조다. 스택은 마지막에 넣은 항목을 먼저 꺼내며 함수 호출·실행 취소에 적합하다. 큐는 먼저 넣은 항목을 먼저 꺼내며 도착 순서대로 작업을 대기시키는 데 적합하다.
같은 입력을 넣어도 꺼내는 순서는 달라진다
스택의 넣기는 push, 꺼내기는 pop이라고 부른다. 큐의 넣기는 enqueue, 꺼내기는 dequeue라고 부른다. 영어 이름보다 어느 쪽에서 꺼내는지부터 추적하자. 아래 표에서 스택은 오른쪽이 맨 위, 큐는 왼쪽이 맨 앞이다.
| 행동 | 스택: 남은 항목 / 꺼낸 값 | 큐: 남은 항목 / 꺼낸 값 |
|---|---|---|
| 빈 상태에 A, B, C 순서로 넣기 | [A,B,C] / 없음 | [A,B,C] / 없음 |
| 한 번 꺼내기 | [A,B] / C | [B,C] / A |
| D 넣기 | [A,B,D] / 없음 | [B,C,D] / 없음 |
| 다시 한 번 꺼내기 | [A,B] / D | [C,D] / B |
스택은 최근 작업의 취소에, 큐는 접수 순서의 처리에 맞는다. 이는 접근 규칙이며 배열·연결이라는 저장 방식과 다른 구분이다. 배열로 큐를 만들 수도 있지만 맨 앞을 꺼낼 때마다 모든 원소를 옮기면 작업 수가 커진다. 앞·뒤 위치를 관리하는 원형 배열이나 양 끝 연산을 지원하는 구현을 검토할 수 있다. Python 공식 설명도 list를 스택에 사용하는 예와, 앞쪽 원소 이동을 피하는 큐 구현의 차이를 구별한다.L2
빈 구조에서 꺼낼 때 오류를 낼지, 값이 없다고 반환할지, 기다릴지는 계약으로 정한다. 크기 한도가 있는 큐가 가득 찼을 때도 기다림·거절·폐기 중 어떤 처리를 하는지 밝혀야 한다. 일반 FIFO 큐가 긴급 작업을 먼저 처리한다고 가정하지 않는다.
FIFO는 First-In, First-Out, 즉 먼저 넣은 것을 먼저 꺼낸다는 선입선출의 약어다. “먼저”는 이 큐의 접수순서를 가리키므로 긴급도와 같다는 뜻은 아니다.
트리·그래프 전에 되짚기
자료구조는 보존해야 할 관계에 맞춰 데이터를 조직한다. 앞뒤 순서만으로 부족한 계층과 일반 연결 관계는 노드와 간선으로 표현한다.
트리와 그래프
트리와 그래프는 계층 관계 또는 일반적인 연결 관계를 노드와 간선으로 표현한 구조다. 노드는 대상, 간선은 두 대상의 관계다. 연결되어 있고 순환이 없는 무방향 그래프를 트리라고 하며, 그중 뿌리 하나를 정하면 부모–자식 계층으로 읽을 수 있다. 일반 그래프는 방향·순환·가중치를 가질 수 있어 도로, 친구, 서비스 의존 관계 같은 망을 표현한다.
조직의 소속과 이동 경로를 같은 관계로 읽지 않는다
‘도서관→자료팀, 도서관→운영팀, 자료팀→분류담당’은 이 사례에서 각 부서의 주된 소속을 나타내는 뿌리 있는 트리다. 뿌리 이외의 각 대상에는 부모가 하나다. 실제 겸직·협업 관계까지 이 소속 트리만으로 모두 표현한다고 가정하지 않는다.
별도 이동망의 연결을 A–B, B–C, C–A, C–D로 정하면 A에서 B·C를 지나 다시 A로 돌아올 수 있다. 같은 대상을 계속 따라가면 순환하므로 이미 발견한 노드를 기록한다. 실제 그래프 탐색에서는 무엇을 방문했다고 표시할지와 인접 노드를 살펴볼 순서를 정해야 한다.
예를 들어 A에서 시작하고 이웃을 문자순으로 살피는 큐 기반 탐색에서는 처음에 A를 발견 표시하고 큐에 넣는다. A를 꺼낸 뒤 B·C를 발견 표시해 넣고, B를 꺼냈을 때 이미 표시된 A·C는 다시 넣지 않는다. C를 꺼냈을 때 D를 추가하므로 꺼내는 순서는 A, B, C, D다. 이것은 연결된 노드를 찾는 예제이며 가중치가 다른 도로의 최단거리 계산이라고 주장하지 않는다.
트리라는 이름만으로 값의 범위 검색이 빨라지는 것도 아니다. 일반 조직도와 키의 대소 관계를 유지하는 탐색용 트리는 다른 사용이다. 뒤의 자료구조 선택 절에서는 탐색 순서·균형·그래프 표현에 따른 비용을 구체화한다.
해시 전에 되짚기
수 표현에서는 비트열과 자릿값 규칙으로 값을 수에 대응시켰다. 해시에서는 이 직관을 확장해 키를 계산된 위치 후보에 대응시키되 같은 위치가 같은 키라는 뜻은 아님을 확인한다.
해시 기반 구조
해시 기반 구조는 키를 계산된 위치에 대응시켜 평균적으로 빠르게 조회하는 구조다. 해시 함수가 키를 배열 위치 후보로 바꾸며, 서로 다른 키가 같은 위치 후보를 만드는 충돌은 별도 규칙으로 해결한다. 키의 정확한 순서보다는 키로 값을 찾는 일이 중심이다.
같은 칸을 가리키는 두 키를 구별한다
정수 키를 5로 나눈 나머지를 저장 위치 후보로 쓰는 자체 예를 보자. 위치는 0~4이고, 12와 17의 나머지는 모두 2다. 같은 칸으로 모아 둘 연결 목록을 사용한다면 위치 2에는 (12,자료A)→(17,자료B)를 저장한다. 이 충돌 목록이 버킷의 한 구현이다.
나머지는 12=5×2+2, 17=5×3+2에서 5의 묶음을 만든 뒤 남은 2를 뜻한다. 키 22도 22=5×4+2라서 같은 위치 후보를 얻지만 키의 값 12·17·22는 서로 다르다. 위치 계산 뒤 실제 키를 다시 비교하는 이유가 여기에 있다.
17을 찾을 때는 먼저 위치 2를 계산한다. 그 안에서 키 12는 다르므로 지나가고, 키 17을 확인한 뒤 자료B를 반환한다. 같은 해시 위치는 같은 키라는 뜻이 아니므로 실제 키의 동등성 비교가 필요하다. 22도 나머지가 2지만 아직 넣지 않았다면 버킷을 살핀 뒤 없음으로 답해야 한다.
평균적으로 빠른 조회는 키가 지나치게 몰리지 않고 적절한 공간과 충돌 처리가 있다는 조건을 가진다. 많은 키가 같은 버킷에 모이면 비교 횟수가 늘 수 있다. 이 예의 단순 나머지 함수는 원리 설명용이지 모든 데이터에 좋은 해시 함수라는 권장이 아니다. 크기를 바꿀 때는 바뀐 위치에 맞게 재배치하는 비용도 생긴다.
여기서 해시는 조회 위치를 정하는 용도다. 보안에서 배우는 암호학적 해시의 성질을 자동으로 갖는다고 보지 않는다. 자료구조의 충돌 처리와 메시지의 보안·무결성은 다른 질문이다.
구조를 고르는 질문 지도
연산과 관계의 선택표에서 후보를 좁힌다. 앞뒤 순서는 순차구조이며 그중 최근 항목 우선은 스택, 먼저 온 항목 우선은 큐다. 부모–자식은 트리, 일반 연결·경로는 그래프, 정확한 키 조회는 해시를 검토한다. 선택 뒤 조회·삽입·삭제·순회 비용과 빈 구조·충돌·순환·최악 조건을 확인한다.
이 도식은 구조 이름을 먼저 고르는 표가 아니다. 먼저 관계와 자주 할 연산을 정한 뒤 후보를 좁히고, 실제 실패조건과 비용을 대조하는 순서를 나타낸다.
관계에 맞춰 구조를 고르는 작은 지도
순차구조의 연속 배열과 next 연결은 배열·연결에서 비교한다. 스택은 마지막 C, 큐는 먼저 온 A를 꺼내는 실제 상태표로 읽는다. 도서관→자료팀·운영팀, 자료팀→분류담당의 계층 트리와 A–B·B–C·C–A·C–D의 순환 이동망은 관계 예제로 구분하고, 해시는 키→위치 후보→실제 키 비교→값의 계약을 지킨다.
구조는 함께 조합할 수 있다. 작업 큐의 대기 항목을 큐로 유지하면서 작업 식별자로 빠르게 취소하기 위해 해시 구조를 함께 둘 수 있다. 이 경우 두 구조가 같은 작업 집합을 나타내므로 추가·삭제를 둘 다 성공시키는 일관성 규칙이 필요하다.
한 담당 흐름만 갱신하는 메모리 내 접수 모형을 실제로 진행해 보자. 신청 A·B·C를 키 기반 조회 구조에 등록하고 각 번호를 큐에 넣은 뒤에만 성공을 응답하면 큐는 [A,B,C], 세 신청 상태는 대기다. 등록 후 큐 추가가 실패했다면 등록을 되돌리거나 미완료로 표시하며 접수 성공을 알리지 않는다. 같은 번호가 다시 오면 기존 내용을 확인해 새 큐 항목을 만들지 않는다. 저장 장애와 여러 서버의 동시 갱신은 이 작은 모형의 보장 범위에서 제외한다.
B를 취소하면 조회 구조의 B 상태만 취소로 바꾸고 큐는 [A,B,C]로 둔다. 처리 때 A를 꺼내 대기 상태를 확인하고 완료로 바꾼 뒤, B를 꺼내 취소 상태라 건너뛰고, C를 꺼내 완료로 바꾼다. 결과는 A·C 완료, B 취소, 빈 큐다. 이 선택은 번호별 큐 노드를 별도 색인해 즉시 지우는 복잡성을 줄이는 대신 취소된 번호가 차례까지 남는 공간과 지연을 부담한다. 그 비용이 허용되지 않을 때만 더 직접적인 삭제 구조를 검토한다.
편집 취소는 다른 상태다. 신청 내용이 초안→수정1→수정2로 바뀔 때 이전 내용 초안·수정1을 스택에 넣어 두면 한 번 꺼낸 수정1로 되돌리고 다음은 초안으로 되돌린다. 이 스택은 내용을 복원할 근거이지 이미 보낸 외부 알림까지 자동 취소하는 장치가 아니다. 위 세 상태를 적은 뒤 B 대신 C를 취소해 보면 같은 원리로 A·B만 처리해야 함을 예측할 수 있다.
연산과 관계로 판단한다
| 주된 요구 | 우선 검토할 구조 | 함께 확인할 비용 |
|---|---|---|
| 번호로 원소 접근·연속 순회 | 배열형 순차구조 | 중간 삽입·크기 변경 |
| 위치와 앞 연결을 아는 중간 변경 | 연결형 순차구조 | 위치 탐색·추가 참조 공간 |
| 최근 작업 되돌리기 | 스택 | 오래된 항목 직접 접근 |
| 도착 순서 처리 | 큐 | 가득 참·긴급 우선처리 요구 |
| 계층 탐색 | 트리 | 깊이·부모 변경·관계 종류 |
| 임의 연결·경로 탐색 | 그래프 | 순환·방향·방문 기록 |
| 정확한 키 조회 | 해시 | 충돌·크기 조정·순서 요구 별도 |
자료구조 선택 질문은 어떤 관계인가 → 가장 잦은 연산은 무엇인가 → 최대 데이터 크기는 얼마인가 → 순서와 중복을 보존해야 하는가 → 최악의 지연을 어디까지 허용하는가 순으로 한다.
실패조건과 방어
구조 이름부터 선택하면 실제 연산과 관계를 놓치기 쉽다. 대표 읽기·쓰기 시나리오와 크기를 먼저 적는다.
빈 구조와 경계 누락은 빈 스택에서 꺼내거나 배열 범위를 넘는 오류를 만든다. 비어 있음·가득 참·첫·마지막 위치를 계약에 넣는다.
해시 충돌을 무시하면 다른 키의 값을 덮어쓸 수 있다. 키 동등성·충돌 처리·크기 조정 규칙을 둔다.
그래프 순환을 무시하면 같은 노드를 무한히 방문할 수 있다. 방문 여부를 기록하고 방향·가중치 의미를 명시한다.
복합 구조 불일치는 큐에서는 삭제한 항목이 해시에는 남아 있는 경우다. 하나의 연산 경계에서 두 구조를 함께 변경하거나 실패 시 복구한다.
평균 비용만 신뢰하면 특정 입력에서 한 위치에 몰리거나 탐색 트리가 한쪽으로 늘어지는 상황을 놓친다. 최악 조건과 입력 분포를 함께 검토한다.
문제: 주요 자료구조를 비교하고 선택기준을 설명하시오.
자료구조 선택 모범답안 보기
모범답안 축약본: 관계와 주된 연산으로 구조를 고른다
자료구조는 값과 값 사이 관계를 배치하여 저장·조회·삽입·삭제·순회의 비용을 정하는 방식이다. 배열과 연결구조 같은 순차구조는 앞뒤 순서를 표현하되 임의 접근과 중간 삽입 비용이 다르다. 스택은 마지막 입력부터, 큐는 먼저 입력부터 처리해 호출 복귀와 작업 대기열에 맞는다. 트리는 부모–자식 계층, 그래프는 일반적인 연결과 경로를 표현한다. 키 순서에 따른 범위 탐색은 이를 지원하는 탐색용 트리의 조건을 별도로 본다. 해시는 키를 해시값과 버킷에 대응시켜 평균적으로 빠른 동등 조회를 제공하지만 충돌 처리와 최악 비용이 있다. 선택은 표현할 관계, 가장 잦은 연산, 순서 필요, 최대 크기, 메모리와 최악 지연으로 한다. 경계값, 빈 구조, 해시 충돌, 그래프 순환과 복합 구조의 동시 갱신을 확인해 한 구조의 장점만 보고 고르는 오류를 막는다.
자체 10점 연습: 같은 삽입과 꺼내기를 끝까지 설명한다
네 값 10, 20, 30, 40 사이에 25를 삽입할 때 배열과 단일 연결 구조를 비교하시오. A, B, C를 넣고 한 번 꺼낸 뒤 D를 넣어 다시 꺼낼 때 스택과 큐의 차이도 설명하시오.
10점 풀이 구성과 완성 답안 보기
풀이 구성: 무엇을 이미 아는지 밝히고, 실제로 옮기는 값·연결을 쓴 다음 꺼낸 순서를 적는다. 정식 국가시험 문항이나 채점표가 아닌 자체 연습이다.
답안 도식: 이동·연결·꺼내기 순서를 분리한다
| 요구된 동작 | 실제 추적·결과 |
|---|---|
| 배열의 가운데에 25 삽입 | [10][20][30][40][ ]에서 40 이동→30 이동→25 기록 |
| B 뒤 연결 삽입 | B(20)→C(30)에서 X.next=C 뒤 B.next=X; C·D 값은 그대로 |
| A,B,C 입력·1회 꺼냄·D 입력·다시 꺼냄 | 스택 C→D, 큐 A→B |
배열의 값 이동 횟수와 연결 구조의 위치 탐색 비용을 한 숫자로 섞지 않고, 스택·큐는 저장 배치가 아니라 꺼내는 규칙이라는 점을 결론에 연결한다.
완성 답안: 여유 공간이 있는 배열에서 인덱스 2에 25를 넣으면 40과 30을 오른쪽부터 옮기고 25를 쓴다. 기존 값 이동은 2회다. 단일 연결에서 B(20)와 다음 C(30)를 이미 알면 새 X의 다음을 C로, B의 다음을 X로 바꾸며 C·D의 값은 이동하지 않는다. 다만 시작점만 아는 경우 B를 찾는 비용과 새 노드 확보는 별도다. 두 구조의 우열은 위치 접근·중간 변경의 빈도와 탐색·공간 비용으로 판단한다.
스택은 마지막에 들어간 값을 꺼내므로 C와 D를 차례로 꺼내고 A·B가 남는다. 큐는 먼저 들어간 값을 꺼내므로 A와 B를 꺼내고 C·D가 남는다. 스택·큐는 접근 순서이고 배열·연결은 저장 방식이므로 같은 분류축으로 합치지 않는다. 빈 구조와 용량 한계도 계약에 포함한다.
자체 25점 연습: 작은 접수 서비스를 실제로 구성한다
도착 순서의 처리, 최근 편집 취소, 신청번호 조회, 부서 소속과 이동 경로를 제공하는 접수 서비스를 설계하시오. 불필요한 복합 구조를 피하고 경계·충돌·순환의 확인 방법을 포함하시오.
가정: 한 담당 처리 흐름이 상태를 갱신하는 메모리 내 교육 모형이다. 저장소 장애 후 보존·여러 서버의 동시 처리는 이 예에서 보장하지 않는다. 신청에는 고유번호·접수순서·내용·상태가 있다. 취소된 신청은 큐에서 바로 찾아 제거하지 않고 상태를 바꾸어 처리 차례에 건너뛰는 안을 선택한다.
25점 설계 구성과 완성 답안 보기
답안 구성: 먼저 각 요구가 순서·키 조회·계층·일반 연결 중 무엇을 필요로 하는지 나눈다. 이어 접수 성공의 변경 경계, 취소된 신청의 처리와 받아들인 공간 비용을 적는다. 마지막에 충돌·빈 구조·순환·부분 실패의 확인 사례를 제시하고 메모리 내 단일 처리라는 보장 범위를 밝힌다. 구조 선택과 실패조건을 구체적 동작으로 옮기는 순서다.
답안 도식: 요구 하나를 구조 하나로 억지로 대응시키지 않는다
등록과 큐 반영을 모두 확인한 뒤 접수 성공을 알린다 · 상태 따라가기
기존 번호 입력의 내용·상태를 확인한 대안에서는 새로 등록하지 않는다. 모든 단계에서 요청 등록·대기열·결과의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.
상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.
신청번호의 자료 등록과 큐 추가를 함께 확인한다. 같은 번호는 기존 내용·상태를 확인해 새 큐 항목을 만들지 않는다. 중간 실패는 되돌리거나 미완료로 남기며 성공 응답으로 숨기지 않는다. 한 담당 흐름의 메모리 모형이며 저장 장애·여러 서버의 동시성 보장은 제외한다.
이 예의 조건
- 신청번호의 자료 등록과 큐 추가를 함께 확인한다. 같은 번호는 기존 내용·상태를 확인해 새 큐 항목을 만들지 않는다. 중간 실패는 되돌리거나 미완료로 남기며 성공 응답으로 숨기지 않는다. 한 담당 흐름의 메모리 모형이며 저장 장애·여러 서버의 동시성 보장은 제외한다.
- 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.
관계도의 보충 설명
| 대상 | 원 설명 |
|---|---|
| 신청번호·내용 | 원그림의 대상 |
| 자료 등록 + 큐 추가 | 키·접수순서 함께 반영 |
| 둘 다 완료? | 원그림의 대상 |
| 접수 성공 | 같은 작업 집합 확인 |
| 되돌림·미완료 | 접수 성공을 알리지 않음 |
| 연결 | 원 라벨·방향 |
|---|---|
| 신청번호·내용 → 자료 등록 + 큐 추가 | 라벨 없는 연결 / 정방향 / 실선 |
| 자료 등록 + 큐 추가 → 둘 다 완료? | 라벨 없는 연결 / 정방향 / 실선 |
| 둘 다 완료? → 접수 성공 | 예 / 정방향 / 실선 |
| 둘 다 완료? → 되돌림·미완료 | 아니오 / 정방향 / 실선 |
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| 같은 번호의 재전송 기존 번호 입력의 내용·상태를 확인한 대안에서는 새로 등록하지 않는다. |
|
|
| 별도 입력: 새 번호 새 신청번호의 시작점으로 재설정하여 해시 등록과 큐 추가를 함께 진행한다. |
|
|
| 완료 판정의 성공 대안 새 번호의 두 반영을 모두 확인한 완료 판정에서 성공인 경우다. |
|
|
| 완료 판정의 실패 대안 새 번호의 완료 판정 시작점으로 재설정하고 부분 실패를 본다. |
|
|
등록과 큐 반영을 모두 확인한 뒤 접수 성공을 알린다 · 상태 따라가기
기존 번호 입력의 내용·상태를 확인한 대안에서는 새로 등록하지 않는다. 모든 단계에서 요청 등록·대기열·결과의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.
상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.
신청번호의 자료 등록과 큐 추가를 함께 확인한다. 같은 번호는 기존 내용·상태를 확인해 새 큐 항목을 만들지 않는다. 중간 실패는 되돌리거나 미완료로 남기며 성공 응답으로 숨기지 않는다. 한 담당 흐름의 메모리 모형이며 저장 장애·여러 서버의 동시성 보장은 제외한다.
이 예의 조건
- 신청번호의 자료 등록과 큐 추가를 함께 확인한다. 같은 번호는 기존 내용·상태를 확인해 새 큐 항목을 만들지 않는다. 중간 실패는 되돌리거나 미완료로 남기며 성공 응답으로 숨기지 않는다. 한 담당 흐름의 메모리 모형이며 저장 장애·여러 서버의 동시성 보장은 제외한다.
- 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.
관계도의 보충 설명
| 대상 | 원 설명 |
|---|---|
| 신청번호·내용 | 원그림의 대상 |
| 자료 등록 + 큐 추가 | 키·접수순서 함께 반영 |
| 둘 다 완료? | 원그림의 대상 |
| 접수 성공 | 같은 작업 집합 확인 |
| 되돌림·미완료 | 접수 성공을 알리지 않음 |
| 연결 | 원 라벨·방향 |
|---|---|
| 신청번호·내용 → 자료 등록 + 큐 추가 | 라벨 없는 연결 / 정방향 / 실선 |
| 자료 등록 + 큐 추가 → 둘 다 완료? | 라벨 없는 연결 / 정방향 / 실선 |
| 둘 다 완료? → 접수 성공 | 예 / 정방향 / 실선 |
| 둘 다 완료? → 되돌림·미완료 | 아니오 / 정방향 / 실선 |
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| 같은 번호의 재전송 기존 번호 입력의 내용·상태를 확인한 대안에서는 새로 등록하지 않는다. |
|
|
| 별도 입력: 새 번호 새 신청번호의 시작점으로 재설정하여 해시 등록과 큐 추가를 함께 진행한다. |
|
|
| 완료 판정의 성공 대안 새 번호의 두 반영을 모두 확인한 완료 판정에서 성공인 경우다. |
|
|
| 완료 판정의 실패 대안 새 번호의 완료 판정 시작점으로 재설정하고 부분 실패를 본다. |
|
|
큐에서 번호를 꺼낸 뒤 현재 신청 상태를 다시 확인한다 · 상태 따라가기
대기열 항목과 현재 업무 상태를 같은 것으로 보지 않는다. 모든 단계에서 대기열·현재 업무 상태의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.
상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.
접수 큐는 번호 순서만 보관하고 해시 조회는 내용·현재 상태를 찾는다. 현재 상태가 취소면 건너뛰고 대기면 처리해 완료로 바꾼다. A·B·C 접수 후 B를 취소하면 A·C만 완료된다. 편집 취소 스택·부서 소속 트리·이동 그래프는 별도 관계와 목적을 가지며 외부 효과를 자동 취소하지 않는다.
이 예의 조건
- 접수 큐는 번호 순서만 보관하고 해시 조회는 내용·현재 상태를 찾는다. 현재 상태가 취소면 건너뛰고 대기면 처리해 완료로 바꾼다. A·B·C 접수 후 B를 취소하면 A·C만 완료된다. 편집 취소 스택·부서 소속 트리·이동 그래프는 별도 관계와 목적을 가지며 외부 효과를 자동 취소하지 않는다.
- 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.
관계도의 보충 설명
| 대상 | 원 설명 |
|---|---|
| 접수 큐 | A · B · C 순서 |
| 신청번호 해시 조회 | 실제 키·현재 상태 비교 |
| 현재 상태? | 대기 / 취소 |
| 건너뛰기 | B: 취소 상태 |
| 처리 후 완료 | A·C: 대기 상태 |
| 연결 | 원 라벨·방향 |
|---|---|
| 접수 큐 → 신청번호 해시 조회 | 라벨 없는 연결 / 정방향 / 실선 |
| 신청번호 해시 조회 → 현재 상태? | 라벨 없는 연결 / 정방향 / 실선 |
| 현재 상태? → 건너뛰기 | 취소 / 정방향 / 실선 |
| 현재 상태? → 처리 후 완료 | 대기 / 정방향 / 실선 |
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| A·B·C 대기 대기열 항목과 현재 업무 상태를 같은 것으로 보지 않는다. |
|
|
| B 취소 B 항목은 남아도 현재 상태는 취소로 바뀐다. |
|
|
| 꺼낸 뒤 재확인 A를 완료하고 B를 꺼낼 때 현재 취소 상태를 확인해 건너뛴다. |
|
|
| C 완료 다음 유효한 C를 처리해 A와 C만 완료한다. |
|
|
큐에서 번호를 꺼낸 뒤 현재 신청 상태를 다시 확인한다 · 상태 따라가기
대기열 항목과 현재 업무 상태를 같은 것으로 보지 않는다. 모든 단계에서 대기열·현재 업무 상태의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.
상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.
접수 큐는 번호 순서만 보관하고 해시 조회는 내용·현재 상태를 찾는다. 현재 상태가 취소면 건너뛰고 대기면 처리해 완료로 바꾼다. A·B·C 접수 후 B를 취소하면 A·C만 완료된다. 편집 취소 스택·부서 소속 트리·이동 그래프는 별도 관계와 목적을 가지며 외부 효과를 자동 취소하지 않는다.
이 예의 조건
- 접수 큐는 번호 순서만 보관하고 해시 조회는 내용·현재 상태를 찾는다. 현재 상태가 취소면 건너뛰고 대기면 처리해 완료로 바꾼다. A·B·C 접수 후 B를 취소하면 A·C만 완료된다. 편집 취소 스택·부서 소속 트리·이동 그래프는 별도 관계와 목적을 가지며 외부 효과를 자동 취소하지 않는다.
- 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.
관계도의 보충 설명
| 대상 | 원 설명 |
|---|---|
| 접수 큐 | A · B · C 순서 |
| 신청번호 해시 조회 | 실제 키·현재 상태 비교 |
| 현재 상태? | 대기 / 취소 |
| 건너뛰기 | B: 취소 상태 |
| 처리 후 완료 | A·C: 대기 상태 |
| 연결 | 원 라벨·방향 |
|---|---|
| 접수 큐 → 신청번호 해시 조회 | 라벨 없는 연결 / 정방향 / 실선 |
| 신청번호 해시 조회 → 현재 상태? | 라벨 없는 연결 / 정방향 / 실선 |
| 현재 상태? → 건너뛰기 | 취소 / 정방향 / 실선 |
| 현재 상태? → 처리 후 완료 | 대기 / 정방향 / 실선 |
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| A·B·C 대기 대기열 항목과 현재 업무 상태를 같은 것으로 보지 않는다. |
|
|
| B 취소 B 항목은 남아도 현재 상태는 취소로 바뀐다. |
|
|
| 꺼낸 뒤 재확인 A를 완료하고 B를 꺼낼 때 현재 취소 상태를 확인해 건너뛴다. |
|
|
| C 완료 다음 유효한 C를 처리해 A와 C만 완료한다. |
|
|
복합 구조에서는 각 구조의 장점보다 같은 신청 상태를 서로 다르게 보게 되는 부분 실패를 먼저 점검한다. 실제 영속성·다중 서버 동시성은 이 메모리 내 교육 모형의 보장 범위가 아니다.
완성 설계 답안: 신청번호로 조회할 자료는 키 기반 구조에 두고, 접수 큐에는 신청번호를 순서대로 넣는다. 같은 번호가 다시 오면 기존 내용·상태를 확인하여 새 신청으로 중복 등록하지 않는다. 새 번호의 자료 등록과 큐 추가가 모두 완료된 뒤 접수 성공으로 알리고, 중간 실패 시 추가 내용을 취소하거나 미완료로 남긴다. 같은 키가 아니면서 같은 해시 위치를 갖는 충돌은 실제 키 비교로 구별한다.
처리는 큐 앞에서 번호를 꺼낸 뒤 현재 상태를 조회한다. 취소 상태면 건너뛰고 대기 상태면 작업을 수행해 완료로 바꾼다. 이 안은 번호에 대응하는 큐 노드를 별도로 색인하는 복잡성을 피하지만, 취소된 번호가 처리 차례까지 큐에 남는 공간·정리 비용을 받아들인다. 취소 지연이나 공간이 허용 범위를 넘으면 더 직접적인 삭제 구조를 다시 평가한다. 단순 FIFO를 긴급 우선순위 처리로 설명하지 않는다.
편집 취소 기록은 되돌릴 수 있는 이전 내용과 편집 순서를 스택에 둔다. 이는 화면 편집의 취소이며 이미 발송한 메시지 같은 외부 효과를 자동으로 되돌린다는 뜻이 아니다. 부서의 주된 소속은 뿌리 있는 트리로, 이동 경로는 방향·가중치 의미를 가진 그래프로 표현한다. 경로를 탐색할 때 방문 기록을 유지하고 도달 가능성과 최단거리 요구를 구별한다.
검토자는 A·B·C 접수 후 B를 취소했을 때 A·C만 실제 처리되는지, 같은 번호 재전송이 새 큐 항목을 만들지 않는지, 해시 충돌이 다른 신청을 덮어쓰지 않는지 확인한다. 빈 큐·가득 찬 큐·편집 취소의 끝·순환 경로·복합 추가의 부분 실패도 확인한다. 실제 영속성·동시성은 뒤의 트랜잭션·분산 상태 설명과 연결하며 이 작은 모형의 성공으로 대신하지 않는다.
자기교정: 구조 이름 대신 실제로 일어나는 일을 쓴다
| 부족한 답 | 빠진 조건 | 고쳐 쓸 내용 | 복습 |
|---|---|---|---|
| 배열은 무엇이든 한 번에 찾는다 | 위치 조회와 값 검색의 차이 | 인덱스 2 접근과 값 30의 위치 검색을 구별 | 배열 |
| 연결이면 중간 삽입은 언제나 같은 비용이다 | 앞 노드와 위치 탐색 | B를 이미 아는 연결 수정과 B를 찾는 비용 분리 | 연결 |
| 스택과 큐는 다른 종류의 메모리다 | 접근 규칙과 저장 방식 | 같은 배열·연결로 서로 다른 접근 규칙 구현 가능 | 순서 |
| 큐는 급한 사람을 먼저 꺼낸다 | FIFO와 우선순위 | 도착 순서 규칙과 별도 우선순위 요구를 구별 | 순서 |
| 트리면 모든 범위 검색이 빠르다 | 키 순서·균형 조건 | 일반 소속 트리와 탐색용 트리를 구별 | 관계 |
| 해시 위치가 같으면 같은 신청이다 | 실제 키 동등성 | 12와 17은 충돌해도 다른 키 | 충돌 |
| 큐에서 지우면 조회 목록에서도 사라진다 | 복합 구조의 변경 경계 | 두 구조·상태의 같은 작업을 함께 대사 | 설계 |
| 방문표는 모든 경로의 최단거리를 보장한다 | 탐색 목적·가중치 | 순환 방지와 최단거리 알고리즘을 구별 | 관계 |
조건 변경과 해설
네 값 배열의 첫 위치에 5를 넣으면? 여유 공간이 있는 동일 조건에서는 기존 네 원소를 뒤로 옮겨야 한다. 25를 가운데 넣던 예의 2회를 그대로 쓰지 않는다.
해시 예에 키 22를 실제로 추가한 뒤 조회하면? 위치 2의 같은 충돌 목록에서 12·17·22의 실제 키를 비교해 새 값을 찾는다. 같은 위치라는 이유로 자료A를 반환하지 않는다.
접수 C가 긴급해서 A보다 먼저 처리해야 한다면? 기존 FIFO 요구와 충돌한다. 우선순위·동률 순서·낮은 우선순위 작업의 대기 한계를 별도로 정하고 그 요구에 맞는 구조를 비교한다. 큐 이름만 바꾸어 해결됐다고 하지 않는다.
근거와 범위
L1. OpenDSA, Comparison of List Implementations, 배열의 위치 접근·이동과 연결 구조의 위치 탐색·수정 비용. https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/ListAnalysis.html . 2026-09-20 해당 HTML을 확인했다. 특정 운영체제·장비에서 측정한 성능으로 확대하지 않는다.
L2. Python 공식 Tutorial, Data Structures, §§5.1.1~5.1.2의 스택·큐와 앞쪽 원소 이동의 차이. https://docs.python.org/3/tutorial/datastructures.html . 2026-09-20 해당 범위를 확인했다. 본문의 A/B/C/D 예·접수 설계는 자체 작성이며 라이브러리 실행 기록이 아니다.
모든 추가 수치·작업 추적·설계·문제·답안은 자체 교육용이다. 고유 정의와 기존 앵커는 유지했으며 기계적 회귀·초보 독자 실험·독립 감수와 사람 승인은 별도다.
30초 정리
- 자료구조는 표현할 관계와 자주 할 연산의 비용에 맞춰 값과 연결을 배치한다.
- 순차구조는 앞뒤 순서, 스택·큐는 접근 순서, 트리·그래프는 계층·망, 해시는 키 조회에 초점을 둔다.
- 하나의 정답 구조는 없으며 경계값·충돌·순환·복합 구조 일관성과 최악 조건을 함께 판단한다.