Heap Build 시간복잡도는 O(NLogN)이 아니다! 얼마 전에 알게 된 사실이다. Heap Build에 필요한 시간복잡도는 O(nlogn)이 아니다. 바로 O(n)이다. 나는 당연히 Heapfy를 한번 하는데 필요한 시간 복잡도가 O(logn)이기 때문에 n개의 리스트를 Heap으로 만들면 당연히 O(nlogn)으로 이해를 하고 있었다. 그런데 실제로는 그것보다 더 적은 값으로 계산이 된다고 한다. 이곳(Time Complexity of building a heap - GeeksforGeeks)에 증명이 되어있었고, 그것을 내가 알아보기 쉽게.. 부족한 수학 머리로 간단히 정리해본다. 먼저 Heap Build 시간복잡도는 다음과 같은 식을 세울 수 있다. 여기서 n은 Array나 List의 최대 ..
이번 포스팅에서는 중요한 자료구조인 큐와 덱에 대해 정리를 하려고 한다. 단, 이 게시글은 비전공자가 따로 공부하고 정리한 내용이기 때문에 틀린 내용이 있을 수 있다. 큐(Que)란? 큐는 먼저 들어온 데이터가 먼저 나가는 자료구조를 가리킨다. 실생활에서 가장 보기 쉬운 형태의 자료구조이며, 간단한 예로는 줄 서는 것을 볼 수 있다. 지하철에서 먼저 줄을 서는 사람이 먼저 타는 것처럼 먼저 들어온 데이터가 먼저 나가는 형식의 자료구조로 보면 된다. 배열기반 큐 구현1( Two Pointer) 큐는 데이터의 가장 앞부분을 알려주는 First Index, 가장 뒷부분을 알려주는 Last Index가 있다. 이 두 Index의 이동을 이용해서 큐를 구현한다. 그렇다면 큐에서 각 쿼리가 발생했을 때, 이 Ind..
정렬 알고리즘 정리 정렬은 쉽게 간단히 구현할 수 있는 간단한 정렬과 복잡하게 구현하는 복잡한 정렬이 있다. 당연한 이야기지만 간단한 정렬은 그만큼 성능이 떨어지며, 복잡한 정렬은 구현이 쉽지 않지만 그만큼 성능이 좋다. 이번 포스팅에서는 정렬 알고리즘에 대해 정리해보고자 한다. 버블정렬 버블정렬은 말 그대로 물방울이 터지듯이 하나씩 정렬이 되어가는 정렬이다. 예를 들어 가장 큰 것을 가장 오른쪽으로 보내고, 그 다음 두번째로 큰 것을 오른쪽에서 두번째로 보내는 방식으로 반복되는 정렬이다. 아래 그림을 통해 예시로 설명한다. 위 이미지는 초기 값으로 3,2,1,5,4가 정렬된 배열을 버블 정렬로 정렬하는 과정을 보여주는 그림이다. 왼쪽 그림은 좌측에 가장 큰 값을 가장 오른쪽으로 옮기는 경우, 오른쪽의 ..
Heap이란 무엇인가? Heap은 우선순위 큐를 구현하기 위해 고안된 자료구조다. 우선순위 큐는 일반적인 큐의 선입선출 동작과는 다른 동작을 한다. 늦게 들어온 값이라도, 우선순위가 높으면 먼저 나오는 기능이 구현된 자료구조다. Heap은 어떻게 구현하는가? Heap은 크게 배열, 링크드리스트, 트리로 구현할 수 있다. 그렇지만 트리로 구현하는 것이 가장 좋은 것으로 알려져 있다. 위처럼 배열로 구현된 Heap이 있다고 가정해본다. 이 때, Heap에 삽입을 할 때, 자기가 들어가야 할 자리를 탐색해야하기 때문에 탐색에만 O(n) 시간이 필요하다. 중간에 삽입 시, 뒷쪽에 있는 배열들을 늘려주고 한 칸씩 이동해주어야 한다. 삭제를 할 경우, 가장 앞에 있는 인덱스를 삭제할 경우 한 칸씩 땡겨야 하기 때문..
테이블은 무엇인가? 딕셔너리는 Key, Value 형식으로 주어진 자료형을 이야기한다. 우리 주변에는 이런 형식을 아주 흔하게 찾을 수 있는데, 예를 들면 아래 표와 같은 것이다. 사번 이름 20160829 김영희 20160830 김철수 20160840 김선생 우리가 엑셀에서 흔히 보는 데이터 테이블인데, 이런 형식으로 주어지는 자료를 차곡차곡 모은 것을 딕셔너리라고 한다. 유사한 말로는 테이블, 맵이 있을 수 있다. 이런 자료구조 형식의 장점은 O(1)의 시간복잡도로 자료를 찾고, 추가할 수 있다는 점이다. 테이블은 어떻게 만들까? 기본적으로 테이블은 배열을 기반으로 구현하는 것으로 알고 있다. 배열을 기반으로 구현한다면, 당연히 배열 범위는 필요한만큼만 선언이 되어야 메모리의 최소화가 가능하다. 이런..