들어가며

이전에 작성한 1~5장에 대한 내용(이전 글 보러가기) 이후 6장부터 9장까지의 내용을 읽고, 학습한 추가 내용을 공유하고자 글을 작성하게 되었습니다.

 

정렬 알고리즘

이제 정렬 알고리즘 내용을 정리하고 다음 내용으로 넘어갈텐데요.

해시 테이블이라는 자료 구조입니다.

 

해시 테이블이란?

이 책에서는 대부분의 프로그래밍 언어가 해시 테이블을 기본 제공하며,  
평균적으로 O(1)의 효율성을 가진 자료구조라고 설명합니다.

조금 더 풀어보면, 해시 테이블은 키(key)를 통해 값(value)에 빠르게 접근할 수 있도록 도와주는 구조입니다.

즉, 어떤 데이터를 저장할 때 고유한 ‘키’를 지정하고, 나중에 다시 찾을 때도 같은 ‘키’를 이용해 직접 값을 꺼낼 수 있다는 점이 핵심입니다.

자바스크립트의 객체({})나 Map,  파이썬의 dict, 자바의 HashMap 등  
언어에 따라 다양한 이름(맵, 딕셔너리, 연관 배열 등)으로 불리지만,  기본 원리는 모두 동일합니다.

해싱과 해시 함수

그렇다면 컴퓨터는 이 "키"를 어떻게 배열의 인덱스로 바꿔서 저장할까요?

여기서 등장하는 개념이 바로 해싱(Hashing)과 해시 함수(Hash Function)입니다.

해싱은 키(문자)를 숫자로 바꾸는 과정이고,  해시 함수는 그 숫자를 계산하는 규칙입니다.

예를 들어 "ABC"이라는 문자를 저장한다고 할 때,  
해시 함수는 "A"는 1, "B"은 2, "C"은 3으로 매핑해서 더합니다.

A = 1
B = 2
C = 3
D = 4
E = 5
F = 7
...

"ABC" = 1 + 2 + 3 = 6

이 숫자 6을 배열의 인덱스로 사용해  6번 위치에 "ABC"이라는 키와 관련된 값을 저장하는 거죠.

이렇게 문자 키를 숫자로 변환해서 배열처럼 빠르게 접근할 수 있게 만드는 것이 해시 테이블의 핵심 원리입니다.

중요한 건 "ABC"을 해싱할 때마다 항상 같은 숫자가 나와야 한다는 것!  
그래야 "ABC"이라는 키로 언제든 같은 위치에서 값을 정확하게 찾아올 수 있습니다.
이렇게 키를 숫자로 바꾸는 덕분에, 복잡한 데이터도 빠르게 저장하고 꺼낼 수 있다고 합니다.

해시 충돌이란?

하지만 해시 테이블에도 문제가 하나 있습니다.  
바로 해시 충돌(collision)입니다.

예를 들어 "BAD"라는 키가 숫자 8로 해싱되어 8번 위치에 저장됐다고 해볼게요. (위 예시의 각 문자에 할당된 숫자를 더한 값을 계산하면 8이거든요.)
그런데 "DAB"이라는 키도 우연히 같은 숫자 8이 나오면?  
이미 그 자리에 "BAD"가 들어 있으므로, 두 키가 같은 칸을 공유하게 됩니다.  
이걸 해시 충돌이라고 부릅니다.

해시 충돌을 해결하는 대표적인 방법 중 하나가 바로 분리 연결법 (Separate Chaining)입니다.  
한 칸에 하나의 값만 넣는 대신, 배열 형태로 여러 값을 함께 저장하는 방식이죠.

인덱스	키	값
8	bad	evil
	dab	pat

"DAB"이라는 키를 찾을 때 컴퓨터는 셀 8번에 있는 여러 쌍을 차례대로 확인하며 일치하는 키를 찾아 값을 꺼냅니다.

다만, 이 방식은 비효율적일 수 있습니다.  
충돌이 자주 발생해 하나의 셀에 값이 몰리면, 결국 순차 검색을 하게 되어 성능이 O(N)으로 떨어질 수 있기 때문입니다.

책에서는 “효율적인 해시 테이블은 많은 메모리를 낭비하지 않으면서, 충돌을 피하고 균형을 유지해야 한다.”라고 하고 있는데요. 

이러한 균형을 측정하는 중요한 개념이 바로 부하율(load factor)입니다.

부하율 (Load Factor)

부하율 = 저장된 데이터 수 ÷ 해시 테이블의 전체 셀 수

