자료구조의 전체 요약

자료구조

자료구조에 대한 기초 지식이 거의 없으시다면, 이 링크에서 학습하시는 것을 추천드립니다.

Array vs LinkedList

둘 다 컴퓨터 메모리 상에 나란히 저장되어 있는 자료구조 이지만, Array의 크기는 정적, LinkedList의 크기는 동적입니다. 즉, Array는 한 번 배열 크기를 정했으면 배열을 다시 재정의하지 않는 한 크기가 바뀌지 않는다는 것이고, ArrayList는 처음 선언 시 일정 크기를 잡아주기는 하지만, 그 크기를 초과한다고 한들 재정의할 필요 없이 노드의 개수를 늘려 연결해주면 됩니다.

또한, Array는 특정 인덱스에 접근. 즉, 조회시 O(1)의 시간 복잡도를 가지며, 삽입과 삭제 후 값을 앞으로 한 칸씩 당겨오기 위해서는 O(N)의 시간이 걸립니다. ArrayList는 가장 앞 혹은 뒤에 있는 인덱스를 조회/삽입/삭제할 경우에는 O(1)의 시간 복잡도를 가지게 되며, 그 외에 인덱스를 조회/삽입/삭제할 경우에는 O(N)의 시간 복잡도를 갖게 됩니다.

 

Stack & Queue

Stack은 LIFO(Last In First Out), 후입선출 알고리즘으로, 마치 상자를 연속해서 쌓아두듯이 바닥부터 쭉 쌓아 나가며, 가장 위에 있는 상자를 가장 먼저 꺼내는 방식의 알고리즘이며, Queue는 반대로 FIFO(First In First Out), 선입선출 알고리즘으로, 가장 먼저 들어온 데이터를 가장 빨리 꺼내는 것으로, 운영체제의 프로세스 스케줄링 작업 등에 사용됩니다. Stack은 가장 마지막에 있는 데이터에 대한 조회/삽입/삭제의 시간 복잡도가 O(1)이며, 다른 데이터에 작업할 경우 O(N)입니다. 반대로 Queue는 가장 앞에 있는 데이터에 대한 조회/삽입/삭제의 시간 복잡도가 O(1)이며, 다른 데이터에 작업할 경우 O(N)입니다.

 

Tree

대표적인 비선형 자료 구조로, 나뭇가지 모양으로 데이터를 저장하는 방식입니다.

 

트리 관련 용어

루트(root) : 트리 구조 중 최상위에 존재하는 노드

노드(node) : 트리에서 각각의 구성 요소

레벨(level) : 트리에서 각각의 층을 나타내는 단어(루트 노드 : 0)

형제 노드(sibling) : 같은 레벨의 노드

간선(edge) : 노드와 노드를 연결하는 선

부모 노드(parent node) : 한 노드를 기준으로 바로 상위에 존재하는 노드

자식 노드(child node) : 한 노드를 기준으로 바로 하위에 존재하는 노드

높이(heigh) : 트리 중 최고 레벨

 

이진 트리

자식 노드의 개수를 최대 2개로 제한하는 노드

 

자세한 내용은 이 링크(https://readerr.tistory.com/35)를 통해 봐주시면 좋을 것 같습니다.

 

Hash

해시는 Key와 Value를 갖는 자료구조로, 배열로 예를 들자면 arr[0] = 10이라는 값이 저장되어 있다고 가정을 해보았을 때, 이를 해시 용어로 바꾸면 0이라는 인덱스를 key, 10이라는 값을 value로 볼 수 있습니다.

그런데 특이한 점은, 해시 자료구조에서의 key는 단순 숫자로 된 인덱스뿐만 아니라, 문자, 문자열 등 원하는 자료형을 넣을 수 있습니다. 예를 들어 ten이라는 key로 10이라는 value를 얻을 수 있죠.

이는 우리가 지정해준 key를 해시코드라는 것으로 변환한 후에 해당 해시코드를 통해 값이 저장될 위치를 찾아 저장하고, 나중에 다시 조회할 경우에 다시 key를 해시코드로 변환하여 그 위치를 찾아 값을 꺼내는 방식입니다.

아주 획기적이게도, key를 알고 있는 경우에 조회/삽입/삭제가 모두 O(1)입니다. 하지만 key를 알지 못하는 경우에는 처음부터 끝까지 값을 찾아봐야 하기 때문에 O(N)이죠.

 

Graph

그래프 또한 트리와 같이 비선형 자료구조이기 때문에 트리와 비교하여 설명을 하는 수밖에 없을 것 같습니다. 트리는 무조건 부모와 자식 관계를 갖고 있으며, 위와 아래의 방향성을 가지고 있죠. 하지만 그에 비해 그래프가 갖는 특징은 다음과 같습니다.

1. 부모-형제 개념이 존재하지 않는다.
2. 방향성에 대한 제약이 없다(양방향, 단방향).
3. 연결 상태를 필수적으로 갖지 않아도 된다.
4. 망형(네트워크형) 모델을 사용한다.

 

용어

방향 그래프 : 간선의 방향이 존재하는 그래프. 무방향 그래프에서는 양방향으로 이동이 가능.

연결 그래프 : 두개 이상의 정점이 연결되어 있는 그래프

사이클 그래프 : 특정 노드의 경로가 시작-종료지점이 동일한 그래프

완전 그래프 : 그래프 내 모든 정점이 서로 연결되어 있는 그래프

 

사용도

지하철 목적지 최단거리 알고리즘 DFS BFS

 

구현 방법

(사용되는 자료구조 차이) 인접 리스트 인접 행렬