Data Structure

그래프의 표현 방식 2번째인 인접 리스트 (adjacency list) 에 대해서 알아보자. 인접 리스트 방식에서는 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결해서 저장한다. 위의 그림과 같이 노드0에 노드1, 노드2, 노드3이 연결되어 있다는 것을 표현했고 같은 방식으로 노드1, 노드2, 노드3에 연결된 노드들을 차례대로 저장하였다. 위의 그림은 C언어에서의 인접 리스트 표현 방식인데 C에서는 배열에 포인터를 넣어서 연결된 노드들을 가리키게 된다. 파이썬에서는 인접 행렬과 동일하게 2차원 리스트로 인접 리스트를 표현할 수 있다. 가중치가 있는 그래프에서의 인접 리스트 표현 방식은 아래와 같다. 위의 그래프를 인접 리스트로 표현하는 소스코드는 아래와 같다. 인접 행렬과 인접 리스트의 차이점은 무..

그래프에서 "인접 (adjacent)하다" 라는 것은 두 vertex를 잇는 edge가 존재한다는 것을 의미한다. 즉, 두 vertex가 연결되어 있다는 뜻이다. 그래프에서 이렇듯 vertex간의 인접함을 나타내는 방식은 크게 2가지가 존재한다. 첫 째로는 인접 행렬 (Adjacency Matrix) 이 있고, 둘 째로는 인접 리스트 (Adjacency List) 가 존재한다. 이 중 인접 행렬에 대해서 다룬다. 인접 행렬이란 2차원 배열에 각 node가 연결된 형태를 저장하는 방법이다. 즉, 인접 행렬에서 [ i ][ j ] 는 vertex i 와 vertex j 간의 연결성을 나타내는 것이다. 이 때 2차원 배열의 [ i ][ j ] 에는 다음과 같은 값들을 저장한다. 1 : (edge에 가중치가 없..

그래프란 자료 구조의 한 종류로 노드 (node) 와 간선 (edge) 으로 표현되는 구조이다. 이 때, 노드를 정점 (vertex) 이라고 부르기도 한다. 아래에 3개의 그래프에 대한 예시를 보자. 이 3개의 그림 모두 그래프를 표현한 것이다. 먼저 G2는 트리 (Tree) 의 형태를 띄고 있다. 따라서 트리 또한 (순환하지 않는) 그래프의 한 종류라는 것을 알 수 있다. G1과 G2에는 화살표가 존재하지 않고, G3에는 화살표가 존재하는 것을 알 수 있다. 이는 undirected graph (무방향 그래프)와 directed graph (유방향 그래프) 의 차이이다. Undirected Graph : 방향이 없는 간선을 가지고 양방향 관계를 나타내는 간선을 가지는 그래프 Directed Graph ..

지난 게시물에서 스택과 큐 중 스택에 대한 내용을 다루었다. 이번 게시물에서는 큐에 대해서 이야기 해 보려고 한다. 큐는 아래와 같이 정의 내릴 수 있다. 큐 (Queue) 란 맛집에서 서는 대기줄과 같다. 대기줄을 설 때 처음 줄을 선 사람은 가장 앞에 서고 점점 그 뒤에 사람들이 대기줄을 서게 된다. 이후 자리가 나게 되면 대기줄의 가장 첫 사람이 식당으로 들어가게 된다. 이러한 비유는 큐를 설명하는데 매우 적합하다. 이를 큐에서의 데이터 삽입, 삭제와 비유하면 다음과 같다. - 삽입 (push / add) : 대기줄에 한 명씩 차례대로 서는 것 - 삭제 (pop / delete) : 대기줄의 가장 앞에서부터 한 명씩 빠지는 것 스택과는 반대로 큐는 선입선출 (First In First Out, FI..

이전 게시물에서 자료구조의 기본 개념이 되는 스택과 큐 라는 구조에 대한 간단한 설명을 게시했다. 이번에는 스택에 대해서 자세히 다뤄보려고 한다. 먼저 스택이란 책의 인용을 빌리면 아래와 같다. 스택 (Stack) 이란 박스 쌓기와 같다. 박스를 쌓을 때는 아래에서부터 차곡차곡 위로 쌓고 박스를 제거할 때는 위에서부터 하나씩 제거하게 되는데 이러한 구조가 스택과 매우 유사하다. 이를 앞의 게시물에서 설명한 핵심 함수에 비유하면 다음과 같다. - 삽입 (push) : 박스를 아래에서부터 한 층씩 쌓는 것 - 삭제 (pop) : 박스를 위에서부터 한 층씩 제거하는 것 이와 같이 스택은 선입후출 (Last In First Out, LIFO) 의 방식으로 데이터를 삽입, 삭제한다. 즉, 스택은 데이터의 삽입과 ..

Chapter 5. DFS/BFS를 들어가기 앞서 자료구조에 대한 기초적인 지식이 필요하다. 먼저 탐색(Search)과 자료구조(Data structure)에 대해서 알아본다. 탐색이란 많은 양의 데이터 중에서 자신이 원하는 데이터를 찾는 과정을 의미한다. 뒤에서 작성하게 될 그래프, 트리 등의 자료구조 내에서 원하는 데이터를 찾는 알고리즘이 자주 등장할 것이다. 대표적으로 DFS 혹은 BFS 등의 탐색 알고리즘이 존재한다. 이러한 탐색 알고리즘을 정확하게 이해하기 위해서는 자료구조에 대한 이해가 필요하다. 자료구조란 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미한다. 그 중 스택(Stack)과 큐(Queue)는 자료구조의 기초 개념이며 자세한 내용은 다음 게시글에서 다루기로 한다. 스택과 큐..