예를 들어 데이터를 7개 저장하고,  
해시 테이블 셀이 10개라면 부하율은 7 ÷ 10 = 0.7입니다.

셀 번호	0	1	2	3	4	5	6	7	8	9	10
내용	●	●		●		●	●	●		●

* ● = 데이터 저장됨 / 빈 칸 = 아직 사용되지 않음

책에서는 부하율 0.7를 이상적인 기준으로 보고 있습니다.  
이 값보다 높아지면 충돌이 자주 발생하고, 너무 낮으면 메모리를 낭비하게 된다고 합니다.

그래서 해시 테이블은 일반적으로 다음과 같은 조건을 만족해야 효율적인 성능을 유지할 수 있다고 생각하여 정리하였습니다.

• 좋은 해시 함수를 사용해서 충돌을 줄이고
• 해시 테이블 크기를 적절히 유지하며
• 부하율이 0.7 근처를 유지하도록 설계

다음은 스택과 큐에 대한 내용입니다.

스택과 큐

자료구조에서 자주 등장하는 두 가지 기본 구조가 있습니다.  
바로 스택(Stack)과 큐(Queue)입니다.  
이 둘은 데이터를 넣고 꺼내는 순서(=선입선출/후입선출)가 다르다는 점에서 구분됩니다.

스택(Stack)

스택은 “나중에 넣은 것이 가장 먼저 나오는” 구조입니다.

• 영어로는 LIFO (Last In, First Out)
• 가장 마지막에 들어간 데이터가 가장 먼저 나옴
• 스택의 끝에만 데이터 삽입 가능
• 스택의 끝에서만 데이터 삭제 가능
• 스택의 마지막 원소만 읽기 가능

예를 들어, [A, B, C] 라는 스택이 있다면, C를 먼저 꺼내고 → 그 다음 B → 마지막으로 A 순서로 꺼냅니다.

스택은 왜 필요할까요? 어차피 배열로도 위에서부터 데이터를 꺼낼 수 있는데, 굳이? 라고 생각할 수도 있는데요.
사실 스택은 배열에 기능적 제약을 더한 자료구조입니다.  
하지만 바로 그 제약이 중요합니다.

1. 잠재적인 버그 방지
   

   스택은 오직 맨 위(push/pop)에서만 데이터를 다룰 수 있습니다.
   즉, 중간이나 앞쪽의 데이터를 임의로 삭제하거나 삽입할 수 없습니다.

   예를 들어 린팅(linting) 알고리즘에서 문법 오류 추적을 위해 스택을 사용하는 경우, 스택의 맨 위 항목만 제거하는 방식으로 설계됩니다. 누군가가 중간 값을 삭제하게 되면 알고리즘은 깨집니다.
   스택을 사용하면 이러한 실수를 아예 구조적으로 막을 수 있다고 하니 알아두시면 좋겠죠?

2. 명확한 사고 모델(Mental Model)
   

   스택은 후입선출(LIFO)이라는 사고 흐름을 기반으로 동작합니다.
   즉, 마지막에 들어온 데이터를 가장 먼저 처리한다는 규칙이 문제 해결 방법을 더 명확하게 정의해주는 역할을 합니다.
   이 사고 모델(멘탈모델 스터디...아련...)을 이해하고 쓰는 코드는 다른 개발자에게도 익숙하고 명쾌하게 읽히는 장점이 있다고 합니다. 코드 안에 스택이 쓰였다면, 해당 로직이 LIFO 기반 프로세스라는 걸 바로 알 수 있으니까요.

3. 되돌리기(Undo) 기능 같은 실제 사례
   

   스택은 일상 속 많은 기능에도 활용됩니다.  
   대표적인 예가 워드 프로세서의 되돌리기(Undo)기능입니다.

   사용자가 입력한 키스트로크를 하나씩 스택에 push() 해두고,  
   되돌리기 키를 누르면 가장 최근의 키스트로크부터 하나씩 pop() 하여 제거합니다.

   이처럼 "최근 것부터 거꾸로 되돌리는" 흐름에 딱 맞는 구조가 바로 스택입니다.

   const stack = [];
   
   // 값 추가 (push)
   stack.push("A");
   stack.push("B");
   stack.push("C");
   
   // 값 제거 (pop)
   console.log(stack.pop()); // "C"
   console.log(stack.pop()); // "B"
   console.log(stack.pop()); // "A"

 

큐(Queue)

