꾸준합니다

그래프 (3) : 가장 짧은 경로

이번 포스팅에서는 가중 그래프와 최단 거리 찾기에 자주 사용되는 알고리즘에 대해 알아보도록 하겠습니다. 1. 가중 그래프(Weighted graph) 란? 그래프에는 다양한 변형이 존재합니다. 그래프 간선에 정보를 추가하는 가중 그래프 역시 또 하나의 유용한 그래프 유형입니다. 위 그래프와 같이 간선에 비용, 거리 등을 데이터를 부여하여 사용됩니다. 코드로 구현한다면 아래와 같이 구현할 수 있습니다. class WeightedGraphVertex { data; // 배열 대신 해시 테이블 사용하여 가중치 삽입 adjacentVertices; constructor(data) { this.data = data; this.adjacentVertices = new Map() } addAdjacentVertex(..

그래프 (2) : 탐색의 방향?

그래프에서의 탐색은 우리가 일반적으로 알고 있는 자료구조에서 일반적으로 쓰이는 연산으로서의 의미 이외에도 여러 의미와 쓰임새를 가지고 있습니다. 이번 포스트에서는 그 의미와 쓰임새를 알아보고 탐색을 진행하는 방법에는 어떠한 것이 있는지 이야기해 보겠습니다. 1. 그래프에서의 탐색 그래프 용어에서 탐색은 몇가지 의미를 함축하고 있습니다. 단순한 의미로는 특정 정점(vertex)이 어디에 존재하는지 찾는 것입니다. 또 하나는 그래프 내에서 정점에 접근할 수 있을 때 그 정점과 연결된 또 다른 특정 정점을 찾는 것을 의미합니다. 경로(path)라는 용어는 그래프 용어로 한 정점에서 다른 정점으로 가는 간선들의 순열을 뜻합니다. 그래프의 탐색은 특정 정점 찾는 것 이외에도 두 정점이 서로 연결되어있는 상태인지 ..

그래프 (1) : SNS가 이거에요

이번 포스팅에서는 데이터 간의 관계에 특화된 자료구조인 그래프에 대해서 이야기해 보겠습니다. 1. 그래프란? 그래프는 관계를 표현하는데 특화된 자료구조로서 데이터 간 연결 상태를 쉽게 보여줍니다. 그래프에서는 각각의 구성 요소를 가리키는 단어가 존재합니다. 그래프의 노드를 정점(vertex), 그 정점을 연결하는 선을 간선(edge)라고 부릅니다. 간선으로 연결된 정점들은 서로 인접한다(adjacent)라고 말합니다. 그리고 인접한 정점들을 가리켜 이웃(neighbor)라고 부릅니다. 그래프에서는 다른 정점과 연결되지 않은 정점이 존재할 수 있습니다. 모든 정점이 연결되어있는 그래프를 가리켜 연결 그래프(connected graph)라고 부릅니다. 2. 방향 그래프 SNS를 예로 들어보면 A라는 사람이 ..

트라이 : 텍스트 데이터 특화 트리

검색창의 자동 완성 기능의 동작 방법에 대해 궁금해하신 적이 있으신가요? 단어의 자동완성을 위해 검색창은 DB에 저장된 전체 데이터에 접근합니다. 이런 단어들에 대해서 어떤 자료구조로 저장하고 있을까요? 정렬되지 않은 배열로 저장되었다면 탐색 시 전체 배열을 탐색해야 하기에 $ O(N) $ 의 시간이 걸리게 됩니다. 정렬된 배열은 어떨까요? 정렬되어 있기 때문에 단계를 진행할수록 많은 후보군이 사라지고 $ O(logN) $ 만큼의 단계 안에 탐색을 마칠 수 있습니다. 정렬된 배열도 매우 빠르지만 무려 상수 시간 안에 자동 완성 기능을 실행할 수 있는 자료 구조가 존재합니다. 오늘은 해당 자료구조에 대해 포스팅 해보도록 하겠습니다. 1. 트라이 (Trie)란? 트리의 한 종류인 트라이 (trie)는 자동 ..

힙과 우선순위 큐 : 제일 큰 값, 작은 값

이번 포스트에서는 특정 시나리오에서 유용하게 사용될 수 있는 트리 자료구조의 카테고리에 있는 힙 (Heap)에 대해 알아보도록 하겠습니다. 힙은 데이터 셋에서 가장 큰 또는 가장 작은 데이터 원소를 계속 알고 있어야 할 때 유용하게 쓰입니다. 또 힙의 기능을 제대로 파악하기 위해 우선순위 큐 (Priority queue) 또한 함께 알아보도록 하겠습니다. 1. 우선순위 큐 (Priority queue)란? 일반 큐 (Queue)는 FIFO (First-In, First-Out)로 항목을 처리하고 자료구조의 양끝에서만 데이터를 처리합니다. 큐의 데이터에 접근하려면 데이터의 삽입된 순서에 우선권이 있습니다. 스택과 큐 - 제약을 통한 문제 해결 전략 이번 포스팅에서 효율성 보다 코드의 간결함에 중점을 둔 자..

이진 탐색 트리 : 검색, 삽입, 삭제 모두 O(logN)

데이터를 특정 항목을 기준으로 정렬하고 싶을 수 있습니다. 퀵 정렬 알고리즘과 같은 방법으로 정렬을 할 수 있겠지만 정렬에는 비용이 발생합니다. 또 정렬된 자료구조에서 데이터의 변경이 발생하는 경우 변경 때마다 정렬된 상태를 지키기 위해서 정렬 비용을 계속해서 지불해야만 합니다. 삽입과 삭제가 빠르면서도 정렬이 되어있는 자료구조가 있다면 어떨까요? 놀랍게도 그러한 자료구조가 존재합니다. 그게 바로 오늘 포스팅할 "트리"입니다. 1. 트리 (Tree)란? 트리는 노드 기반 자료 구조이면서 구성 요소인 각 노드는 여러 노드로의 링크를 포함할 수 있습니다. 그 모습이 마치 나무를 연상시킨다 하여 트리라 명명하였습니다. 2. 트리의 고유 용어 트리 자료구조에는 트리에서만 사용하는 고유 용어가 존재합니다. 가장 ..

연결리스트 : 대량 삽입과 삭제에 유리한 Node 기반 자료구조

컴퓨터 과학의 많은 자료 구조들은 Node라는 개념에 기반해 만들어져 있습니다. Node란 컴퓨터 메모리 곳곳에 흩어져 있는 데이터 조각을 의미합니다. 이번 포스트에서 알아볼 연결 리스트는 이러한 Node 기반 자료 구조 중 가장 간단한 자료구조라고 할 수 있습니다. 지금부터 연결리스트에 대해 알아보도록 하겠습니다. 1. 연결 리스트 (Linked List) 란? 연결리스트는 배열과 마찬가지로 항목의 리스트를 표현하는 자료구조입니다. 배열은 연속되는 메모리에 항목들을 배치하고 이러한 점 덕분에 인덱스를 통해 항목에 바로 접근할 수 있습니다. 그렇다면 메모리에 흩어져있는 항목(Node)들을 가진 연결리스트는 어떻게 항목에 접근할까요? 이 답이 바로 연결 리스트의 핵심입니다. 각 Node는 추가정보, 연결리..

스택과 큐 - 제약을 통한 문제 해결 전략

이번 포스팅에서 효율성 보다 코드의 간결함에 중점을 둔 자료구조에 대해 알아보겠습니다. 스택과 큐는 임시데이터를 처리할 수 있는 도구입니다. 임시데이터란 사용 후에는 의미 없는 데이터로서 제거해도 무관합니다. 스택과 큐는 임시데이터를 처리하며 주로 처리 "순서"에 중점을 둡니다. 1. 스택 ( Stack )이란? 스택이 데이터를 저장하는 방법은 배열과 같습니다. 다만 몇 가지의 제약 사항을 가지고 있습니다. 데이터는 스택의 끝에만 삽입 가능 => push 데이터를 스택의 끝에서만 삭제 가능 => pop 마지막 원소( Top )만 읽기가 가능 => peek 스택의 연산은 보통 두 문장으로 LIFO ( Last-In, First-Out / 후입선출 )으로 표현합니다. 항상 삽입된 마지막 항목이 첫 번째로 출..