Ruby 개발자를 위한 필수 데이터 구조 완벽 가이드

데이터 구조란 무엇일까요?

데이터 구조(Data Structure)란 데이터를 체계적으로 조직화하고 접근하는 특정한 방식을 말합니다.

대표적인 예시는 다음과 같습니다.

• 배열(Array)
• 이진 트리(Binary Tree)
• 해시(Hash)

각 데이터 구조는 저마다 잘하는 작업이 다릅니다.

예를 들어 해시는 사전(단어와 뜻)처럼 키-값 쌍으로 이루어진 데이터나 전화번호부(이름과 번호) 같은 데이터를 저장할 때 매우 유용합니다.

어떤 데이터 구조들이 존재하는지, 그리고 각 구조가 지닌 특성을 제대로 이해하면 한 단계 더 나은 Ruby 개발자가 될 수 있습니다.

바로 지금부터 그 내용을 하나씩 살펴보겠습니다!

배열(Array)의 이해

배열은 프로그래밍을 배울 때 가장 먼저 접하게 되는 데이터 구조입니다.

배열은 연속된 메모리 공간을 사용하며, 객체들이 빈틈없이 차례대로 저장됩니다.

C와 같은 저수준 언어와 달리, Ruby에서는 메모리 관리, 배열 최대 크기 확장, 요소 삭제 후 메모리 재정렬 같은 복잡한 작업을 모두 자동으로 처리해 줍니다.

활용 예:

• 더 고급스러운 데이터 구조의 기반
• 반복문 실행 결과를 모아두는 용도
• 여러 항목을 담는 컬렉션

배열은 Ruby 곳곳에서 활용되는데, 문자열을 문자 배열로 분해하는 split과 chars 메서드가 대표적입니다.

예제:

out = []

10.times { |i| out << i }

out
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

다음 표는 배열의 크기가 커질수록 각 연산의 성능이 어떻게 변하는지 보여줍니다.

시간 복잡도 표기법에 익숙하지 않다면 관련 글을 먼저 읽어보시길 권합니다.

배열의 시간 복잡도:

이 정보가 왜 도움이 될까요?

배열의 성능 특성을 미리 파악할 수 있기 때문입니다.

거대한 배열에서 find 연산을 반복적으로 수행하면 속도가 느려질 수밖에 없습니다...

반면 접근하려는 인덱스를 이미 알고 있다면, O(1)의 시간 복잡도 덕분에 매우 빠르게 처리할 수 있습니다.

데이터 구조 선택 기준:

1. 성능 특성 => 데이터로 무엇을 하려는지? 데이터셋의 크기는 어느 정도인지?
2. 데이터의 형태 => 어떤 종류의 데이터를 다루는지? 더 적합한 구조에 맞게 데이터를 재구성할 수 있는지?

해시(Hash) 데이터 구조

국가 코드와 국가 이름을 서로 매핑해야 하나요?

아니면 단순히 무언가의 개수를 세고 싶으신가요?

바로 그럴 때 해시가 빛을 발합니다!

해시는 모든 값이 키를 가지며, 이 키는 문자열, 정수, 심볼 등 무엇이든 될 수 있는 데이터 구조입니다.

동작 원리는 어떻게 될까?

해시는 키를 숫자로 변환하고(Ruby의 hash 메서드 사용), 그 숫자를 인덱스로 활용합니다. 다만 Ruby 프로그램에서 해시를 사용하기 위해 이 내부 원리까지 알 필요는 없습니다.

활용 예:

• 문자열 내 각 문자의 개수 세기
• 단어-뜻, 이름-전화번호 등의 매핑
• 배열 안에서 중복 항목 찾기

예제:

"aaabcd"
  .each_char
  .with_object(Hash.new(0)) { |ch, hash| hash[ch] += 1 }

# {"a"=>3, "b"=>1, "c"=>1, "d"=>1}

시간 복잡도:

해시는 저장, 삭제, 접근이 모두 일정한 O(1) 시간에 이루어지기 때문에 성능 면에서 가장 유용한 데이터 구조 중 하나로 꼽힙니다.

여기서 말하는 '찾기'는 특정 키가 아닌 특정 값을 찾는 경우를 의미합니다.