큐는 “먼저 넣은 것이 먼저 나오는” 구조입니다.  

• 영어로는 FIFO (First In, First Out)
• 가장 먼저 들어간 데이터가 가장 먼저 나옴
• 큐의 끝에만 데이터 삽입 가능(스택과 동일)
• 큐의 앞에서만 데이터 삭제 가능(스택과 정반대)
• 큐의 앞에 있는 원소만 읽기 가능(스택과 정반대)

예를 들어, [A, B, C]라는 큐가 있다면 A → B → C 순서로 꺼냅니다.

큐도 스택과 마찬가지로 기능적으로 제약된 배열 형태입니다.  
하지만 그 제약이 주는 장점은 분명한 것 같아요.

1. 제약은 구조를 보호합니다.
   

   큐는 앞(front)에서만 꺼내고, 뒤(rear)에서만 추가할 수 있습니다.  
   데이터를 중간에서 빼거나, 앞에 새로 추가하는 등의 동작은 허용되지 않습니다.

   예를 들어 서버에서 처리해야 할 요청들을 큐에 넣고 순서대로 꺼내 처리한다고 할 때,  
   누군가 큐 앞에서 무작위로 항목을 제거하면 전체 요청 순서가 꼬이게 됩니다.
   큐를 사용하면 이런 의도하지 않은 조작을 방지할 수 있겠죠?

2. 명확한 순서 기반 사고 제공
   

   큐는 선입선출(FIFO) 방식이라는 정확한 흐름 기반 모델을 제공합니다.  
   앞에서 들어온 데이터부터 순서대로 처리하는 이 구조는 작업 대기열, 네트워크 요청, 메시지 처리 등에서 매우 직관적으로 작동합니다.
   코드를 보는 사람도 "아, 이건 순서대로 처리되는 구조구나"라는 걸 큐라는 자료구조만 보고 바로 이해할 수 있습니다.

3. 실제 사례: 작업 대기열
   

   예를 들어, 브라우저가 백그라운드에서 여러 리소스를 로딩하고 있다면,
   각 로딩 요청은 큐에 저장되며, 네트워크가 가능한 시점마다 앞에서부터 하나씩 꺼내 처리됩니다.

   이처럼 “선입선출”이 중요한 시나리오에서 큐는 가장 자연스럽고 안정적인 구조입니다.

   const queue = [];
   
   // 값 추가 (enqueue)
   queue.push("A");
   queue.push("B");
   queue.push("C");
   
   // 값 제거 (dequeue)
   console.log(queue.shift()); // "A"
   console.log(queue.shift()); // "B"
   console.log(queue.shift()); // "C"

큐는 단순한 배열 조작처럼 보여도,  
그 제약 덕분에 예측 가능한 흐름, 구조적 안정성, 직관적인 문제 해결 방식을 제공합니다.

 

스택 vs 큐 한눈에 비교

특징	스택(Stack)	큐(Queue)
동작 원리	후입선출 (LIFO)	선입선출 (FIFO)
추가 방식	push()	push()
제거 방식	pop()	shift()
사용 예시	되돌리기, 브라우저 방문 기록	작업 대기열, 메시지 큐

스택과 큐, 이 둘은 정말 단순한 구조이지만, 많은 알고리즘 문제나 시스템 구조에서 예상보다 자주 사용되는 핵심 개념입니다.  
실제로 다양한 문제 해결에서 이 두 자료 구조를 어떻게 사용하는지가 성능에 큰 영향을 주기도 하니 알아두시면 좋을 것 같네요.

 

참고 문서

누구나 자료 구조와 알고리즘 - 제이 웬그로우 저/심지현 역

 

마치며

이번 글에서는 정렬 알고리즘 중 삽입 정렬,  효율적인 자료 접근을 위한 해시 테이블,  
그리고 자료 흐름의 방향성을 다루는 스택과 큐까지 함께 정리해보았습니다.

기능은 단순하지만 제약이 있는 구조가 왜 중요한지,  
그리고 그것이 문제를 바라보는 사고의 틀을 바꿔준다는 점이 인상 깊었고,
이해한 만큼 직접 구현해보며 몸에 익히는 과정이 중요하다는 생각이 들었습니다.

글은 여기까지이며, 혹시 수정할 내용이 있다면 언제든 알려주세요.
다음 글에서는 재귀(recursion)에 대해 다뤄볼 예정입니다.  
읽어주셔서 감사합니다. 🙇🏻‍♀️  
그럼 안녕히…👋 -The End-