경계의 경계

그래프를 공부하자

트리를 공부하면서 폴더나 조직도처럼 위아래 관계가 있는 데이터를 표현했다. 트리에서는 모든 노드가 부모를 딱 하나만 가지고, 길을 따라가다 제자리로 돌아오는 일도 없다. 그런데 현실의 관계가 모두 이렇게 깔끔한 위아래는 아니다. 지하철 노선도에서 한 역은 여러 역과 이어지고, 순환선을 타면 출발한 역으로 돌아온다. SNS의 친구 관계에는 누가 위고 누가 아래라는 개념조차 없다. 이렇게 위아래 없이 그물처럼 얽힌 관계를 표현하기 위해 등장한 것이 그래프(Graph)다.사실 트리도 그래프의 한 종류다. 그래프에 "부모는 하나", "제자리로 돌아오는 길(사이클)은 없음"이라는 제약을 건 것이 트리였다. 그래프는 그 제약을 풀어버린, 가장 자유로운 형태의 자료구조다.그래프의 용어는 트리와 비슷하다. 동그라미 하..

힙을 공부하자

스택과 큐를 공부할 때, 큐는 먼저 들어온 것을 먼저 꺼내는 FIFO 구조였다. 그런데 현실에서는 들어온 순서보다 중요도가 먼저인 경우가 많다. 응급실은 먼저 온 환자보다 위급한 환자를 먼저 보고, 운영체제는 우선순위가 높은 작업부터 실행한다. 이렇게 가장 중요한 것을 먼저 꺼내는 큐를 우선순위 큐(Priority Queue)라고 한다.지금까지 배운 구조로 우선순위 큐를 만들면 어떨까? 배열에 그냥 넣으면 넣기는 빠르지만, 꺼낼 때마다 가장 큰 값을 찾느라 전부 훑어야 한다(O(n)). 반대로 정렬된 상태로 유지하면 꺼내기는 빠르지만, 넣을 때마다 자리를 찾아 밀어야 한다(O(n)). 지난 글의 균형 트리를 쓰면 둘 다 O(log n)이지만, "가장 큰 것 하나"만 필요한데 전체를 정렬해 두는 건 과하다..

트리를 공부하자

지금까지 공부한 배열, 리스트, 스택, 큐는 모두 데이터를 한 줄로 늘어놓는 선형(linear) 구조였다. 해시 테이블도 속을 들여다보면 결국 배열이었다. 그런데 현실의 데이터가 모두 한 줄로 서 있지는 않다. 컴퓨터의 폴더 안에는 또 폴더가 있고, 회사 조직도에는 대표 아래 팀장이, 팀장 아래 팀원이 있다. 이렇게 위아래 관계(계층)가 있는 데이터를 표현하기 위해 등장한 것이 트리(Tree)다. 이름처럼 하나의 뿌리에서 가지가 뻗어 나가는 모양이다.트리는 계층을 표현하는 데서 끝나지 않는다. 규칙을 하나 더하면 정렬된 상태를 유지하면서도 빠르게 찾을 수 있는 구조가 된다. 사실 지난 글에서 다룬 HashMap도 한 칸에 값이 너무 많이 쌓이면 그 칸을 트리로 바꿔 탐색 속도를 지킨다.트리를 이루는 동그..

해시는 앞서 공부했던 배열이나 스택, 큐와는 다른 문제를 풀기 위한 자료구조이다. 해시 없이 배열만으로 "값 찾기"를 한다고 가정해보자. 배열/리스트에서 9라는 값이 있는지 찾으려면 앞에서부터 하나씩 비교해야하는 연산을 수행해야 하고 이는 O(n)이다. 인덱스를 안다면 O(1)이지만, 우리가 알고 찾으려고 하는 것은 값(키)이다. 해시는 키를 계산(해시 함수)해서 곧바로 배열의 인덱스로 바꾼다.그럼 키를 어떻게 인덱스로 바꿀까? 그 계산을 맡는 게 해시 함수(hash function) 다. 해시 함수는 임의의 키를 정해진 범위의 숫자로 변환한다. 예를 들어 "apple"이라는 문자열을 넣으면 8493... 같은 정수(해시값)가 나온다.그런데 이 숫자는 배열 크기보다 클 수 있으니, 배열 크기로 나눈 나머..

다음 공부 순서는 큐(Queue)와 스택(Stack)이다. 데이터 구조에 대한 이야기는 이전 포스팅에서 했다. 배열과 리스트는 자료를 저장하고 찾는 방법에 대하여, 데이터를 묶음으로 다루는 데이터 구조였다. 큐와 스택은 왜 등장했을까? 배열과 리스트는 아무 칸에나 접근할 수 있는 범용 구조다. 인덱스로 어디든 읽고, 어디든 뺄 수 있다. 그런데 이 "뭐든 할 수 있음"이 단점으로 작용하는 상황이 있다. 현실의 많은 문제는 데이터를 넣고 빼는 순서에 규칙이 필요하기 때문이다. 예를 들면 웹 브라우저의 뒤로가기는 가장 최근에 있었던 페이지로 되돌아가고, 은행의 번호표는 항상 먼저 온 순서를 불러준다. 이걸 배열로 직접 짜려면 "매번 마지막 인덱스에서 꺼내야지", "맨 앞부터 빼야지" 하고 개발자가 규칙을 손..

