자료구조
-
[Data Structure] 연결 리스트와 스킵 리스트카테고리 없음 2020. 8. 11. 19:42
* 연결 리스트(Linked List) 연결 리스트는 일렬로 연결된 데이터를 저장할 때 사용하는 자료구조. 한 노드에는 다음 노드의 주소 정보가 담겨져 있다. 배열과 연결 리스트는 흔히 비교되는 자료구조 형태다. 배열의 경우에는 배열 각 칸들이 물리적으로 한 곳에 모여 있으므로, 크기를 한 번 정하면 늘리거나 줄일 수 없다. 반면, 연결 리스트의 경우 데이터를 중간에 삽입을 하는 것이 용이하다. 가령, A노드와 C 노드 사이에 B 노드를 추가하려는 경우, B 노드의 다음 주소를 C노드로 연결하고, A노드의 다음 주소를 B노드로 연결하면 된다. (관련 알고리즘 문제풀이) 연결 리스트는 주소를 일일이 찾아다녀야 하기 때문에 배열보다 검색 속도가 느릴 수 있다. 반면 위에서 본 것 처럼 데이터를 중간에 추가하..
-
[Data Structure] Tree, Binary Search Tree, Graph카테고리 없음 2020. 2. 10. 14:08
1. 트리(Tree) 트리는 부모-자식의 계층구조를 가진 자료구조를 의미한다. 자식은 여럿일 수 있지만, 부모는 하나라는 특징이 있다. 트리 최상단에 위치한 부모 노드를 루트 노드(Root Node)라고 한다. 그리고, 자식이 없는 노드는 리프 노드(Leaf Node) 혹은 터미널 노드(Terminal Node)라고 한다. 그 외의 노드들은 내부 노드(Internal Node) 라고 한다. 아래 그림에서 루트 노드는 A, 리프 노드는 F, G, H 가 된다. 트리 관련해서 추가적으로 살펴볼 개념은 다음과 같다. - 엣지(Edge) : 노드와 노드를 이어주는 선을 의미한다. 한 노드와 다른 노드와의 관계를 설명한다. - 레벨(Level) : 루트 노드로부터의 거리를 의미한다. 그림의 경우, 레벨 1은:A,..
-
[Data Structure] Stack, Queue카테고리 없음 2020. 2. 9. 20:42
자료를 일정한 규칙에 따라 데이터를 정리하는 것을 자료구조(Data Structure)라고 한다. 자료를 효율적으로 저장하고 관리하기 위해서 자료구조를 알맞게 활용하는 것이 중요하다. 1. 스택 (Stack) 스택은 한 방향에서만 자료를 넣고 뺄 수 있는 구조를 의미한다. Stack의 사전적 의미는 '쌓다' 이다. 스택을 이해하기 위해서는 책상 위에 쌓아 올려진 책을 생각하면 편하다. 스택의 특징은 마지막으로 들어간 요소가, 제일 먼저 나간다는 데 있다. 이를 LIFO(Last In First Out)라고 줄여 말하기도 한다. 그림으로 보면 더욱 간편하다. 2. 큐 (Que)큐는 스택과 달리 양방향으로 열려 있어, 먼저 들어간 데이터가 먼저 나오는 구조를(FIFO, First In First Out)가지..