Coding Diary

1. 정의 완전 이진 트리로 최소 힙이라면 작은 값이 위쪽에 있고 최대 힙이라면 큰 값이 위쪽에 있다. 즉, 최소 힙이라면 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같다. 최대 힙이라면 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같다. 2. 특징 우선순위큐를 위해 사용되는 자료구조 중복된 값을 허용한다 3. 구현 배열로 구현한다 구현의 용이성을 위해 트리의 인덱스를 1로 시작한다 왼쪽 자식의 인덱스 = 부모 인덱스 * 2 오른쪽 자식의 인덱스 = 부모 인덱스 * 2 + 1 부모의 인덱스 = 자식의 인덱스 / 2 4. 연산 1) 삽입 새로운 요소가 들어오면 완전 이진 트리의 맨 뒤에 일단 삽입을 한다 삽입한 새로운 노드를 부모와 비교해가면서 최소 힙 혹은 최대 힙에 맞게 교환해 나간다 ..

1. 개념 각 노드의 자식 노드의 개수가 2 이하로 구성돼 있는 트리이다. 2. 종류 1) 편향 이진 트리 노드들이 한쪽으로 편향돼 생성된 이진트리 이렇게 저장된 이진 트리는 탐색 속도가 저하되고 공간이 많이 낭비된다 2) 포화 이진 트리 트리의 높이가 모두 일정하며 리프 노드가 꽉찬 이진 트리 3) 완전 이진 트리 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고 마지막 레벨은 왼쪽부터 채워진 트리 4) 이진 탐색 트리 루트보다 작은 값은 왼쪽에 위치, 루트보다 큰 값은 오른쪽에 위치하도록 하여 노드를 저장 데이터를 효율적으로 저장하고 검색, 삭제할 수 있다. 3. 트리의 노드와 배열 인덱스의 상관관계 루트 노드 인덱스 = 1 부모 노드 인덱스 = 현재 노드 인덱스 / 2 (현재 노드가 루트가 아니..

1. 개념 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조. 각 노드는 문자 혹은 문자열의 한 글자를 나타낸다. 또한, 각 노드는 자식을 가지고 있을 수 있는데, 이는 각 노드의 다음 문자를 나타낸다. 2. 특징 루트 노드는 항상 공백이다. N진 트리의 형식을 가진다. 문자 종류에 따라 N이 결정된다. 알파벳은 26개의 문자로 이루어져 있기 때문에 26진 트리 형태를 갖게 된다. 즉 부모 노드가 자식을 최대 26개까지 가질 수 있다는 것이다. 각 문자의 접두사를 공유하기 때문에 검색이 빠르다. 트리 형태로 문자를 저장하기 때문에 삽입과 삭제 연산이 빠르다. 조건을 만족한다면 상수시간 안에도 가능하다. 3. 구현 // 트라이에서 사용하는 노드 정의 class tNode{ tNode[] ..

1. 개념 노드와 에지로 연결된 그래프의 특수한 형태. 2. 특징 순환 구조를 가지고 있지 않다. 1개의 루트 노드가 존재한다. 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다. 트리의 부분 트리도 트리의 모든 특징을 따른다. 3. 트리의 구성 요소 1) 루트 노드 2) 부모 노드 3) 자식 노드 4) 에지 5) 리프 노드 6) 서브 트리 4. 구현 1) 그래프 이용 그래프 구현을 이용해서 구현하면 된다. 인접 리스트 사용. 동적으로 크기 조정이 가능하다. 연결리스트로 구현되기 때문에 노드의 삽입과 삭제가 쉽다. 특정 위치의 노드에 접근하기 위해서 연결리스트를 순회해야 해서 접근 시간이 오래 걸린다. 다음 노드를 가리키는 정보를 저장해야 해서 메모리 사용량이 증가할 수 있다. adjList = ..

