자료구조

우리는 프로그램을 작성할 때 수많은 데이터를 다룹니다. 사용자 목록, 게시글 목록, 방문 기록, 검색 결과, 캐시, 파일 경로, 친구 관계처럼 형태는 다르지만 결국 대부분의 프로그램은 데이터를 저장하고, 찾고, 바꾸고, 지우는 일을 반복합니다.

그렇다면 데이터는 어떻게 저장하고 다뤄야 할까요?

처음에는 단순히 배열이나 객체에 값을 넣는 것만으로도 충분해 보입니다. 하지만 데이터가 많아지고 찾아야 하는 조건이 복잡해지고 계속해서 추가와 삭제가 일어나기 시작하면서 문제가 발생하기 시작합니다. 같은 데이터를 다루더라도 어떤 방식으로 저장하느냐에 따라 프로그램의 속도와 복잡도는 크게 달라질 수 있습니다.

이때 필요한 것이 바로 자료구조입니다.

자료구조란

자료구조(data structure) 란 데이터를 저장하고 다루는 방법입니다.

하지만 단순히 “데이터를 담는 그릇”이라고만 이해하면 조금 부족합니다. 자료구조는 데이터를 어떤 형태로 저장할지뿐만 아니라 그 데이터를 얼마나 빠르게 찾고, 추가하고, 삭제하고, 순회할 수 있는지를 함께 결정합니다.

예를 들어 배열은 데이터를 순서대로 저장하기에 좋습니다. 인덱스를 알고 있다면 원하는 위치의 값에 바로 접근할 수 있고, 전체를 처음부터 끝까지 순회하기도 쉽습니다. 하지만 중간에 값을 자주 끼워 넣거나 삭제해야 한다면 매번 많은 값을 움직여야 할 수 있습니다.

반대로 연결 리스트는 중간 삽입과 삭제에는 유리할 수 있지만, 원하는 위치로 바로 이동하기는 어렵습니다. 이렇게 같은 데이터라도 어떤 구조를 선택하느냐에 따라 잘하는 일과 못하는 일이 달라집니다.

결국 자료구조를 배운다는 것은 데이터를 저장하고 다루는 방법을 이해함으로써 각 구조가 어떤 상황에서 유리하고 어떤 상황에 불리한지 이해하는 일이라고 볼 수 있습니다.

자료구조의 중요성

자료구조가 중요한 이유는 프로그램의 성능과 설계에 영향을 주기 때문입니다.

어떤 문제는 배열 하나로 해결할 수 있습니다. 순서대로 데이터를 모아두고 처음부터 끝까지 순회하면 됩니다. 하지만 어떤 문제는 빠른 검색이 필요합니다. 이때 매번 배열을 처음부터 끝까지 순회한다면 데이터가 많아질수록 점점 느려질 것입니다. 이런 상황에서는 해시 테이블처럼 값을 빠르게 찾을 수 있는 자료구조가 필요합니다.

또 어떤 문제는 데이터 사이의 관계가 중요합니다. 지하철 노선도, 친구 관계, 웹 페이지 링크, 파일 시스템처럼 데이터가 서로 연결되어 있다면 단순한 배열만으로는 그 관계를 자연스럽게 표현하기 어렵습니다. 이때는 트리나 그래프처럼 관계 자체를 표현할 수 있는 구조가 필요합니다.

자료구조는 이렇게 데이터를 표현하고 접근하는 방식을 다룹니다. 적합한 자료구조를 잘 선택할수록 알고리즘은 단순해지고 코드는 더욱 명확해집니다. 구현에 앞서 “이 데이터는 어떤 모습으로 표현해야 할까?” 고민하고 적절한 구조를 선택함으로써 더욱 빠르고 안정적인 프로그램을 만들 수 있습니다.

자료구조의 종류

자료구조는 여러 방식으로 나눌 수 있지만, 처음 공부할 때는 데이터가 어떤 모양으로 놓이는지를 기준으로 보는 것이 이해하기 쉽습니다.

선형 자료구조

가장 먼저 알아볼 것은 데이터가 한 줄로 이어지는 선형 자료구조입니다. 배열, 연결 리스트, 스택, 큐가 여기에 속합니다.

배열은 데이터를 연속된 공간에 순서대로 저장합니다. 연결 리스트는 각 데이터가 다음 데이터를 가리키는 방식으로 이어집니다. 스택은 마지막에 넣은 데이터를 먼저 꺼내는 구조이고, 큐는 먼저 넣은 데이터를 먼저 꺼내는 구조입니다.

이 구조들은 단순해 보이지만 이후 여러 자료구조와 알고리즘을 이해하는 데 계속 등장합니다. 연결 리스트는 그래프를 인접 리스트 형태로 표현하거나 해시 테이블의 충돌을 처리하는 방식에서 다시 등장합니다. 스택은 깊이 우선 탐색(DFS)과 연결되고, 큐는 너비 우선 탐색(BFS)과 연결됩니다. 그래서 선형 자료구조는 자료구조 학습의 출발점이 됩니다.

