Theory/Algorithms (35) 썸네일형 리스트형 위상 정렬 (Topological Sort) 위상 정렬은 사이클이 없는 방향 그래프 (Directed Acyclic Graph, DAG) 에서 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 정렬을 말합니다. 즉, 시작점이 존재하는 방향 그래프에서 순서를 거스르지 않고 정점을 나열하는 것입니다. 위상 정렬을 위해서는 진입차수 (In degree) 와 진출차수 (Out degree) 를 알아야 합니다. 그래프는 정점과 간선 정보로 존재하는데, 진입차수란 특정한 노드로 들어오는 간선의 개수, 진출차수는 특정한 노드에서 나가는 간선의 개수입니다. 위상 정렬은 진입차수가 0인 정점 (시작점)을 먼저 배치하고, 그 정점에서 나가는 간선들을 제거합니다. 그 후, 다음 진입차수가 0인 정점을 배치합니다. 위상 정렬은 큐나 스택을 이용해 구현할 수 있습니.. 자료구조 - 서로소 집합 서로소 집합은 데이터를 여러 가지 집합으로 분리하는 자료구조로 각 데이터를 같거나 다른 집합으로 분리하여 집합 관계를 표현합니다. 서로소 집합 자료구조는 X가 속한 집합과, Y가 속한 집합을 합치는 UNION(X, Y) 연산과 X가 속한 집합을 찾는 FIND(X) 연산으로 구성되어 있으며, UNION-FIND 자료구조라 부르기도 합니다. 각 집합은 루트 노드로 표현되며 UNION 연산은 각 데이터의 속한 집합이 다른 경우 합쳐주면서 루트 노드를 통일합니다. FIND 연산은 해당 데이터가 속한 집합의 루트 노드를 반환합니다. 여러 개의 합치기 연산이 주어졌을 때, 서로소 집합은 다음과 같이 동작합니다. X가 속한 집합의 루트 노드와, Y가 속한 집합의 루트 노드를 확인합니다. 같은 집합일 경우, 따로 합치.. 유니코드와 UTF-8 유니코드 (Unicode) 유니코드는 유니코드 consortium 에서 규율하는, 전 세계의 모든 문자를 다루도록 처리된 표준 문자 전산 처리 방식으로 전 세계의 모든 문자를 담은 ISO/IEC 10646 Universal Character Set을 사용함으로써 각 언어의 문자체계에 따른 충돌을 해결했습니다. 따라서, 한글, 간체자, 아랍 문자 등을 통일된 환경에서 깨뜨리지 않고 사용할 수 있습니다. 아스키코드 초창기 문자를 표현하던 방식은 미국 국립 표준 협회 (ANSI)에서 표준화한 ASCII (American Standard Code for Information Interchange) 코드로 1바이트에 문자를 표현한 방식입니다. Checksum 1비트를 제외한 7비트의 128글자로 (영문 키보드로 .. 최단 경로 문제 (2) - 플로이드 워셜 알고리즘 플로이드 워셜 (Floyd Warshall) 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 계산하는 알고리즘으로 다익스트라 알고리즘처럼 단계 별로 거쳐가는 노드를 기준으로 수행합니다. 하지만, 다익스트라 알고리즘처럼 방문하지 않은 노드 중 최단 거리를 찾는 과정을 거치지 않고 다이나믹 프로그래밍 방법처럼 2차원 테이블에 대해 각 노드별 최단 거리를 업데이트하는 방법으로 수행하여 음수 간선을 가지는 그래프에 대해서도 동작합니다. 다이나믹 프로그래밍의 상향식 테뷸리이션 방법으로 2차원 최단 거리 테이블을 업데이트하는 방식으로 이루어지는데요. a노드와 b노드의 최단거리 테이블을 업데이트하기 위한 점화식은 다음과 같습니다. $D_{ab} = min(D_{ab}, D_{ak}+D_{bk})$ 각 단계.. 최단 경로 문제 (1) - 다익스트라 알고리즘 최단 경로는 지도 상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제입니다. 각 지점은 정점 (vertex), 정점사이의 간선 (edge)은 길에 해당하고 가중치는 간선에 대한 시간, 거리 등의 이동비용에 해당합니다. 구성한 그래프의 형태에 따라 각각 최적화된 다양한 최단 경로 알고리즘이 존재합니다. 이번 포스트에서는 그 중 가장 대표적인 다익스트라 (Dijkstra) 알고리즘을 살펴보겠습니다. 다익스타라 알고리즘은 네덜란드의 에츠허리 다익스트라가 1956년에 고안한 알고리즘으로 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산하는 알고리즘입니다. 특히, 다익스타라 알고리즘은 매 상황에서 가장 비용이 적은 노드를 선택하는 그리디 알고리즘으로 분류됩니다. 알고리즘.. 자료구조 - 해시 테이블 (Hash Table) 해시 테이블은 임의 크기 데이터를 고정 크기 값으로 매핑하는 해시 함수를 기반으로 동작하는 대부분의 연산의 시간 복잡도가 상수 시간 $O(1)$ 이 소요되는 자료구조입니다. 한스 피터 룬 (Hans Peter Luhn)이 처음 사용한 것으로 알려져 있으며, 현대에도 각종 프로그래밍 및 알고리즘에 중요하게 사용되는 자료구조입니다. 해시 테이블은 키:값 (key:value) 의 형태로 데이터를 저장합니다. 키 (key) 값에는 해시 함수를 적용해 값이 저장된 배열 (버킷)에 대한 고유한 인덱스를 생성하고 이 인덱스를 활용해 값을 저장하거나 검색합니다. 따라서 키에 대해 해시 함수를 한 번만 적용하면 되니, 저장이나 검색에 $O(1)$의 상수 시간 복잡도가 소요됩니다. 위 그림에서 키인 'John Smith'.. 자료구조 - 힙 (Heap) 힙은 부모가 항상 자식보다 작거나 같다 (최소힙)라는 특성을 만족하는 트리 기반의 자료구조입니다. 이번 포스트에서 다룰 힙은 최소힙이고 최소힙은 부모가 항상 자식보다 작기 때문에 트리의 루트가 가장 작은 값을 갖게 됩니다. 반대로 최대힙은 부모가 항상 자식보다 큰 트리가 되겠죠. 힙이라는 자료구조는 J.W.J. 윌리엄스가 1964년 힙 정렬 알고르짐을 고안하면서 파생된 부산물입니다. 보통 배열로 구현하며 다음 그림과 같이 부모와 자식 간의 상하 관계가 정의되어 있고 같은 레벨의 자식들끼리의 좌우 관계는 정의되어 있지 않습니다. 힙은 주로 배열로 구현되며, 위 그림 오른쪽처럼 배열로 표현할 수 있습니다. 루트 노드의 인덱스는 1부터 시작하고 그 다음 레벨 노드의 인덱스는 2,3, 그 다음 레벨 노드의 인덱.. 자료구조 - 스택 (Stack), 큐 (Queue) 스택 (Stack) 과 큐 (Queue) 는 프로그래밍에서 가장 기본적으로 사용하는 고전적인 자료 구조임과 동시에 특히 스택은 거의 모든 애플리케이션을 만들 때 사용됩니다. 스택은 Last In First Out (선입후출) 의 자료구조로 마지막에 들어온 원소가 가장 먼저 추출됩니다. 잔뜩 쌓인 접시를 생각하면 됩니다. 스택의 개념은 자료를 저장하는 자료구조와 동시에 컴퓨터 프로그램의 서브루틴에 대한 정보로 활용됩니다. 가장 마지막에 저장된 커맨드가 실행되는 식이죠. 큐는 스택과 반대로 First In First Out (선입선출) 의 자료구조로 가장 먼저 들어온 원소가 가장 먼저 추출됩니다. 일반적인 대기열을 생각하면 되겠네요. 파이썬에서는 스택과 큐의 자료구조를 따로 제공하지는 않으나 리스트가 관련 .. 이전 1 2 3 4 5 다음
