개발일지

목차 이진 탐색 트리 각 노드의 값이 왼쪽 서브트리에 속한 모든 노드의 값보다 크고 오른쪽 서브트리에 속한 모든 노드의 값보다 작은 이진 트리이다. 이진 탐색 트리는 데이터를 효율적으로 검색할 수 있다. 원하는 값을 찾을 때까지 현재의 노드값보다 찾고자하는 값이 작으면 왼쪽으로 움직이고, 크면 오른쪽으로 움직인다. 이렇게 원하는 값을 더 빠르게 찾을 수 있게 된다. 중복값을 허용하지 않는다. 이진 탐색 트리와 힙의 차이 이진 탐색 트리 힙 정렬 방식 정렬된 데이터 저장 일정한 순서(최소힙 또는 최대 힙) 중복 중복 허용 안함 중복 허용 주 용도 - 연산에 특화(데이터 삽입,삭제,검색에 효율) - 특정 트리를 빠르게 탐색하는데 유용 최대 또는 최소값을 빠르게 찾을 때 유용 이진 탐색 트리 삽입, 삭제 과정..

목차 힙이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙을 사용하는 이유? 최솟값이나 최댓값을 찾기 위해 배열을 사용하면 Ο(n)만큼 시간이 걸린다. 하지만 힙을 사용하면 O(logn)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다. 우선순위 큐와 같이 최댓값 또는..

목차 트리란? 트리 (Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다. 트리는 또한 트리 내에 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 하다. 트리 구조에서 사용되는 기본 용어 노드 (Node) 트리를 구성하고 있는 기본 요소 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음. A, B, C, D, E, F, G, H, I, J 간선 (Edge) 노드와 노드 간의 연결선 루트 노드 (Root Node) 트리 구조에서 부모가 없는 최상위 노드 root node : A 부모 노드 (Parent Node) 자식 노드를 가진 노드 H, I에 부모 노드는 D 자식 노드 (Child node) 부모 노드의 하위 노드 노드 D의 자..

목차 그래프란? 그래프는 정점(node 또는 vertex)과 간선(edge)로 이루어진 자료구조이다. 그래프의 활용 그래프는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다. 그래서 그래프는 실생활에서 지하철 노선도 최단 경로, 도로, 선수 과목 등에 쓰이고 있다. 그래프 관련용어 간선(Edge) : 정점(노드)를 연결하는 선. 링크(Link) 또는 브랜치(branch) 로도 불린다. 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점을 의미한다. 단순 경로(simple path) : 경로 중에서 반복되는 정점이 없는 경우를 의미한다. 한붓 그리기와 같이 같은 간선을 지나가지 않는 경로를 의미한다. 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수..

목차 스택이란 '쌓다' 라는 의미를 가지고 있는 스택(Stack)은 그 의미와 같이 데이터를 차곡차곡 쌓아올린 형태로 자료를 구성한다. 후입선출(Last-in First-out)의 자료구조이다. 앞자만 따서 LIFO 구조라고 하며, 마지막에 들어온 것이 먼저 나간다라는 뜻이다.(입구와 출구가 같은 자료구조) 입구와 출구가 하나밖에 없으니 데이터의 삽입과 삭제가 한 방향에서만 이루어진다. 스택에서는 흔히 데이터의 삽입 연산을 push, 삭제 연산을 pop 이라고 한다. 스택 활용 예시 웹 브라우저 방문기록(뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다. 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다. 실행 취소(undo) : 가장 나중에 실행된 것 부터 실행을 취소한다. 후위표기..