비선형 자료구조

다음으로 알아볼 것은 데이터가 한 줄로만 이어지지 않는 비선형 자료구조입니다. 트리와 그래프가 대표적이며, 힙처럼 트리 형태를 활용하거나 해시 테이블처럼 빠른 탐색을 위해 별도의 저장 방식을 사용하는 구조도 함께 살펴볼 수 있습니다.

트리는 데이터를 계층적으로 표현할 때 사용됩니다. 힙은 가장 크거나 작은 값을 빠르게 꺼내야 할 때 유용합니다. 그래프는 데이터 사이의 연결 관계를 표현할 때 사용됩니다. 해시 테이블은 키를 이용해 원하는 값을 빠르게 찾을 때 사용됩니다.

이 구조들을 배우기 시작하면 자료구조를 단순히 값을 저장하는 방법을 넘어, 문제를 어떤 형태로 바라볼 것인지 이해할 수 있게 됩니다. 데이터에 계층이 필요한지, 서로 연결이 필요한지, 혹은 빠르게 찾아야 하는지 등 목적에 따라 적합한 자료구조를 사용할 수 있습니다.

추천 학습 방법

자료구조 학습은 단순히 이름과 구조를 외우는 방법만으로 부족할 수 있습니다. 배열, 스택, 큐, 트리, 그래프라는 이름과 구조는 기억나지만 막상 문제를 만나면 어떤 것을 써야 할지 떠오르지 않을 수 있습니다.

그래서 각 자료구조를 학습할 때마다 다음 질문을 함께 던지는 것이 좋습니다.

• 어떤 데이터를 표현하기 위한 구조인가
• 삽입, 삭제, 탐색, 순회는 얼마나 빠른가
• 어떤 상황에서 적합한가
• 어떤 상황에서는 오히려 불리한가
• 실제 문제에서는 어떤 알고리즘과 함께 쓰이는가

예를 들어 스택을 배울 때는 “마지막에 넣은 것을 먼저 꺼낸다”는 정의에서 멈추기보다, 왜 괄호 검사나 함수 호출, DFS 같은 문제와 잘 맞는지까지 연관지어 학습하는 것이 좋습니다. 큐도 마찬가지입니다. “먼저 넣은 것을 먼저 꺼낸다”는 특징이 왜 BFS나 작업 대기열과 자연스럽게 연결되는지 함께 이해해야 합니다.

자료구조를 보다 잘 이해하고 기억하기 위해서는 결국 각 구조의 모양과 연산, 그리고 그것이 어울리는 문제 상황을 함께 기억하는 것이 중요합니다.

추천 학습 순서

처음에는 배열과 문자열에서 시작하는 것이 좋습니다. 대부분의 데이터 처리 문제는 배열과 문자열을 다루는 영역에서 출발하기 때문입니다. 인덱스, 순회, 슬라이딩 윈도우, 투 포인터 같은 기초적인 알고리즘도 이 단계에서 함께 익힐 수 있습니다.

그 다음에는 연결 리스트를 통해 데이터가 반드시 연속된 공간에 놓일 필요는 없다는 것을 이해합니다. 이어서 스택과 큐를 배우면 데이터가 들어오고 나가는 순서가 알고리즘의 흐름을 어떻게 바꾸는지 이해할 수 있습니다.

그 이후에는 해시 테이블을 통해 빠른 탐색의 방법을 익히고, 트리와 힙을 통해 계층 구조와 우선순위 관리 방식을 배웁니다. 마지막으로 그래프를 공부하면 데이터 사이의 관계를 직접 모델링하는 단계로 넘어갈 수 있습니다.

정리하면 대략 다음 순서가 자연스럽습니다.

1. 배열과 문자열
2. 연결 리스트
3. 스택과 큐
4. 해시 테이블
5. 트리
6. 힙과 우선순위 큐
7. 그래프

물론 이 순서가 절대적인 것은 아닙니다. 하지만 앞의 구조가 뒤의 구조를 이해하는 데 자주 사용되기 때문에 처음 공부할 때는 이 흐름을 따라가는 편이 좋습니다.

결국 자료구조는 선택의 문제다

자료구조를 공부하는 이유는 단순히 여러 구조를 외우기 위해서가 아닙니다. 문제를 만났을 때 데이터에 어떤 연산이 자주 일어나는지 그리고 어떤 제약이 중요한지 보고 그에 맞는 구조를 선택하기 위해서입니다.

어떤 문제는 배열처럼 단순한 구조가 가장 좋은 선택이 될 수 있습니다. 어떤 문제는 해시 테이블을 이용하여 빠른 탐색이 필요할 수 있습니다. 또 어떤 문제에서는 그래프를 이용하여 관계를 보다 명확하게 표현해야 할 수 있습니다.

결국 적절한 자료구조를 선택하는 것이 좋은 알고리즘으로 이어질 수 있습니다. 나아가 자료구조를 이해함으로써 문제 속 데이터를 보다 정확한 모양으로 표현하고 바라볼 수 있습니다.