재밌고 쓸모 있는, 조금은 엉뚱한 Data Structure 이야기
프로그래밍 조금 해봤다는 사람이라면 array, linked list, hash table, stack, queue, graph, tree… 이 일곱 친구들 모를 수가 없죠. 전공 수업 첫 주에 늘 나오는 애들이기도 하고요. 데이터를 저장하고, 불러오고, 바꾸고, 지우고… 그야말로 프로그래밍의 살림살이를 책임지는 녀석들이에요.
근데 이름만 들어도 머릿속에 그림이 그려지지 않나요? array는 번호 붙은 서랍장이 줄줄이 늘어선 느낌, linked list는 뭔가 다음 힌트를 따라가야 하는 보물찾기 같고요. hash table은 내 이름 딱 박힌 개인 사물함, stack은 책 위에 책 쌓는 거고, queue는 점심시간 학교 급식 줄… graph는 거미줄 같고, tree는 말 그대로 나무 모양이죠.
이렇게 익숙한 구조들이지만, 세상일이 다 그렇게 쉽지 않잖아요. 어떤 문제는 이 기본 친구들만으로는 해결이 안 되기도 해요. 그래서 오늘은 조금 더 기발하고 엉뚱하지만, 정말 유용한 data structure들을 소개해볼까 해요. 어려운 말 없이, 친구한테 설명하듯 편하게요!
B-Tree: 알고리즘이 갑자기 빨라져서 소름 돋았던 날
- Binary search tree는 속도를 빠르게 해주지만, 자식 노드가 두 개뿐이라 깊이가 커지고 성능이 저하될 수 있다.
- B-tree는 한 노드가 여러 자식을 가질 수 있어 트리 깊이를 줄이고 검색 속도를 향상시킨다.
- 데이터베이스나 파일 시스템처럼 대용량 데이터를 다루는 데에 특히 유리하다.
처음 binary search tree 만들었을 때 아직도 생생해요. "어? 진짜 이렇게 하면 빨라지네?" 하고 신기해서 혼자 들떴던 기억이 있거든요. 그 전엔 똑같은 데이터 처리하는 데 시간이 너무 오래 걸렸는데, 이거 쓰니까 확 줄어드는 거 있죠.
근데 이 구조도 완벽하진 않아요. 노드가 딱 두 개 자식만 가지니까, 데이터가 많아질수록 트리가 길쭉해지고 느려지거든요. 요즘처럼 데이터가 산더미처럼 쌓이는 시대엔 조금 버겁죠.
그래서 등장한 게 바로 B-tree! 얘는 한 노드가 여러 자식을 가질 수 있어요. 그러니까 트리가 옆으로 퍼지니까 깊이가 줄고, 검색도 훨씬 빨라지는 거죠. 특히 파일 시스템이나 데이터베이스 쪽에서 정말 자주 써요. 저도 이거 공부하면서 "와, 이거 만든 사람 진짜 천재다" 감탄했어요.
Radix Tree: 인터넷이 빠른 이유, 사실 이런 거 덕분이에요
- 접두어가 같은 데이터를 하나로 묶어 트리 깊이를 줄이고 빠르게 검색할 수 있다.
- IP 주소나 도메인처럼 비슷한 시작점을 가진 데이터에서 매우 효율적이다.
- 복잡하고 다양한 문자열에는 잘 어울리지 않는다.
IP 주소가 몇 개냐고요? 진짜 말도 안 되게 많아요. 근데도 컴퓨터는 몇 초도 안 돼서 원하는 주소를 찾잖아요. 신기하지 않나요?
이때 쓰는 게 radix tree라는 구조인데요, 쉽게 말하면 비슷한 시작을 가진 데이터들을 한 줄로 묶어주는 거예요. 예를 들어, 'C'로 시작하는 단어들을 따로 나누지 않고 하나로 쭉 이어버리는 식이죠.
그래서 접두어가 비슷한 애들이 많을수록 훨씬 효율적이에요. 물론, 아주 복잡한 문자열이나 뒤죽박죽인 데이터엔 잘 안 맞지만요. 코드 엉켜서 IDE에서 디버깅할 때처럼요... 아시죠, 그 혼란한 화면.
Rope: 에디터가 무거운 파일도 가뿐하게 여는 비결
- 긴 문자열을 여러 조각으로 나눠 트리처럼 연결한 구조다.
- 문서의 일부분만 수정해도 전체를 다시 건드리지 않아도 되기 때문에 속도가 빠르다.
- 대형 텍스트 파일을 다루는 에디터에서 유용하게 쓰인다.
한 번쯤은 텍스트 에디터로 긴 문서 열다가 버벅이는 거 느껴보셨을 거예요. 저도 그랬어요. 회사 문서 정리하다가 2만 줄 짜리 로그 파일 열었는데, 에디터가 숨 막히더라고요.
그럴 때 Rope라는 구조가 아주 큰 힘이 돼요. 긴 문자열을 조각조각 나눠서, 트리처럼 이어붙이는 거예요. 각 조각은 어디서 시작되고 얼마나 긴지 정보도 가지고 있어서, 중간에 뭔가 삽입하거나 삭제할 때 전체를 다시 건드릴 필요가 없어요.
그래서 오래된 에디터들이나, 진짜 무거운 문서 편집 도구들이 이 구조를 많이 씁니다. 은근히 똑똑하고 실용적이에요.
Bloom Filter: "그건 없어요"를 초고속으로 알려주는 녀석
- 특정 데이터가 '절대 없음'을 빠르게 판별할 수 있는 구조다.
- false positive는 있지만 false negative는 없다.
- 메모리를 적게 사용하면서도 빠른 속도로 동작한다.
어떤 데이터가 있는지보다, 없는 걸 빠르게 아는 게 더 중요한 경우가 종종 있어요. 예를 들어, 스팸 필터처럼요. 없으면 바로 버리면 되잖아요.
Bloom filter는 이런 상황에서 진가를 발휘해요. "이건 확실히 없어!"는 완벽하게 말해주고, "있을 수도?"라는 애매한 대답은 가능하지만, 잘못해서 없는 걸 있다고 하진 않아요.
hash function 여러 개 써서 배열의 비트를 설정하고 체크해요. 약간은 추측 기반이지만, 속도는 진짜 빠르죠. 클럽 입구에서 보안 요원이 명단 확인하는 느낌이에요. 아닌 사람은 바로 거절하고, 비슷한 이름 가진 사람은 가끔 실수로 들여보낼 수도 있는 정도?
Cuckoo Hashing: 새한테 배우는 충돌 해결법
- 한 key가 여러 자리에 들어갈 수 있어 hash 충돌을 독특하게 해결한다.
- 자리가 이미 찬 경우 기존 데이터를 다른 위치로 밀어내는 방식이다.
- 빠르고 안정적인 성능을 보장하는 hashing 기법이다.
이건 진짜 웃기고도 천재 같은 발상인데요, 뻐꾸기 새 아시죠? 자기 알을 남의 둥지에 몰래 낳는 습성이 있대요. 그러면 다른 새가 그걸 자기 자식인 줄 알고 키우는 거죠.
이 행동에서 아이디어를 얻은 게 Cuckoo Hashing이에요. 한 key가 여러 자리 중 하나에 들어갈 수 있고, 만약 자리가 이미 차 있으면 그 자리에 있던 걸 다른 자리로 밀어내요. 완전 뻐꾸기처럼요.
이런 식으로 충돌을 해결하는데, 진짜 빠르기도 하고 안정적이기도 해요. 처음 들었을 땐 "이런 생각을 한다고...?" 싶었지만, 써보면 납득이 됩니다.
왜 이런 구조들을 알아야 하냐고요?
- 기본 구조만으로는 현실의 복잡한 문제를 해결하기 어려울 때가 많다.
- 특수한 상황에서는 이러한 독특한 구조들이 훨씬 더 효율적인 해답이 된다.
- 문제 해결 능력을 확장해주는 도구로 꼭 알고 있어야 할 가치가 있다.
처음엔 array나 stack 같은 구조만 알아도 충분히 뭐든 할 수 있을 것 같아요. 근데 현실은 늘 복잡하죠. 데이터 양도 많고, 구조도 엉켜 있고, 성능도 중요해지고요.
그럴 때 이런 특이한 Data Structure들이 빛을 발해요. 상황에 따라 완전 게임 체인저가 되거든요. 저도 처음엔 "굳이 이걸...?" 했다가, 직접 써보니 진심으로 고마웠어요. 꼭 알아둬야 할 친구들이에요.
Code Rabbit: 이건 진짜 써봐야 안다
여기까지 읽고 "아 근데 나 이런 거 못 짜…" 싶을 수 있어요. 저도 그랬거든요. 그래서 소개하고 싶은 게 있어요. Code Rabbit이라는 도구인데요, 진짜 신기해요.
VS Code 안에서 코드 검사해주고, 버그도 미리 알려줘요. 뭔가 지적만 하는 게 아니라, 이유도 설명해주고, 해결책까지 바로 보여주는 똑똑한 친구예요.
무엇보다 무료라는 점에서 한 번은 써볼 만해요. Cursor나 Windsurf 같은 에디터에서도 되고요. 솔직히, 처음 써봤을 때 “이게 왜 이제 나왔지?” 싶었어요.
마무리할게요!
프로그래밍이란 게 참 그래요. 늘 똑같이 해오던 방법이, 어느 날 벽에 부딪히는 순간이 와요. 그럴 때 새로운 구조 하나가 문제를 싹 해결해줄 수도 있어요.
그러니까 낯설다고 피하지 말고, 이런 구조들도 한 번쯤 써보세요. 언젠가는 분명히 쓸모 있을 거예요.
끝까지 읽어주셔서 감사해요! 여러분도 계속 실험하고, 실패도 해보고, 새로운 구조도 도전해보세요. 그런 게 진짜 개발자의 성장인 것 같아요 :)
'SW > 면접' 카테고리의 다른 글
| 2025 개발자 취업 전략: Specialization과 Evidence로 No-Risk Hire로 보이는 방법 (0) | 2025.09.16 |
|---|---|
| 2025 개발자 채용 시장 완전 가이드: niche·branding·positioning으로 인터뷰 기회 늘리는 법 (0) | 2025.08.14 |
| 비개발자도 이해하는 API의 모든 것 – 예시로 쉽게 배우는 API 입문 (0) | 2025.08.04 |
| System Design 면접에서 떨어지는 5가지 이유와 해결법 완전 정리 (0) | 2025.07.29 |
| 코딩 면접 합격 비법: Python으로 빠르게 마스터하는 자료구조 알고리즘 공부법 (0) | 2025.07.24 |