Coding Ha

미완/백준 24174 힙 정렬

힙(Heap) 문제 https://www.acmicpc.net/problem/24174 24174번: 알고리즘 수업 - 힙 정렬 2 2 5 1 4 3(heapify(A, 2, 5)) -> 2 3 1 4 5(heapify(A, 1, 5)) -> 1 3 2 4 5(A[1] A[5]) -> 5 3 2 4 1(heapify(A, 1, 4)) -> 2 3 5 4 1(A[1] A[4]) -> 4 3 5 2 1(heapify(A, 1, 3)) -> 3 4 5 2 1(A[1] A[3]) -> 5 4 3 2 1(heapify(A, www.acmicpc.net 오늘도 서준이는 최소 힙 기반 힙 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 서로 다른 양의 정수..

미완/백준 1158 요세푸스 순열

연결리스트(Linked List) 문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K) - 요세푸스 순열이라고 한다. 예를 들어 (7, 3) - 요세푸르 순열은 이다. N과 K가 주어지면 (N, K..

백준 26008 해시 해킹

해시맵(HashMap) 문제 https://www.acmicpc.net/problem/26008 26008번: 해시 해킹 첫째 줄에 비밀번호의 길이 $N$과 문자 종류의 개수 $M$, 정수 $A$가 주어진다. ($1 \le N, M, A \le 5\,000\,000$) 둘째 줄에 재현이가 알아낸 해시값 정수 $H$가 주어진다. ($0 \le H < M$) www.acmicpc.net 그린닷컴의 운영자 연두는 비밀번호를 평문 그대로 저장하는 과오를 뒤로하고, 이제부터 암호에 해시 함수를 적용해 저장하려고 한다. 연두가 아는 해시 함수라고는 알고리즘 문제 풀이에 많이 사용되는 롤링 해시 함수밖에 없기 때문에 이것을 응용하여 사용하기로 했다. 그린닷컴의 비밀번호 규칙은 꽤 특이한데, 길이가 정확히 N이어야 하..

해시 테이블_2

연습 코드3 // Practice3 // 해시 충돌 해결 - 개방 주소법 (제곱 탐사법) class MyHashTable3 extends MyHashTable { MyHashTable3(int size) { super(size); } public void setValue(int key, int data) { int idx = this.getHash(key); if(this.elemCnt == this.table.length) { System.out.println("Hash table is full!"); return; } else if (this.table[idx] == null) { this.table[idx] = data; } else { // 충돌 - 제곱 탐사법 int newIdx = idx; /..

해시 테이블_1

해시 테이블(Hash Table) = 해시 맵, 해시 표 - 키(Key), 값(Value)을 대응시켜 저장하는 데이터 구조 : 키를 통해 해당 데이터에 빠르게 접근 가능 - 해싱 : 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정 해시 테이블 구조 키 : 해시 테이블 접근을 위한 입력 값 해시 함수 : 키를 해시 값으로 매핑하는 연산 해시 값 : 해시 테이블의 인덱스 해시 테이블 : 키-값을 연관시켜 저장하는 데이터 구조 해시 충돌 - 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우 : 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우 - 해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있음 해시 충돌 해결 방법 ▶ 개방 주소법(Open Address) -..