1. 개념 정점(노드)과 간선(에지)으로 이루어진 자료구조. 정점은 고유한 식별자를 가지고 있고, 간선은 정점들끼리의 관계를 나타낸다. 2. 종류 1) 방향 그래프 간선에 방향성이 있는 그래프를 의미한다. A에서 출발해서 B로 가는 간선이 존재한다면 이는 A에서 B로 가는 방향을 가진 간선이고, 이러한 정점과 간선을 모아 놓으면 방향 그래프이다. A에서 B로는 갈 수 있지만, B에서 A로 가는 길은 없다. 2) 무방향 그래프 간선에 방향이 없다. A에서 B가 연결되어 있으면 출발과 도착이 없고 그냥 둘이 연결 된 거다. A에서 B로 갈 수 있고, B에서 A로도 갈 수 있다. 3) 가중치 그래프 A와 B가 연결이 되어 있는데 그 연결된 간선에 가중치가 부여된 것이다. 이러한 가중치는 두 정점 사이의 거리,..

1. 에지 리스트 1) 개념 에지 리스트는 에지를 중심으로 그래프를 표현한다. 2차원 배열에 각 에지의 출발 노드와 도착 노드를 저장한다. 만약 가중치가 있는 에지일 경우 각 에지의 출발 노드, 도착 노드, 가중치를 저장한다. 2) 종류 ⓛ 가중치가 없는 에지 int[2][6] edgeList = {{1,2},{1,3},{2,5},{2,4},{3,4},{4,5}}; ② 가중치가 있는 에지 int[2][6] edgeList = {{1,2,4},{1,3,1},{2,5,2},{2,4,1},{3,4,7},{4,5,4}}; + 만약 방향이 없는 에지면 {1,2}와 {2,1}은 같은 것이니 둘 중 하나만 저장하면 된다. 3) 특징 구현하기가 쉽다 에지만 딱 나와있기 때문에 특정 노드가 어떤 에지와 연결되어 있는지,..

1. 개념 일반적인 큐의 구조를 가짐. 하지만 먼저 들어온 것이 먼저 나가는 구조가 아님. 들어올 때 우선순위에 맞게 정렬이 되어 들어오고, 들어온 것들 중 정해놓은 우선순위가 가장 높은 것이 먼저 나가는 구조. 나가고 나서 우선순위에 맞게 다시 정렬이 됨. 2. 특징 값을 비교해야 하므로 null을 허용하지 않음 값을 비교해야 하므로 우선순위 큐에 삽입될 객체들은 Comparable Interface에 있는 compareTo 메서드가 구현되어 있는 객체여야 함. 내부 구조는 이진트리 힙으로 되어 있음 값이 들어올 때 마다 일단 이진트리 맨 마지막에 값을 넣음 그리고 부모 노드와 비교해가며 우선순위에 맞게 정렬을 진행함 값이 나갈 때는 트리의 루트를 이진트리 맨 마지막 노드와 바꿈 맨 마지막을 나가게 하..

1. 개념 한 쪽에서는(맨 뒤) 넣을 수만 있고, 다른 한 쪽에서는(맨 앞) 지울 수만 있는 자료구조 2. 특징 선입선출 방식이다. 즉 먼저 들어온 게 먼저 나간다 3. 자바에서 구현 Queue의 인터페이스가 있고, 이 인터페이스를 구현한 클래스를 사용해야 한다. 그 클래스에는 LinkedList ArrayDeque PriorityQueue 가 있다. 4. 연산 1) offer Enqueue 수행. 큐가 꽉 차 있으면 false 리턴 2) add Enqueue 수행. 큐가 꽉 차 있으면 예외 발생 3) poll Dequeue 수행. 큐가 비어 있으면 null 리턴 4) remove Dequeue 수행. 큐가 비어 있으면 예외 발생 5) clear 한 번에 모든 요소 제거 6) peek 큐의 첫 번째 데이..

1. 개념 앞으로 넣을 수 있고 뺄 수 있으면서, 뒤로도 넣을 수 있고 뺄 수 있는 자료구조 2. 특징 스택과 큐의 특징을 모두 가질 수 있음 3. 자바에서 구현 덱의 여러 연산을 모아 놓은 인터페이스가 있고, 이 인터페이스를 실제로 구현한 여러 클래스가 있다. ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 가 클래스의 종류며 구현 방법에 따라 종류가 나뉜다. 1) ArrayDeque array로 구현 내부 배열의 크기가 resizable 함 용량 제한이 없음, 기본 크기를 16으로 하고 용량 넘어가면 2배씩 증가시킴 Thread-Safe하지 않아서 멀티 쓰레드 환경에서는 문제가 있음 null 추가 불가 끝에 삽입, 삭제만 할 경우..