L.O.K

JAVA에서 우선순위 기준이 복잡할 때, 정렬을 위해 주로 사용하는 자료구조가 우선순위큐(PriorityQueue)이다. 우선순위큐가 내가 원하는 우선순위대로 정렬하려면, 비교로직을 우선순위큐에 전달해야 한다. 이번 포스팅은 우선순위큐에 비교로직을 전달하는 방법을 알아보겠다. 예시 정렬기준 ( 여러 단어를 3가지 기준으로 정렬한다. ) 자주 나오는 단어일수록 앞에 배치한다. 해당 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 1) Comparable 인터페이스 우선순위큐는 객체를 기준으로 정렬하는데, 객체가 자체적인 정렬기준을 가지고 있으면 우선순위큐가 알아서 참조하여 정렬한다. 객체가 자체적인 정렬기준을 가지려면 Comparable 인터페이스를 구현해서 c..

완전 이진 트리를 이해하기 위해 이진 트리에 대해서 알아보자. 이진 트리란? 위 그림은 이진트리의 가장 기본적인 구조이다. 부모는 자식을 갖는다. 이는 굉장한 의미를 갖는다. 버블정렬, 퀵정렬, 병합정렬은 모든 데이터가 동등한 지위를 갖었다. 그러나 힙정렬은 계층구조를 이용한다. 이런 수직적 구조는 '탐색'에 유용하기에 선택정렬을 응용한 힙정렬에는 알맞는 구조이다. 부모보다 작은 값은 왼쪽 자식, 부모보다 큰 값은 오른쪽 자식에 저장된다고 가정하자. 만약 탐색값이 부모보다 크다면 왼쪽 트리는 탐색할 필요가 없다. 그러므로 탐색할 노드의 수가 절반으로 줄어든다. 이와같이, 이진트리는 부모와 자식간의 규칙을 설정할 수 있다. 규칙은 데이터의 위치를 특정지을 수 있다. 이는 탐색에 유용하다. 그렇다면 구현은 ..

지난 포스팅에서는 HashMap의 기본 개념에 대해서 다루었다. HashMap은 key와 value로 구성된 Map 데이터를 해싱함수를 통해 산출된 인덱스 위치의 버킷(배열)안에 저장하는 자료구조이다. 해싱함수(function)는 key 값(X)을 받아 인덱스(Y)를 산출한다. 그래서 key값을 알면, 버킷의 위치를 바로 알 수 있어 HashMap은 시간 복잡도가 O(1)인 빠른 성능을 자랑한다. 그러나 key는 무한하지만 인덱스는 한정되어 있어 key들 간의 인덱스를 향한 충돌은 불가피하다. 그래서 충돌이 일어나는 인덱스에 또 다른 자료구조가 만들어 지는데 충돌 초기에는 Linked List 방식으로 Map 데이터가 저장된다. 그러다가 충돌횟수가 어느 임계점을 넘으면 Linked List 방식의 시간복..

나는 HashMap이 잘 이해되지 않았다. 인덱스가 없으니 배열이나 List에 비해 확실히 더 어렵고 직관적으로 이해하기가 힘들었다. 그래서 오늘 HashMap 자료구조가 어떤 원리로 돌아가는지 파헤쳐볼까 한다. Map Map 자료구조의 특징은 키(Key)와 값(Value)이다. 키를 통하여 값에 접근할 수 있는 구조이다. List나 배열은 인덱스로 접근한다. 인덱스는 단순히 순서만 나타낸다. 그러나 Map의 키는 개발자가 의미를 부여할 수 있다. 현재 내가 포스팅하고 있는 글의 글쓰기 창의 주소이다. Redirect = Write & categoryNo = 6 Redirect와 categoryNo는 Key이다. 그리고 Write와 6은 Value이다. 이런 원리로 key는 개발자가 부여한 의미를 갖고 ..

컬렉션 프레임 워크란 표준 API로 제공하는 자료구조 라이브러리를 의미한다. 데이터를 저장할 때, 어떤 방식으로 저장하느냐에 따라 프로그램의 성능이 바뀐다. 그래서 상황에 맞는 적절한 자료구조를 선택해야한다. 그래서 JAVA는 자료구조를 만드는데 필요한 다양한 인터페이스를 제공하는데 이를 JAVA 컬렉션 프레임워크라고 부른다. 컬렉션 프레임워크와 관련된 클래스들은 java.util 패키지 안에 들어가 있다. List, Map, Set, Queue 같이 기본적인 자료구조 인터페이스가 java.util 패키지 안에 담겨져 있다. 그러므로 우리는 자료구조를 직접 만들지 않고 API를 갖다가 쓰면 된다. 그럼 이제부터 하나씩 자료구조들을 사용해보자. List 배열이 공간이 한정되어 있는 상자라면 리스트는 구슬을..