자료구조란? 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등을 연구 분석하는 것 선형 구조(Linear Structure) 배열(Array) 선형 리스트(Linear List) 스택(Stack) 큐(Queue) 데크(Deque) 비선형 구조(Non-Linear Structure) 트리(Tree) 그래프(Graph) 자료구조의 활용 정렬(Sort) 검색(Search) 인덱스(Index) 배열(Array) 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합 정적인 자료구조 데이터 삭제 시 삭제된 공간이 빈 공간으로 남아있어 메모리의 낭비가 발생함 반복적인 데이터 처리 작업에 적합 선형 리스트(Linear L..

이진 탐색 트리의 목적 이진 탐색 + 연결 리스트 이진 탐색 : 탐색에 소요되는 시간복잡도는 O(logN), but 삽입, 삭제가 불가능 연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), but 탐색하는 시간복잡도가 O(N) ⇒ 이 두가지를 합하여 장점을 모두 얻는 것이 '이진탐색트리' ⇒ 즉, 효율적인 탐색 능력을 가지고, 자료의 삽입 삭제도 가능하게 하기 특징 각 노드의 자식이 2개 이하 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼 중복된 노드가 없어야 함 중복이 없어야 하는 이유 검색 목적 자료구조인데, 굳이 중복이 많은 경우에 트리를 사용하여 검색 속도를 느리게 할 필요가 없음 (트리에 삽입하는 것보다, 노드에 count 값을 가지게 하여 처리하는 것이 훨씬 효율적) 이진탐..

트리 트리는 값을 가진 노드와 이 노드들을 연결해주는 간선(Edge)으로 이루어져있음 그림 상 데이터 1을 가진 노드가 루트(Root) 노드 모든 노드들은 0개 이상의 자식(Child) 노드를 갖고 있으며 보통 부모-자식 관계로 부름 트리의 특징 트리에는 사이클이 존재할 수 없음 (만약 사이클이 만들어진다면, 그것은 트리가 아니고 그래프) 모든 노드는 자료형으로 표현이 가능 루트에서 한 노드로 가는 경로는 유일한 경로 뿐 노드의 개수가 N개면, 간선은 N-1개를 가짐 트리 순회 방식 1. 전위 순회(pre-order) 각 루트(Root)를 순차적으로 먼저 방문하는 방식 (Root → 왼쪽 자식 → 오른쪽 자식)1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14..