정의무방향이면서 사이클이 없는 연결 그래프. 특징계층 형태로 이루어져 있고, 최상위 노드를 제외한 모든 노드가 하나의 부모 노드를 가지고 있는 특별한 그래프V개의 정점을 가졌을 때, V-1개의 간선을 가지고 있다.임의의 두 점을 연결하는 Simple Path(시작 노드부터 도착 노드까지 중복되는 노드가 없는 경로)가 유일하다.각 노드마다 최대 두 개의 자식을 가질 수 있는 트리를 이진 트리라고 한다. 이진 트리의 순회레벨 순회 : 계층 순으로 방문해 나가는 방법. BFS 순회와 동일하다.전위 순회(Preorder Traversal) : 현재 노드 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 방문해 나가는 방법. DFS 순회와 동일하다.중위 순회(Inorder Traversal) : 왼쪽 서브트리 - 현재..

정의정점과 두 정점을 잇는 간선으로 이루어진 자료구조. 자료 사이의 연결 관계를 설정해야 하는 상황에서 유용하게 활용된다. 특징방향성 : 방향성의 유무에 따라 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 나뉜다.무방향 그래프의 간선이 양방향 도로라면, 방향 그래프의 간선은 일방통행 도로이다.즉, 방향 그래프에서 A  -> B로의 간선이 있다면 B 차수(Degree) : 한 정점이 가진 간선의 개수.방향성 그래프에서는 나가는 방향인 진출차수(Outdegree), 들어오는 방향인 진입차수(Indegree)로 나뉜다.사이클(Cycle) : 임의의 한 정점에서 출발해 자기 자신에게 돌아올 수 있는 경로가 있는지 여부에 따라 순환 그래프(Cycle Graph)와 비순..

정의pop 연산에서 가장 먼저 들어온 원소 대신 우선순위가 가장 높은 원소가 내보내지는 큐. 일반적으로 힙(Heap)을 이용해 구현된다. 특징원소의 추가에 O(logN)의 시간이 걸린다.원소를 삽입한 후 우선순위 큐를 만족할 때까지 계층 이동이 일어나기 때문우선순위가 가장 높은 원소의 확인에 O(1), 우선순위가 가장 높은 원소의 삭제에 O(logN)이 걸린다.원칙적으로 가장 높은 원소의 확인과 삭제만이 가능하다.최상위 원소 삭제 후 다시 우선순위 큐를 만족할 때까지 계층 이동이 일어난다.이진 트리의 모양을 띠고 있다.이진 탐색 트리와 다른 점은 이진 탐색 트리가 왼쪽 자식이 자신보다 작고 오른쪽 자식이 자신보다 커야 한다면, 우선순위 큐는 왼쪽, 오른쪽 자식 모두 자신보다 우선순위가 낮으면 된다.최소 ..

정의왼쪽 서브 트리의 모든 값이 부모 노드보다 작고, 오른쪽 서브 트리의 모든 값이 부모 노드보다 큰 이진 트리서브 트리 : 자식 노드로부터 뻗어나가는 하위 트리이진 트리 : 자식이 최대 2개까지 있는 트리 구조 특징삽입, 삭제, 탐색, 갱신 모두 O(logN)의 시간이 걸린다.단, 한쪽 부분에 값이 몰리는 편향이 발생할 수 있는데, 이 편향이 심해질수록 성능이 저하된다.삽입 시 자동으로 원소가 크기 순으로 정렬되어 저장된다.특정 노드보다 작거나 큰 최초의 노드가 무엇인지 O(logN)에 알아낼 수 있다.편향된 이진 트리를 균형 있게 다시 배치해 편향을 해소한 트리를 자가 균형 트리라 한다.대표적으로 AVL트리와 Red Black 트리가 있다.O(N^2)보다 빠른 속도로 데이터의 대소 관계가 필요한 경우..

정의키에 대응되는 값을 저장하는 자료구조.해시 함수를 통해 키를 해시 값으로 변환한 뒤, 테이블에서 그 값에 해당하는 인덱스에 배치해 데이터를 관리한다. 특징삽입, 삭제, 검색, 갱신에 전부 O(1)의 시간이 걸린다.단, 서로 다른 키가 같은 해시 값을 갖게 되면 충돌이 발생하게 되는데 이 충돌이 빈번해질 경우 성능이 저하된다.모든 키의 해시 값이 같은 최악의 경우 O(N)의 시간이 걸리게 된다.때문에 합리적인 해시 함수를 사용해 각 키의 해시 값을 최대한 고르게 퍼뜨려야 성능을 향상시킬 수 있다일단 충돌이 발생한 경우에 대한 대표적인 대처 방법은 Chaining과 Open Addressing이 있다.Chaining : 각 인덱스마다 연결 리스트를 두고 충돌 발생 시 해당 연결 리스트에 삽입해 충돌을 회..

정의양쪽 끝 모두에서 데이터를 넣고 뺄 수 있는 자료구조 특징요소를 추가하고 제거하는 데 O(1)의 시간이 걸린다.무조건 한쪽 끝에서 요소를 넣거나 빼기 때문에한쪽 끝의 요소를 확인하는 데 O(1)의 시간이 걸린다.원칙적으로 양쪽 끝의 요소만 확인할 수 있다.

정의한쪽 끝에서 데이터를 넣고 다른 한쪽 끝에서 데이터를 뺄 수 있는 자료구조 특징먼저 들어온 데이터가 가장 먼저 처리되는 FIFO(선입선출) 구조이다.요소를 추가하거나 제거하는 데 O(1)의 시간이 걸린다.무조건 맨 뒤에 요소를 넣고 맨 앞에서 빼기 때문에맨 앞(또는 맨 뒤)의 요소를 확인하는 데 O(1)의 시간이 걸린다.원칙적으로 맨 앞(또는 맨 뒤)의 요소만 확인이 가능하다.

정의한쪽 끝에서만 데이터를 넣고 뺄 수 있는 자료구조 특징먼저 들어온 데이터가 가장 늦게 나갈 수 있는 FILO(선입후출) 구조이다.요소를 추가하거나 제거하는 데 O(1)의 시간이 걸린다.무조건 맨 뒤에서 요소를 넣고 빼야 하기 때문에맨 뒤(최상단)의 요소를 확인하는 데 O(1)의 시간이 걸린다.원칙적으로 맨 뒤의 요소만 확인이 가능하다.다만, 배열로 스택을 구현하면 스택 중간의 원소도 확인이 가능하게 구현할 수 있다.