아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 트리 순회 중위 순회 - 왼쪽, 루트, 오른쪽 순서로 순회 전위 순회 - 루트, 왼쪽, 오른쪽 순서로 순회 후위 순회 - 왼쪽, 오른쪽, 루트 순서로 순회 레벨 순회 - 레벨 순서대로 순회 TrickelUp 완전이진트리에서 레벨 순회식 노드의 위치는 다음과 같은 성질을 가진다. children - 2 * parent + 1 // 또는 // 2 * parent + 2 parent - floor(내림)( (child-1) / 2 ) 이진 힙을 코드로 구현하기 위해서는 배열(0~..)을 만들어 인덱스를 노드 위치로 하여 이러한 규칙을 사용할 수 있다. int lastposition; // 배열에서 어디까지 요소를 넣었는지 기록: 힙이 시작점에서 얼마나 떨..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 트리 (Tree) 가계도처럼 노드를 나무 형태로 연결한 비선형 자료구조를 트리라고 한다. 트리를 구성하고 있는 각각의 기본 요소는 노드로, 노드는 부모, 자식 형태로 이어진다. 루트 (root): 트리의 시작 부분. 부모가 없는 최상위 노드. 루트를 이용해 트리를 탐색한다. 리프, 단말노드 (leaf): 자식 노드가 없는 노드. 간선 (edge): 두 노드를 연결하는 선. 뿌리로부터의 간선의 수에 따라 level을 나눈다. ( 루트는 0 level) 형제 노드(sibling): 같은 부모를 가지는 노드. 힙 (Heap) 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기반으로 한 자료구조이다. 힙에는 두 가지 규칙이 ..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. Resize 해시가 가득 차게되면 테이블의 사이즈를 더 크게 하여 새로운 배열을 만들어 다시 데이터를 넣어주어야 한다. = O(n) 일반적으로 원래 배열의 두 배의 크기로 만들게 된다. public void resize(int newSize){ // 새로운 체인 해시 생성
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. add, remove 해시에 요소를 추가하고 삭제하는 코드. 연결 리스트의 addFirst로 add한다. public boolean add(K key, V value){ if (loadFactor() > maxLoadFactor)// 적재율 확인 resize(tableSize*2);// resize 메소드 - 테이블 크기 2배로 늘이기 // 키와 값을 저장해 놓을 object he 정의 HashElement he = new HashElement(key, value); // he의 index 찾기 int hashval = key.hashCode(); hashval = hashval & 0x7FFFFFFF;// 양수만들기 hashval = hashval..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 재해싱 체인 해시에서도 해시가 너무 많이 찰 경우 크기 조정을 해야 한다. 해시의 크기 조정 과정을 재해싱이라고 한다. 일반적으로, 배열에서 적재율이 높아져 가득 차게 되면 배열의 크기를 두 배로 새로 만들어 모든 요소를 기존의 위치대로 옮긴다. 그러나 체인 해시에서는 이와 같이 이전 위치 그대로 요소를 옮기는 방식을 사용할 수 없다. 테이블의 크기를 키웠기 때문에, 다시 객체를 찾고자 할 때 해싱 과정에서 크기를 최적화하기 위해 테이블 크기만큼 %연산을 하게되면 다른 해시값이 나오기 때문이다. 따라서, 새 테이블에 연결 리스트를 만들어 첫 요소부터 시작하여 모든 요소마다 1. hashCode를 구하고 2. 양수로 변환한 뒤 3. 새 테이블 크기만큼..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. LoadFactor(적재율) 메소드 LoadFactor(적재율)는 해시에 데이터가 얼마만큼 있는지 알려주는 메소드이다. 배열의 크기에 비해 얼마정도 차 있는지를 알기 위합이다. 적재율은 자료 구조에 있는 항목 수를 자료 구조의 크기만큼 나눈 값으로, λ(람다)로 표기한다. (100 배열에 25칸 = 0.25λ) λ의 크기(0 - 비어있음 / 1/2 - 반 차있음 / 1 - 완전히 차 있음)에 따라 해시 테이블의 크기를 조절해야 한다. 해시 충돌을 해결하는 방식에 따라 적재율은 달라지기 때문에 충돌을 해결하는 것이 중요하다. 해시 충돌의 해결 방법 1. 개방 주소법 선형 조사법 (linear probing) 채우려는 공간이 이미 차 있다면, 비어있는 ..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 해시 함수에서의 문자열 문자열 "this"를 해시로 나타내려면, 각 문자를 유니코드로 변환한 후 숫자들을 합하여 나타낼 수 있을 것이다. 그런데 이렇게 변환할 경우, this뿐만 아니라 hits, tish 등 다른 문자열도 같은 숫자로 표현되는 해시 충돌이 발생한다. 여기서 어떤 상수 g를 문자의 위치만큼 제곱한 뒤 그 수를 곱하여 해시충돌을 최소화 할 수 있다. 문자열의 길이가 아주 길다면 subString으로 더 작은 문자열만 사용하여 나타내면 된다. public int hashCode(String s) { // this int g = 31; int hast = 0; for(int i = s.length() -1; i >= 0; i--) // s..
