일련의 숫자에서 중앙값 찾기 중앙값이란 어떤 배열을 정렬했을 때 정 가운데에 위치하는 값 원소의 개수가 홀수인 경우: 가장 중앙에 위치한 원소가 중앙 값((전체 개수 + 1) / 2 번째 원소) [1, 2, 3]의 배열에서는 2가 중앙값 원소의 개수가 짝수인 경우: 가운데 두 원소의 평균이 중앙값 [1, 2, 3, 4]에서는 2와 3의 평균인 2.5가 중앙값 중앙값을 찾을 때 그냥 최소힙이나 최대힙 둘중 하나로 만들고 중앙에 해당하는 인덱스에 있는 값을 반환하면 되겠지만 데이터가 지속적으로 추가/삭제되고 있는 상황에서 중앙값을 찾으려면 중앙값을 찾을때마다 배열 전체에 대한 정렬을 시도하므로 시간 낭비임 🌟🌟🌟하나의 최소 힙과 최대 힙을 만들면 중간 값을 얻는 것은 단지 O(1) 시간 밖에 걸리지 않음 그..

힙(Heap) 힙이란? 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 힙에는 최소힙과 최대힙이 있음 최소힙 작은 값을 항상 트리의 위에 있게 해서 트리의 루트에는 가장 작은 값이 오도록 함 최대힙 가장 큰 값이 맨 위에 오도록 함. 모든 노드는 자기 부모 노드가 자기보다 큰 값을 가지고 있음 힙에 데이터를 삽입하고 값을 꺼내오는 방법 최소힙에 데이터를 삽입하는 방법 저런 트리가 있다고 하자 1을 삽입하려고 할 때 완전이진트리의 요건을 만족시키기위해 저 자리에 삽입 자신의 값과 자신의 부모노드값을 비교하여 자신의 값이 더 작으면 자리를 바꿈 3번의 과정을 자신의 값이 부모노드값보다 작을때까지 혹은 루트에 도착할 때까지 반복한다. 이 작업은 밸런스가 맞춰져있..