스택(Stack)

스택은 접시 쌓기에 비유할 수 있습니다. 접시를 한 장씩 위에 쌓고, 꺼낼 수 있는 것은 오직 맨 위의 접시뿐이죠.

처음 들었을 때보다 훨씬 실용적인 구조입니다!

활용 예:

• 재귀 메서드를 일반 반복문으로 대체
• 남은 작업 추적 (최근 작업이 항상 맨 위에 위치)
• 배열 뒤집기

예제:

stack = [1,2,3,4,5]

(1..stack.size).map { stack.pop }

# [5, 4, 3, 2, 1]

물론 reverse 메서드를 사용해도 됩니다.

여기서는 스택의 동작 특성을 보여주기 위한 예시일 뿐입니다.

시간 복잡도:

스택(그리고 큐)은 insert와 delete, 즉 push와 pop이라는 두 가지 연산만 제공한다는 점에 주목하세요.

스택 내부를 검색하는 것이 불가능한 것은 아니지만, 실제로는 매우 드문 경우입니다.

이진 트리(Binary Tree) 활용법

대부분의 Ruby 개발자는 이진 트리에 대해 들어본 적은 있지만, 실제로 사용해 본 경험은 없을 겁니다.

왜 그럴까요?

첫째, Ruby에는 내장된 이진 트리 구현체가 없습니다.

둘째, 배열과 해시처럼 매일 사용하는 구조에 비해 이진 트리는 일상적인 프로그래밍 문제에서 큰 도움이 되지 않습니다.

하지만 이진 트리는 분명 매우 흥미로운 데이터 구조입니다.

실제로 다음 섹션에서 다룰 Trie, 데이터베이스에서 사용되는 B-Tree 같은 멀티웨이 트리, 그리고 힙(Heap) 등 다양한 변형이 존재합니다.

활용 예:

• 데이터 압축
• 라우팅 테이블
• 추상 구문 트리(AST)

예제:

# https://github.com/jamesconant/bstree

require 'bstree'

root = Bstree::Node.new(5)

root.insert(2)
root.insert(7)

root.search(3)
# nil

시간 복잡도:

'균형 잡힌 이진 트리'란 모든 노드가 두 개의 자식을 가지며, 모든 리프 노드가 같은 레벨에 위치하는 경우를 말합니다.

트리가 불균형해지면 성능은 O(n)까지 저하됩니다.

자가 균형 이진 트리(레드-블랙 트리, AVL 트리 등)에서는 모든 연산이 트리의 높이(레벨)에 비례하는 시간 안에 완료됩니다.

표에 접근(access) 시간이 없다는 점도 눈여겨보세요. 노드에 접근하려면 우선 해당 노드를 찾아야 하기 때문입니다...

그런 경우 접근 시간은 O(log n)이 됩니다.

반면 특정 노드에 대한 참조를 변수로 계속 유지하고 있다면, 접근 시간은 O(1)이 됩니다.

트라이(Trie) 데이터 구조

트라이(Trie)는 트리 형태에서 특화된 데이터 구조입니다.

단어를 다룰 때 특히 유용하며, 특정 접두사로 시작하는 단어를 빠르게 검색하거나 단어 전체를 찾는 데 활용됩니다.

활용 예:

• 단어 게임
• 맞춤법 검사기
• 자동완성 추천

예제:

# https://github.com/gonzedge/rambling-trie

require 'rambling-trie'

trie = Rambling::Trie.create('words.txt')

trie.include?('chocolate')
# true
trie.include?('salmon')
# true

시간 복잡도:

위 표에서 k는 입력 문자열의 크기를 의미하며, n은 데이터 구조 자체의 크기를 나타냅니다.

예를 들어 apple이라는 단어라면 k는 5가 됩니다.

마무리

이번 글에서는 널리 사용되는 데이터 구조들과 각각의 주요 용도, 특성, 그리고 Ruby에서의 활용 방법까지 살펴보았습니다.

오늘 배운 내용을 실무에 적용하면 문제를 훨씬 더 빠르게 해결할 수 있을 것입니다!

글이 도움이 되셨다면 주변에 공유 부탁드립니다.

감사합니다 🙂