자료구조

1. 개요

자료구조는 데이터를 어떤 관계와 순서로 저장하고, 어떤 방식으로 찾고 바꿀지를 정한 구조다. 좋은 자료구조는 하나로 정해져 있지 않다. 접근 속도, 삽입·삭제 비용, 저장 공간, 데이터의 관계를 함께 따져 목적에 맞게 골라야 한다. CPU와 메모리의 상호 작용, 데이터를 학습하는 기술, 장면 데이터를 화면으로 바꾸는 과정도 결국 데이터를 어떤 구조로 다루는지와 연결된다.

2. 상세

2.1. 선형과 비선형

선형 자료구조는 데이터가 앞뒤의 순서를 따라 이어지는 구조다. 배열, 연결 리스트, 스택, 큐가 여기에 속한다. 비선형 자료구조는 한 데이터가 여러 데이터와 갈래를 이루며 연결될 수 있고, 트리와 그래프가 대표적이다.¹ 선형·비선형은 단순히 화면에 그린 모양이 아니라 데이터 사이의 관계를 기준으로 한 구분이다.

2.2. 배열과 연결 리스트

배열은 데이터를 메모리의 연속된 위치에 놓는다. 시작 위치와 인덱스를 알면 원하는 원소의 위치를 바로 계산할 수 있다.² 그러나 배열 중간에 원소를 넣거나 빼면 뒤의 원소들을 옮겨야 할 수 있다.

연결 리스트는 각 원소가 다음 원소의 위치를 가리키는 포인터를 가진다. 원소가 메모리에 연속해서 놓일 필요가 없고 연결만 바꾸어 삽입·삭제할 수 있다. 대신 특정 순서의 원소를 찾으려면 앞에서부터 포인터를 따라가야 한다.³

2.3. 스택과 큐

스택은 마지막에 넣은 데이터를 먼저 꺼내는 후입선출 구조다. 방문 기록에서 직전에 본 페이지로 되돌아가는 흐름처럼, 가장 최근 상태를 먼저 복원할 때 알맞다. 큐는 먼저 넣은 데이터를 먼저 꺼내는 선입선출 구조로, 들어온 순서를 지켜 처리하는 대기열에 맞는다.⁴

2.4. 트리와 탐색 기준

트리는 하나의 노드에서 여러 자식 노드로 갈라지는 계층 구조다. 이진 탐색 트리는 각 노드를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 두는 규칙을 사용한다. 찾는 값과 현재 노드를 비교해 이동 방향을 정하므로 모든 노드를 차례로 보지 않고 탐색 범위를 줄일 수 있다.⁵ 다만 트리의 모양과 정렬 상태에 따라 실제 탐색 비용은 달라진다.

3. 수능에서는 이렇게 나온다

자료구조 문제에서는 구조의 이름보다 연산의 조건을 먼저 찾는다. ‘몇 번째 원소에 곧바로 접근’, ‘중간 삽입이 반복’, ‘최근 항목부터 복원’, ‘도착 순서대로 처리’, ‘비교하며 탐색 범위 축소’ 같은 조건을 자료구조의 성질과 연결한다.

한 장점이 커지면 다른 비용이 생길 수 있다는 점도 중요하다. 배열은 접근이 빠르지만 중간 변경 비용이 커질 수 있고, 연결 리스트는 연결 변경이 쉽지만 임의 위치 접근에는 순차 탐색이 필요하다. 선지에서 서로 다른 구조의 장점을 바꾸어 붙였는지 확인한다.

4. 헷갈리기 쉬운 것들

자료구조	핵심 관계	유리한 연산	함께 생기는 비용
배열	연속된 위치와 인덱스	임의 위치 접근	중간 삽입·삭제 시 이동 가능
연결 리스트	포인터로 다음 원소 연결	연결을 바꾸는 삽입·삭제	원하는 위치까지 순차 이동
스택	후입선출	최근 상태부터 꺼내기	먼저 들어온 항목은 아래에 남음
큐	선입선출	도착 순서대로 처리	뒤에 들어온 항목은 기다림
이진 탐색 트리	비교 결과로 좌우 분기	규칙에 따른 범위 축소	구조가 치우치면 효율이 낮아질 수 있음

5. 관련 개념

• 폰 노이만 구조 — 자료구조가 실제로 놓이는 메모리와 이를 처리하는 CPU의 관계를 설명한다.
• 인공지능·머신러닝·딥러닝 — 학습 데이터와 모델 내부 정보를 조직해 처리하는 기술이다.
• 컴퓨터 그래픽 렌더링 — 오브젝트·폴리곤·화면 픽셀 데이터를 단계별로 다룬다.

각주

1. ‘선형’은 데이터가 한 줄의 순서 관계를 이루고, ‘비선형’은 여러 갈래 관계를 허용한다는 뜻이다. ↩

2. 인덱스는 배열의 시작점에서 원소가 몇 번째 위치에 있는지를 나타낸다. ↩

3. 포인터는 다음 데이터가 놓인 메모리 주소를 담아 떨어진 원소들을 연결한다. ↩

4. 스택과 큐는 저장 모양보다 데이터를 꺼내는 순서 규칙이 핵심이다. ↩

5. 이진 탐색 트리의 좌우 배치 규칙이 유지되어야 비교를 통한 탐색 축소가 가능하다. ↩