배열, 스택, 정렬, 해싱까지 데이터 입출력 구현의 기초 정리

Table of Content

소프트웨어를 개발한다고 하면 보통 기능 구현이나 화면, API 같은 것부터 떠올리기 쉽다.
그런데 실제로 프로그램이 데이터를 어떻게 저장하고, 어떻게 정렬하고, 어떻게 찾아내는지를 먼저 이해하지 않으면 전체 성능과 구조가 금방 흔들리게 된다.

이번 글에서는 데이터 입/출력 구현 내용을 바탕으로, 자료 구조의 기본 분류부터 정렬 알고리즘, 검색 알고리즘과 해싱까지 데이터 처리의 핵심 흐름을 한 번에 정리해보려 한다.

주제	세부 핵심 내용
자료 구조	선형 구조, 비선형 구조, 트리와 그래프
정렬 알고리즘	삽입, 선택, 버블, 퀵, 힙, 합병 정렬
검색 알고리즘	이분 검색, 해싱, 충돌 해결 방법

🧱 자료 구조는 왜 소프트웨어 효율성의 출발점일까

이 장에서는 소프트웨어가 실제로 데이터를 다루는 기법들에 대해 배운다.
결국 소프트웨어의 효율성은 코드 몇 줄을 줄이는 데서만 나오지 않는다.
자료 구조의 효율성, 알고리즘의 효율성, 탐색 방법의 효율성이 모두 합쳐져서 전체 프로그램의 효율성이 만들어진다.

어떤 데이터를 어떤 구조에 담을 것인가는
단순한 구현 취향의 문제가 아니라,
이후의 삽입, 삭제, 탐색, 정렬 비용을 통째로 바꿔버리는 선택이다.

선형 구조

선형 구조는 데이터를 한 줄로 이어진 흐름처럼 다루는 방식이다.
구조가 단순하고 직관적이라 가장 먼저 접하게 되는 경우가 많다.

구조	핵심 특징
배열(Array)	동일한 자료형의 데이터를 동일한 크기로 연속 저장
연속 리스트(Contiguous List)	배열 기반 리스트, 수정·탐색은 좋지만 삽입·삭제는 불리
연결 리스트(Linked List)	포인터 기반 리스트, 삽입·삭제는 좋지만 수정·탐색은 불리
스택(Stack)	LIFO, 가장 나중에 들어온 데이터가 먼저 나감
큐(Queue)	FIFO, 가장 먼저 들어온 데이터가 먼저 나감
데크(Deque)	양쪽 끝에서 삽입/삭제가 모두 가능한 큐 구조

배열과 리스트는 비슷해 보여도 사용하는 관점이 조금 다르다.
배열은 연속된 메모리 공간을 기반으로 빠르게 접근하는 데 강하고, 연결 리스트는 중간 삽입/삭제를 더 유연하게 처리하는 데 강하다.

특히 스택과 큐는 이후 알고리즘 문제를 풀다 보면 정말 자주 다시 만나게 된다.

• 스택(Stack)은 LIFO(Last In First Out) 구조다.

  • 가장 위를 가리키는 TOP 포인터가 필요하다.
  • 정해진 크기를 초과하면 Overflow
  • 더 꺼낼 것이 없는데 꺼내려 하면 Underflow

• 큐(Queue)는 FIFO(First In First Out) 구조다.

  • Front, Rear 두 포인터가 필요하다.
  • 스케줄링, 순차 처리 같은 문제에 자주 쓰인다.

• 데크(Deque)는 큐를 양방향으로 확장한 구조라고 보면 편하다.

  • 양쪽 삽입/삭제가 모두 가능해서 생각보다 활용 범위가 넓다.

비선형 구조

비선형 구조는 데이터를 단순히 한 줄로만 보지 않고, 분기와 연결 관계를 포함한 구조로 다룬다.

대표적으로는 트리(Tree)와 그래프(Graph)가 있다.

트리(Tree)

트리는 정점(Node)과 가지(Branch)를 이용한, 사이클이 존재하지 않는 그래프 구조다.
부모-자식 관계를 가지는 계층 구조를 표현하는 데 매우 잘 맞는다.

트리에서는 순회 방식도 중요하다.

1. Preorder 순회: 부모 → 자식1 → 자식2
2. Inorder 순회: 자식1 → 부모 → 자식2
3. Postorder 순회: 자식1 → 자식2 → 부모

