본문 바로가기

🖋️ 자료구조와 알고리즘26

이전 1 2 3 4 다음

[해시 테이블] 해시 테이블, 해시 함수 해시 테이블은 자료를 검색, 삽입, 삭제하는 데 평균시간이 가능하게 하여 극단적 효율에 다다른 자료구조 키 자신의 값에 따라 자리가 결정됨 해시 테이블은 키가 저장될 자리를 키의 '값'으로 결정하는 자료구조 해시 함수는 임의의 킷값을 입력으로 받아 주소 중 한 값을 리턴함(리턴값=해당 키를 저장하는 자리) 해시 함수 나누기의 방법 곱하기 방법 충돌 어떤 키가 이미 자리 잡고 있는 상태에서 다른 키가 삽입을 시도하는 것 동일한 주소에 2개 이상의 키가 해싱되는 상황 충돌 해결방법 체이닝 : 충돌을 일으킨 키들을 연결 리스트로 관리하는 방법 개방 주소 방법 : 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결하는 것 검색 시간 체이닝, 개방 주소 방법으로 검색할 때의 기대시간 적재율 해시 테이블에 원.. 2023. 11. 30.

[메서드] Queue 인터페이스를 구현한 클래스의 메서드(LinkedList, PriorityQueue) Queue 인터페이스를 구현한 클래스 LinkedList 는 일반적인 큐 연산 외에 리스트 기능과 양방향 큐 기능을 제공하는 반면 PriorityQueue 는 요소들이 우선순위에 따라 정렬되는 특성을 가짐 2023.11.21 - [🖋️ 자료구조와 알고리즘/알고리즘 이론] - [힙] 우선순위 큐 : 힙 LinkedList LinkedList는 Queue 인터페이스의 모든 메서드를 구현하며, 추가로 Deque 인터페이스의 메서드를 제공함 [ 이중 연결 리스트를 기반으로 하기 때문에, Queue 인터페이스 외에 추가로 제공하는 메서드 ] void addFirst(E e): 리스트의 앞쪽에 요소를 추가 void addLast(E e): 리스트의 뒤쪽에 요소를 추가 boolean offerFirst(E e): 리.. 2023. 11. 30.

[메서드] Queue 인터페이스 메서드 2023.11.21 - [🖋️ 자료구조와 알고리즘/알고리즘 이론] - [큐] 배열 기반 큐와 연결리스트 기반 큐 boolean add(E e): 설명: 지정된 요소를 큐의 끝에 추가합니다. 만약 큐가 더 이상 요소를 추가할 수 없는 상태라면 (예: 용량 제한이 있는 큐의 경우), 이 메서드는 IllegalStateException을 던집니다. 반환값: 요소가 성공적으로 추가되면 true를 반환합니다. boolean offer(E e): 설명: 지정된 요소를 큐의 끝에 추가합니다. add 메서드와 달리, 큐가 추가를 수용할 수 없는 경우에 false를 반환하고 예외를 던지지 않습니다. 반환값: 요소가 성공적으로 추가되면 true, 그렇지 않으면 false를 반환합니다. E remove(): 설명: 큐의 맨.. 2023. 11. 30.

[메서드] ArrayDeque 클래스 메서드 ArrayDeque 클래스 ArrayDeque 는 배열을 기반으로 하는 더블 엔드 큐(double-ended queue)를 구현한 Java 클래스 ArrayDeque 는 Queue 인터페이스와 Deque 인터페이스를 구현하며, 스택과 큐의 기능을 모두 제공함 생성자 ArrayDeque(): 빈 ArrayDeque를 생성합니다. ArrayDeque(int numElements): 지정된 초기 용량을 가진 ArrayDeque를 생성합니다. ArrayDeque(Collection c): 지정된 컬렉션에 있는 요소를 모두 큐에서 제거합니다. boolean retainAll(Collection c): 지정된 컬렉션에 없는 모든 요소를 큐에서 제거합니다. boolean contains(Object o): 큐가 지정.. 2023. 11. 30.

[메서드] Stack 클래스 메서드 2023.11.21 - [🖋️ 자료구조와 알고리즘/알고리즘 이론] - [스택] 배열 기반 스택과 연결 리스트 기반 스택 생성자 Stack(): 설명: 새로운 빈 스택을 생성합니다. E push(E item): 설명: 지정된 항목을 스택의 맨 위에 추가합니다. 이 메서드는 Vector 클래스의 addElement 메서드와 동일한 효과를 가집니다. 반환값: 스택에 추가된 항목입니다. E pop(): 설명: 스택의 맨 위에 있는 항목을 제거하고 반환합니다. 스택이 비어 있으면 EmptyStackException을 던집니다. 반환값: 제거된 맨 위의 항목입니다. E peek(): 설명: 스택의 맨 위에 있는 항목을 제거하지 않고 반환합니다. 스택이 비어 있으면 EmptyStackException을 던집니다. 반.. 2023. 11. 30.

[메서드] Map 인터페이스 메서드 모음 2023.11.14 - [🖥️ 백엔드/Java] - [ch.11] 컬렉션 프레임워크 Map int size(): 맵에 저장된 키-값 쌍의 개수를 반환합니다. boolean isEmpty(): 맵이 비어있는지 여부를 반환합니다. 맵이 비어있으면 true, 그렇지 않으면 false를 반환합니다. boolean containsKey(Object key): 맵에 특정 키가 존재하는지 여부를 반환합니다. 키가 존재하면 true, 그렇지 않으면 false를 반환합니다. boolean containsValue(Object value): 맵에 특정 값이 존재하는지 여부를 반환합니다. 값이 존재하면 true, 그렇지 않으면 false를 반환합니다. V get(Object key): 지정된 키에 연결된 값을 반환합니다. .. 2023. 11. 30.

[트리] 균형 검색 트리 (AVL트리, 레드-블랙트리, B-트리) 균형 이진 검색 트리 최악의 경우에도 이진 트리의 균형이 잘 맞도록 유지해서 작업들이 항상 O(logn)시간을 보장함 AVL 트리 자가 균형, 높이 균형 어떤 노드도 좌서브 트리와 우서브 트리의 높이 차가 1보다 크지 않은 상태로 유지되는 이진 검색 트리 회전 연산 균형이 깨진 서브 트리 중 가장 낮은 곳에 있는 것부터 수선을 시작함 단일회전, 이중회전 AVL트리 운영 삽입과 삭제 새로운 노드를 삽입하거나 노드를 삭제할 때, AVL 트리는 불균형도를 체크하고 필요에 따라 회전을 수행하여 균형을 재조정 불균형도 체크 각 노드는 자신의 왼쪽과 오른쪽 자식 트리의 높이를 기반으로 불균형도를 계산. 불균형도가 1을 초과하면 균형이 깨진 것으로 간주 회전 유형 균형이 깨진 경우, LL, RR, LR, RL 네 가.. 2023. 11. 27.

이전 1 2 3 4 다음

티스토리툴바