Data Structure

자료구조는 자료(데이터)를 효과적으로 효과적으로 표현하고 효율적인 저장과 처리하도록 하는 논리적 구조를 이야기 합니다. 자료구조에는 선형, 비선형, 파일, 단순구조가 존재합니다.시중에 나와있는 책이나 여러 글들을 보면 선형구조인 리스트, 스택, 큐/ 비선형 구조인 트리

리스트는 자료(데이터)를 순서대로 나열한 자료구조 입니다. 순서대로 나열되어있다는 점 때문에 순차 자료구조라고 부르기도 합니다. 리스트에는 선형 리스트와 연결 리스트 두 가지가 존재합니다. 두 가지는 순서대로 자료가 나열되어있다는 점은 같지만 다음과 같은 차이점이 있습

선형 리스트(Linear List)는 자료들이 순서대로 저장되어있는 리스트입니다. 이때 저장된 물리적 순서와 논리적 순서가 반드시 일치해야합니다. 그래서 선형 리스트는 배열로 구현하게 됩니다.사실 선형 리스트는 배열이라고 봐도 무방할 정도로 그동안 써왔던 배열을 그대로

C로 작성된 포스트입니다.연결 리스트(Linked List)는 선형 리스트와는(순차 자료구조) 다르게 자료의 순서가 존재하지 않는 자료구조 입니다. 순서가 없는 자료구조를 저장하는 방식은 노드(포인터)를 이용하는 방식입니다. 자료는 데이터 필드와 링크 필드 한 쌍으로

원형이라는 이름에서 볼 수 있듯이 원형 연결 리스트는 동그란 형태를 가진 연결 리스트입니다. 하지만 연결 리스트 소개에서 이야기 했듯이 실제 물리적으로 원형이 아니라 처음과 끝이 이어져 있기 때문에 원형이라고 불리우는 것 입니다. 지난번 까지 배운 연결 리스트는 hea

이중 연결 리스트 혹은 양방향 연결 리스트라고 불리우는 이 자료도 연결 리스트의 일종입니다. 지난번 원형 연결 리스트와 마찬가지로 한 가지 개념만 추가하면 되는데요. 바로 링크 필드가 데이터 필드의 양옆에 있다는 점입니다.지난번 까지 알아본 리스트의 노드들은 다음과 같

스택(Stack)은 데이터를 쌓아올린듯한 자료구조입니다.마트에 가면 '프루팁스'라고 제가 좋아하는 젤리를 팝니다.이렇게 생긴 원통형 젤리인데요. 한쪽은 젤리를 꺼낼 수 있는 뚜껑이 있고 반대쪽은 막혀있습니다. 그래서 한쪽으로만 젤리를 넣고 꺼낼 수 있죠. 스택이 마치

