뽀블로그

해시 테이블 key와 value로 데이터를 저장하는 자료구조 하나의 해시 함수를 이용해 저장한다 ex) h(x) = xmod13 → h(7) = 7, h(13) = 0 해당 원소의 해시값을 해시 함수를 이용해 계산한다. (= 해싱) 이 해시값을 주소로 하는 위치에 원소를 저장한다. 저장 후에 검색을 할 때도 원소의 해시값을 계산해 바로 해당 위치로 이동한다.임의의 원소를 해시 테이블에 저장하려면 → 이렇게 해시 테이블은 원소를 저장할 위치를 상수 시간에 계산할 수 있다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라한다. 해시 함수란? 임이의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수 좋은 해시함수 계산이 간단해야 한다. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. → 해시충돌 발생..

우선순위 큐(Priority Queue) 일반적인 큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 이런 큐의 특성과 달리 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 일정한 규칙에 따라 우선순위를 선정하고 우선순위가 가장 높은 데이터가 가장 먼저 나오게 된다. heap으로 구현되어 있다. 우선순위 큐의 이용 사례 시뮬레이션 시스템 네트워크 트래픽 제어 운영 체제에서의 작업 스케쥴링 수치 해석적인 계산 우선순위를 구현할 수 있는 방법 : Array, LinkedList, heap heap으로 구현된 이유 : 힙의 경우 삭제나 삽입 과정에서 모두 부모와 자식 간의 비교만 계속 이루어진다. 이진 트리의 높이가 하나 증가할 때마다 저장 가능한 자료의 갯수는 2배 증가하며, 비교 연산 횟수..

Stack 입력과 출력이 한 곳(방향)으로 제한 LIFO(Last In First Out, 후입선출) : 마지막 입력 데이터가 먼저 출력 자바에서는 Vector로 구현 (ArrayList성질이 비슷하다) 함수 push() : Stack에 객체를 저장합니다. pop() : Stack의 맨 위에 저장된 객체를 꺼냅니다. peek() : Stack의 맨 위에 저장된 객체를 반환합니다. Stack에서 꺼내지는 않습니다. 비었을 때 null을 반환합니다. empty() : Stack이 비어있는지 알려줍니다. 있으면 true, 없으면 false를 반환합니다. search() : Stack에서 주어진 객체를 찾아서 그 위치를 반환합니다. (배열과는 달리 1부터 시작합니다.) clear() : Stack의 모든 객체를..