호기롭게 첫 글을 적어두고, 포스팅 할 거리를 찾아보니 현재 업무하고 있는 내용들은 내가 쉽게 풀어 쓸 수 있는 범주의 것들이 별로 없었다ㅠㅠ. 물론 쉽게 풀어 쓸 수 있느냐 여부가 뭐가 중요해! 할 수 있지만, 내가 이해한 바대로 적을 수 있어야 좋은 글이 나오지 않을까 싶은 마음에 기초적인 것부터 다시 공부를 시작하는 의미로 developer roadmap 의 순서를 다시 따라가 보기로 했다.한번 공부를 진행하다가 꾸준함의 실패를 겪은 적이 있어서, 최대한 내가 지속할 수 있고 이해할 수 있는 범위 내에서 공부를 진행해보기로 마음먹었다. 우선 현재 업무에 가장 많이 사용하고 있는 언어가 코틀린이기 때문에 가볍게 코틀린으로 골랐다. 이전에 실패한 원인은 "Pick a Language" 파트에서 low ..

최근 내 개발에 큰 영향을 미치는 시니어 스태프(이하 고문님)에게 나는 현재 상황에서 무엇을 해야할 지 방향성을 여쭤보았다. 가장 빠르게 성과가 보이는 방향성은 AI 역량을 강화하고, 비즈니스적으로 깊에 파고드는 것이라고 생각하기에 고문님도 현실의 방향성과 밸런스가 맞는 조언을 주실 것이라고 생각했는데, 고문님이 제시한 방향성은 정반대였다.이럴 때일수록 CS 지식을 강화하라.AI 는 적극 활용하되, 보조 도구로 사용하라. 알지 못하는 상태에서 하는 질문은 진실과 거짓을 구분할 수 없다.맞는 말씀이다. 아직 수많은 개발팀들이 원하는건 합류하는 팀원의 탄탄한 실력이고, 이는 철저한 지식이 뒷받침하니까. 그렇다고 해서 마냥 반성만 하고 있기에 의문이 전부 다 가신것도 아니었다. 실제로 AI가 발전함에 따라 실..

Complex Data Structures 정리: B트리, 스킵 리스트, ISAM (Python 예제 포함)Complex Data Structures(복잡한 자료구조)는 대규모 데이터를 효율적으로 저장하고 탐색하기 위해 사용되는 고급 자료구조다. 데이터베이스, 파일 시스템, 검색 엔진 등 다양한 분야에서 핵심적으로 활용된다.Complex Data Structures란?복잡한 자료구조는 단순한 배열, 연결 리스트로는 해결하기 어려운 문제를 다루기 위해 설계되었다. 대표적인 예시는 다음과 같다.트리(Tree): 계층적 구조 표현, 파일 시스템 등에서 사용그래프(Graph): 네트워크 구조, SNS나 네트워크 토폴로지 표현해시 테이블(Hash Table): 키-값 기반으로 평균 O(1) 탐색 성능 제공힙(He..

고급 자료구조 (Advanced Data Structures) 정리와 파이썬 구현 예제프로그래밍과 알고리즘 문제 해결에서 중요한 개념 중 하나가 자료구조다. 특히, 기본적인 배열(Array), 스택(Stack), 큐(Queue), 연결 리스트(Linked List) 등을 넘어서는 고급 자료구조(Advanced Data Structures) 는 복잡한 문제를 효율적으로 해결하는 데 핵심 역할을 한다.이 글에서는 Trie, Segment Tree, Fenwick Tree, Disjoint Set, Suffix Array 같은 대표적인 고급 자료구조를 정리하고, 파이썬 코드 예제를 통해 이해를 돕는다.목차Trie (트라이)Segment Tree (세그먼트 트리)Fenwick Tree (펜윅 트리, Binary..

그래프 자료구조(Graph Data Structure)와 탐색 알고리즘 총정리그래프 자료구조(Graph Data Structure)는 컴퓨터 과학에서 매우 중요한 개념이다. 그래프는 정점(Vertex, Node)과 간선(Edge)으로 이루어진 비선형 자료구조로, 네트워크나 관계를 표현할 때 자주 사용된다.웹 페이지 연결, 소셜 네트워크, 최단 경로 탐색 등 다양한 분야에서 활용된다.그래프의 종류그래프는 크게 방향 그래프와 무방향 그래프로 구분된다.방향 그래프(Directed Graph): 간선이 한쪽 방향으로만 연결된다. 예를 들어, 일방통행 도로 네트워크.무방향 그래프(Undirected Graph): 간선이 양방향 관계를 가진다. 예를 들어, 친구 관계.또한 가중 그래프(Weighted Graph)와..