LeeHyojin Blog LeeHyojin Blog

Tree 트리는 노드로 구성된 계층적 자료구조입니다. 최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 트리 구조를 구현할 수 있습니다. Array, Linked List, Stack, Queue는 라인처럼 생긴 일직선 데이터 구조인데 Tree는 부모 자식 관계를 가지는 구조입니다. Tree는 계층적 자료구조라고 했는데 이 것을 가능하게 한 것은 노드가 하나 이상의 child를 갖기 때문입니다. 노드중에는 부모를 아는경우도 있고 자식만 아는 경우도 있습니다. 또한 어떠한 순서에 의해서 데이터가 관리되는 경우도 있고, 데이터가 마구 섞여있는 경우도 있습니다. ※ 트리의 용어 정리 루트 노드 (Root) : 부모가 없는 노드, 트리는 하나의 ..

Hash Table ( 해시 테이블 ) 해시 테이블(해시 맵이라고도 합니다.)은 연관배열 구조를 이용하여 키(key)에 결과 값(value)을 저장하는 자료구조 입니다. 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키를 "해시 함수"(Hash Function)라는 함수를 통해 특정 숫자값의 인덱스로 변환합니다. 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지합니다. 연관배열 구조( associative array )란 키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조 입니다. 따라서 키(key)를 이용하여 값(value)을 도출할 수 있습니다. 연관배열 구조는 다음의 명령들을 지원하고 이 명령들은 해시테이블에서도 동일하게 적용..

그래프는 노드(Node, 또는 정점 -vertex- 라고도 부릅니다), 그리고 노드와 노드를 연결하는 간선(edge)으로 구성된 자료구조 입니다. 그래프는 무방향(undirected)일 수 있습니다. 이는 간선에 의해 연결된 2개의 노드가 대칭 일 수 있다는 의미입니다. 한편 방향성(directed)을 가질 수도 있는데, 이는 비대칭 관계를 의미합니다. 그래프 G = ( V, E )로 정의하는데, V( Vertex )는 그래프에 있는 정점들의 집합을 의미하고 E( Edge )는 정점을 연결하는 간선들의 집합을 의미합니다. 그래프 용어 정점 (Vertex) : 연결한 객체들을 의미 간선 (Edge) : 정점들을 연결하는 선 차수 (Degree) : 정점에 연결되어 있는 간선의 수, 방향 그래프에서 진입 /..

Linked List ( 연결 리스트 ) 연결 리스트는 그 크기가 동적인 자료구조로, 자료구조를 구성하는 요소( Node )노드의 연결로 이루어진 자료구조 입니다. 연결리스트의 어떠한 임의의 지점에 데이터의 추가와 삭제를 할 경우, O(1) (상수 시간)의 시간 복잡도를 갖습니다. 추가와 삭제에 대해 O(n) (선형 시간)의 복잡도를 갖는 배열과는 다릅니다. 다만 이 추가와 삭제 속도에 대한 대가로, 연결 리스트의 각 노드는 인덱스를 갖지 않습니다. 그래서 어떤 특정 데이터를 연결 리스트에서 검색하고자 할 경우, 처음부터 전체 연결 리스트를 훓어야 하며, 이는 O(n) (선형 시간)의 복잡도를 필요로 합니다. 따라서 Linked List는 그 위치들이 각각 흩어져 있기 때문에 서로 연결되어 있어야 합니다..

Stack 스택( Stack ) 이란 쌓아올린 다는 것을 의미합니다. 쌓여져 있는 접시 더미와 같이 차곡차곡 쌓아 올린 형태의 자료구조를 말합니다. 접시를 쌓을 때 맨 위에 차곡차곡 쌓고 가져올 때에는 위에서부터 하나씩 가져오는 것과 같은 원리입니다. Stack의 특징 스택은 위의 사진처럼 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있습니다. top은 가장 위에 있는 자료가 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 됩니다. 스택에서 자료를 삭제하거나 가져올 때에도 top을 통해서만 가능합니다. 스택에서 top을 통해 삽입하는 연산을 push, top을 통해 삭제하거나 가져오는 연산을 pop 이라고 합니다. 따라서..