이 순회 방식은 수식 표현과도 연결된다.

표기법	의미
전위(Prefix)	연산자 → 원소1 → 원소2
중위(Infix)	원소1 → 연산자 → 원소2
후위(Postfix)	원소1 → 원소2 → 연산자

기본적으로 우리가 익숙한 수식은 중위 표기법이다.
반면 전위나 후위 표기법은 수식 전체를 트리로 그려보면 훨씬 이해가 쉽다.

그래프(Graph)

그래프는 정점 V(Vertex)와 간선 E(Edge)로 이루어진 자료 구조다.
트리보다 더 일반적인 구조로, 사이클이 존재할 수도 있다는 점이 차이점이다.

그래프는 여러 방식으로 표현할 수 있지만,
입문 단계에서는 인접 행렬을 이용한 표현을 자주 보게 된다.
정점 간 연결 여부를 행렬로 나타내기 때문에 구조를 한눈에 보기 좋다.

---

🔄 정렬 알고리즘은 데이터를 어떻게 다루게 만들까

자료 구조를 다룬다는 것은 결국 데이터를 잘 저장하는 것에서 끝나지 않는다.
필요한 순간 빠르게 찾기 위해서는 정렬과 탐색이 함께 따라와야 한다.

정렬 알고리즘은 데이터를 일정한 기준으로 재배열하는 방식이다.
같은 정렬이라도 어떤 방식으로 자리를 바꾸는지에 따라 성격이 꽤 달라진다.

기본 정렬 알고리즘

1. 삽입 정렬(Insertion Sort)

   • 이미 어느 정도 정렬된 흐름 속에 새 원소를 하나씩 끼워 넣는 방식이다.
   • 이름 그대로 “제자리에 삽입”하는 느낌이 강하다.

2. 쉘 정렬(Shell Sort)

   • 삽입 정렬을 부분적으로 먼저 수행하는 방식이다.
   • 일정 간격으로 나눠 정렬한 뒤 점점 간격을 줄여간다.

3. 선택 정렬(Selection Sort)

   • 최솟값을 하나씩 찾아 맨 앞에 두는 방식이다.
   • 아이디어는 직관적이지만 큰 데이터에서는 느려지기 쉽다.

4. 버블 정렬(Bubble Sort)

   • 인접한 값들을 비교하면서 큰 값이 뒤로 계속 밀려나는 방식이다.
   • 구현은 단순하지만 효율은 좋지 않은 편이다.

이 네 가지는 정렬 알고리즘의 감각을 익히기에는 좋지만,
실무나 성능 중심 관점에서는 보통 더 효율적인 정렬을 보게 된다.

성능상 더 자주 언급되는 정렬

5. 퀵 정렬(Quick Sort)

   • 기준값(pivot)을 잡고 그보다 작은 값과 큰 값을 나눠가며 정렬한다.
   • 분할 정복의 대표적인 예시다.

6. 힙 정렬(Heap Sort)

   • 힙 구조를 이용해 최댓값이나 최솟값을 빠르게 꺼내면서 정렬한다.
   • 우선순위 큐와도 자연스럽게 연결된다.

7. 합병 정렬(Merge Sort)

   • 전체를 잘게 나눈 뒤, 부분 정렬된 결과를 다시 합쳐 나가는 방식이다.
   • 퀵 정렬이 기준값을 중심으로 나눈다면, 합병 정렬은 나누고 다시 합친다는 점이 핵심이다.

정렬 알고리즘은 단순히 “오름차순 만들기” 기술이 아니라,
이후 탐색과 처리의 효율을 끌어올리기 위한 사전 작업에 더 가깝다.

같은 데이터를 다뤄도 정렬이 되어 있느냐 아니냐에 따라
다음 단계의 탐색 속도는 완전히 달라진다.

---

🔎 검색 알고리즘은 원하는 데이터를 어떻게 빠르게 찾을까

데이터를 저장하고 정렬했다면, 그다음은 결국 찾는 문제다.
검색 알고리즘은 원하는 레코드를 얼마나 빠르게 찾을 수 있는지를 다룬다.

이분 검색(Binary Search)

가장 대표적인 검색 방식 중 하나는 이분 검색(Binary Search)이다.

핵심은 단순하다.

