S E P H ' S

Hash HashSet에 대해 다루기 전에 Hash에 대한 개념을 먼저 다뤄보도록 하자. Hash는 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환하는 것이다. 그리고 위와 같은 기능을 하는 함수를 해시 함수(Hash Function)이라고 한다. abcd 라는 문자열이 있다면 이를 특정 길이 (ex 256bit, 512bit 등) 의 데이터로 변환시키는 것이다. 만약 특정 길이를 32bit로 고정된다는 가정하에 아래 이미지를 보자. 32bit는 2진수일때 기준이므로, 16진수로 보자면 4bit 당 한 묶음이기 때문에 16진수로 표현하면 8개의 문자를 얻게된다. 즉 해시함수를 돌리기 전 문자열의 길이가 얼마이든지 일정한 길이를 얻는다는 것이다. 실제로 대표적인 해시함수의 SHA계열의 SHA-51..

Set Interface Set은 말그대로 집합이다. 기본적으로 Set 혹은 Set 계열을 구현하는 클래스들은 다음과 같은 공통점이 있다. 중복 요소(원소)를 허용하지 않는다. 저장 순서를 유지하지 않는다. (LinkedHashSet 만 예외) 가장 중요한 특징은 '중복 요소를 허용하지 않는다'는 점이다. Set의 종류 Set은 크게 HashSet, LinkedHashSet, TreeSet으로 나뉜다. HashSet 가장 기본적인 Set 컬렉션의 클래스이다. 입력 순서를 보장하지 않고 순서도 보장되지 않는다. 가장 쉽게 이해할 수 있는 예시로는 게임에서 닉네임 중복확인을 할때이다. 이는 데이터가 정렬될 필요도 없을뿐더러 빠르게 중복되는 값인지만 찾으면 되므로 유용한 방법이 될 수 있다. hash에 의해 ..

2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net BOJ 2042 구간 합 구하기 풀이를 하면서 정리를 시작하게 됐다. 이 문제는 세그먼트 트리에 대해 이해하고 있어야 접근이 가능하다. 우선 세그먼트 트리에 대해서 정리하고 문제 풀이를 시작해보겠다. 세그먼트 트리 (Segment Tree) 특정 구간 내 데이터에 대한 연산(쿼리)를 빠르게 구할 수 있는 트리이다. 예를 들어 특정 구간 합, 최소값, 최대값, 평균값 등을 구하는데 용이하다. 시간 복잡도는..

우선순위 큐(Priority Queue) 힙(Heap) 자료구조를 기반으로 구현된다. 힙은 노드를 활용하여 링크드리스트 처럼 구현하는 방식이 있고 배열을 활용하는 방식이 있는데 힙의 특성상 배열을 이용하는 것이 훨씬 구현이 편리하다. 우선순위 큐는 힙의 특성을 이용해서 '우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료 구조'이다. 우선순위 큐에서 사용하는 힙의 특성은 '부모 노드는 항상 자식보다 우선순위가 높다'는 성질이다. 이를 활용하여 힙에서는 부모노드를 제거해가면서 우선 순위가 높은 순대로 뽑혀 나오는 것으로 구현했었다. 다만 주의해야할 것은 우선순위 큐가 힙이고 힙이 우선순위 큐는 아니라는 것이다. 힙은 '최솟값 혹은 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 ..