큐(Queue)는 스택처럼 특정한 위치에서 넣고 뺄 수 있는 자료구조입니다. 스택은 입구와 출구가 같아서 나중에 들어간 자료가 먼저 나오는 후입선출 구조였다면, 큐는 입구와 출구가 따로 있어서 먼저들어간 자료가 먼저 나오는 선입선출(FIFO, First Input Fi

지난번에 배열을 이용한 큐 구현에서 원소를 삭제할 때 삭제하고 배열 내부의 원소를 하나씩 앞으로 이동하면 큐가 구현되지만 원소 이동이라는 작업이 오버헤드를 일으켜 구현도 사용도 어렵다고 했었습니다. 그래서 나온개념이 배열 내부의 원소가 아닌 front와 rear를 움직

데크(Deque)는 큐의 변형 자료구조 중 하나입니다. 데크의 의미는 Double Ended Queue로써 끝이 2개인 큐를 의미합니다. 기존의 큐는 아래 그림처럼 한 끝에서만 삽입, 다른 한 끝에서만 삭제가 이루어졌습니다. 하지만 데크는 양 쪽 끝에서 삽입과 삭제가

트리(Tree), 나무와 스펠링이 같습니다. 보통 우리가 생각하는 나무는 어떻게 생겼죠? 아래는 넒고 위로 갈수록 좁아지는 형태를 갖고있습니다.이처럼 트리도 위에서 아래로 갈수록 자료가 많아지는 구조를 가지고 있습니다.가만보면 여태까지 배운 리스트나 큐, 스택, 데크를

트리마다 자식 노드 수가 제각각이라면, 연산에 대해서 오버헤드가 굉장히 버겁고, 구현도 복잡해지게 됩니다. 그래서 이런 문제를 해결하기 위해 트리의 구조를 일정하게 만드는데, 그 구조 중 대표적인 것이 이진 트리입니다. 이진 트리(Binary Tree)란, 모든 노드의

이전 두 개의 포스트에 걸쳐서 이진 트리에 대한 개념을 소개했었습니다. 본격적으로 이번 포스트에서 이진 트리를 구현해보도록 하겠습니다.트리도 배열을 이용해서 구현할 수는 있습니다.그림처럼 노드에 번호를 부여하고 배열의 인덱스와 노드 번호를 일치시켜 데이터를 저장하죠.

지난 포스트에서 이진 트리를 구현해 보면서, 트리 삽입 과정에서 문제가 발생했었습니다. 트리의 하위 트리가 존재하는 경우 그 아래 트리의 메모리가 반환되지 않아 메모리 낭비가 일어나는 과정이었는데요. 이 과정을 순회 라는 개념으로 해결할 수 있다고 했었습니다.순회는 트

이진 탐색 트리는 트리를 실제로 사용하기 위해 정의한 구조입니다. 자료구조를 실제로 사용한다는 것은 자료를 저장하고 검색하기 위함을 의미합니다. 이때 특정 기준에 따라서 트리 노드를 정렬하는데 보통 노드의 원소 크기를 기준으로 정렬합니다. 이때 노드의 원소를 우리는 키

이진 탐색 트리는 트리 구조마다 연산시간이 천차만별입니다. 다음 그림처럼 같은 노드를 가져도 구조에 따라서 연산시간이 다르게 됩니다. 같은 3개의 노드, 같은 요소인데도 8이라는 요소를 탐색 할 때 왼쪽 편향 트리는 노드를 2번 거치는 연산을 하고, 오른쪽 그림의 이진

힙(Heap) 혹은 히프는 완전 이진 트리 종류 중 하나 입니다. 힙는 여태까지 트리를 계속 해서 연결 자료구조로 구현한 것과는 다르게 1차원 배열을 이용해서 구현할 수 있는 자료구조 이기도 합니다.힙(Heap)은 이진 트리의 노드들 중에서 키값이 가장 큰 값또는 가장

리스트와 스택, 큐는 1:1 구조의 자료구조, 트리는 1:다의 자료구조였습니다. 그렇다면 다:다 관계를 가진 자료구조도 존재할 것 같다는 생각이 듭니다. 그래프는 이처럼 다:다의 관계를 가진 자료구조 입니다.지하철 노선도 처럼 한 역에서 찍어서 다른 역에 도달하는 방법

모든 자료구조가 그래왔듯이 그래프를 구현하는 방식에는 순차 자료구조를 이용하는 방식과 연결 자료구조를 이용하는 방식 두가지가 있습니다. 그래프에서도 마찬가지이지만 이름을 조금 다르게 부릅니다.순차 자료구조를 이용해서 구현하는 것을 인접 행렬 기반 그래프, 연결 자료구조

지난번엔 순차 자료구조인 2차원 배열을 이용한 인접 행렬 기반 그래프를 구현했습니다. 이번에는 연결 자료구조를 이용해서 그래프를 구현해보도록 하겠습니다.인접 리스트 방식은 한 정점에 대해서 인접한 리스트를 연결 리스트로 연결한 것입니다. 다음과 같은 그래프를 인접 리스

그래프의 탐색 혹은 그래프의 순회라고 불리우는 개념은 그래프의 모든 정점을 반드시 한 번은 방문하는 것을 말합니다. 그래프의 탐색 방법에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 두 종류가 있는 그 중에서 깊이 우선 탐색 부터 알아보겠습니다.깊이 우선 탐색

지난번에 본 깊이 우선 탐색(DFS)는 한 정점에서 시작해서 갈 수 있는 정점까지 방문한 후에 방문하지 않은 인접 정점이 있는 정점으로 돌아와서 진행하는 방식이었습니다. 이번에 배울 너비 우선 탐색(BFS, Breadth First Search)은 정점에 인접한 정점들