1. 중간 레코드의 키 값을 본다.
2. 찾는 값과 비교한다.
3. 더 작은 쪽인지 큰 쪽인지에 따라 탐색 범위를 절반으로 줄인다.

단, 이 방식은 전제가 있다.

• 데이터가 정렬되어 있어야 한다

즉, 이분 검색은 강력하지만 아무 데이터에나 바로 쓸 수 있는 건 아니다.
정렬이 전제되어 있다는 점에서, 앞서 본 정렬 알고리즘과 자연스럽게 연결된다.

해싱(Hashing)

해싱은 이분 검색과는 조금 다른 방향의 검색 방식이다.
정렬된 순서를 따라가는 대신, 키를 바로 주소로 바꿔서 접근하려는 방식에 가깝다.

해싱은 별도의 해시 테이블(Hash Table) 공간을 두고,
해시 함수(Hash Function)를 이용해 레코드의 키를 주소에 매핑한다.

즉, “이 데이터는 어디에 있을까?”를 비교로 찾는 것이 아니라,
“이 키면 여기쯤 있어야 한다”는 식으로 바로 접근하는 것이다.

해싱 관련 용어

용어	의미
버킷(Bucket)	동일한 주소를 가지는 해시 테이블 내 공간
슬롯(Slot)	하나의 레코드가 저장되는 공간
충돌(Collision)	서로 다른 키가 같은 주소로 매핑되는 현상
Synonym	충돌이 발생한 레코드들
Overflow	해당 버킷에 남은 슬롯이 없어 저장이 안 되는 경우

특히 충돌은 해싱에서 피하기 어려운 문제다.
해시 함수가 아무리 좋아도 서로 다른 키가 같은 주소를 가질 가능성은 남아 있기 때문이다.

해싱 함수 종류

소스에서 정리된 해싱 함수는 다음과 같다.

1. 제산법(Division)

   • 소수로 나눈 나머지를 이용하는 방식

2. 제곱법(Mid-Square)

   • 제곱해서 나온 숫자의 일부를 이용하는 방식

3. 폴딩법(Folding)

   • 키를 여러 부분으로 나눈 뒤 조합하는 방식

4. 기수 변환법(Radix)

   • 진수 변환을 이용하는 방식

5. 대수적 코딩법(Algebraic Coding)

   • 다항식 계산을 이용하는 방식

6. 숫자 분석법(Digit Analysis)

   • 키 숫자들의 특정 자리 패턴을 분석하는 방식

7. 무작위법(Random)

   • 무작위적인 매핑 아이디어를 활용하는 방식

이름은 다양하지만, 핵심은 같다.
키를 가능한 한 고르게 분산시키는 것이다.

충돌 해결 방법

충돌이 발생했을 때는 이를 처리하는 전략이 필요하다.

1. 체이닝(Chaining)

   • 같은 버킷에 들어온 데이터를 연결 리스트로 이어서 관리하는 방식

2. 개방 주소법(Open Addressing)

   • 비어 있는 다른 주소를 자동으로 찾아가는 방식

3. 재해싱(Rehashing)

   • 새로운 해시 함수를 다시 적용하는 방식

해싱은 빠르게 접근할 수 있다는 점이 굉장히 매력적이지만,
그만큼 충돌 처리 전략이 함께 설계되지 않으면 오히려 비효율적이 될 수도 있다.

해싱은 결국
“정렬하고 비교해서 찾기” 대신
“키를 주소로 바꿔서 최대한 바로 찾아가기” 위한 방식이다.

---

데이터 입/출력 구현은 이름만 보면 단순히 파일을 읽고 쓰는 기술처럼 보일 수도 있다.
하지만 실제로는 그보다 훨씬 넓은 범위를 다룬다.
데이터를 어떤 구조에 담을지, 어떤 방식으로 정렬할지, 그리고 얼마나 빠르게 검색할지를 함께 고민하는 영역에 가깝다.

자료 구조는 소프트웨어의 뼈대가 되고,
정렬은 그 데이터를 다루기 쉬운 상태로 만들고,
검색은 결국 필요한 값을 빠르게 찾아내는 마지막 단계가 된다.

그래서 이 단원을 보고 나면,
좋은 소프트웨어는 단순히 기능이 많은 프로그램이 아니라
데이터를 얼마나 합리적인 구조로 담고 움직이게 하느냐에서부터 달라진다는 점을 다시 느끼게 된다.