해시(Hash) 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑함 Lee → 해싱함수 → 5 Kim → 해싱함수 → 3 Park → 해싱함수 → 2 ... Chun → 해싱함수 → 5 // Lee와 해싱값 충돌 결국 데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생 → ‘collisoin’ 현상 ⇒ 그래도 해시 테이블을 쓰는 이유는? 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해 하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해짐 언제나 동일한 해시값 리턴, index를 알면 빠른 데이터 검색이 가능해짐 해..

이진 탐색 트리의 목적 이진 탐색 + 연결 리스트 이진 탐색 : 탐색에 소요되는 시간복잡도는 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..

우선순위 큐 우선순위의 개념을 큐에 도입한 자료구조 데이터들이 우선순위를 가지고 있음 우선순위가 높은 데이터가 먼저 나감 스택은 LIFO, 큐는 FIFO 배열, 연결 리스트, 힙으로 구현 힙 → 삽입 : O(logn), 삭제 : O(logn) 힙(Heap) 완전 이진 트리의 일종 여러 값 중 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조 반정렬 상태 힙 트리는 중복된 값 허용(이진 탐색 트리는 중복값 허용 X) 힙 종류 1) 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 2) 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 구현 힙을 저장하는 표준적인 자료구조는 배열 구현을 쉽게 하기 위해 배..

스택(Stack) 입력과 출력이 한 곳(방향)으로 제한 LIFO(Last In First Out, 후입선출) : 가장 나중에 들어온 것이 가장 먼저 나옴 함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법에 사용 push와 pop할 때는 해당 위치를 알고 있어야 하므로 기억하고 있는 ‘스택 포인터(SP)’가 필요함 스택 포인터는 다음 값이 들어갈 위치를 가리키고 있음 (처음 기본값은 -1) private int sp = -1; 1) push() : 데이터 넣음 public void push(Object o) { if(isFull(o)) { return; } stack[++sp] = o; } 스택 포인터가 최대 크기와 같으면 return 아니면 스택의 최상위 위치에 값을 넣음 2) pop() : 데이터 ..

Array는 index로 빠르게 값을 찾는 것이 가능함 LinkedList는 데이터의 삽입 및 삭제가 빠름 ArrayList는 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느림 배열 int arr[10]; String arr[5]; 선언할 때 크기와 데이터 타입을 지정해야 함 메모리 공간에 할당할 사이즈를 미리 정해놓고 사용하는 자료구조다. 계속 데이터가 늘어날 때, 최대 사이즈를 알 수 없을 때는 사용하기에 부적합 중간에 데이터를 삽입하거나 삭제할 때도 매우 비효율적 특정 인덱스에 새로운 값을 넣어야 한다면 원래 값을 밀어내고 덮어씌워야 함 인덱스가 존재하기 때문에 위치를 바로 알 수 있어 검색이 편함 → 이를 해결하기 위해 나온 것이 List arrayList 배열처럼 크기를 정하지 않아도 됨 배열에서..