안녕하세요! 콩하나입니다 ㅎㅎ 오랜만에 블로그 글을 작성해보네요. 요즘 블로깅할만한 거리가 보이지 않아서... 못했다고 하죠 ㅎㅎ 예전에 백준 666일 연속 풀이를 하다가 끊기고 나서 한동안 안풀다가 최근 알고리즘 문제를 다시 풀고 있는데요. 이제는 오히려 스트릭에 구애받지 않고 풀고싶은 문제들을 풀어서 더 편안한 마음으로 스트레스 안받고 푸는 것 같아요 ㅎㅎ 아무튼 지난주에 블랙캣이 18년도 카카오 공채 문제들을 한번 풀어봐라~ 추천해서 지난주에는 18년도 카카오 공채 문제들을 풀어봤습니다. 확실히 최근 문제들이 어렵긴하더라고요... 금요일에는 당시 제일 어려운 난이도로 출제된 '추석 트래픽' 문제를 한번 풀어봤습니다. 그냥 풀어보고 넘기려고 했는데, 요즘 우테코 크루들 중에서도 알고리즘을 푸는 분들도..

Heap 1. Heap 1) Heap이란? - Heap은 Priority Queue와 밀접한 관계가 있다. Priority Queue 내부에 Heap을 사용하는 경우가 많다. 힙은 노드에는 우선순위에 관한 자료를 추가적으로 가지고 있다. - 힙은 이진트리이지만 BST는 아니다. BST는 크기의 대소 관계에 따라 데이터를 삽입한다. - 이진트리는 자식이 최대 두개까지 있는 것을 의미한다. 또한 가장 깊은 노드에 있는 것을 제외한 노드는 모두 2개의 자식이 있고, 가장 하단에 있는 노드는 좌하단부터 노드를 채워간다. 최대힙은 모든 노드는 자기의 자식보다 더 크거나 같은 트리를 가지게 된다. 따라서 루트에 있는 값만 확인하면 된다. - 왼쪽의 예시는 힙은 아니지만 오른쪽은 최대힙이다. 2) Heap의 특징 -..

우선순위 큐 특징 : 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 예시) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야하는 경우 구현 방법 1) 단순히 리스트를 이용하여 구현한다. 2) 힙(heap)을 이용하여 구현한다. 시간복잡도 - 데이터의 개수가 N개 일 때, 구현 방식에 따라서 시간 복잡도를 비교한 내용은 다음과 같다. 1) 리스트 - 삽입 시간 : O(1) (리스트의 가장 뒤에 추가가 되기에 O(1)이 소요됨) - 삭제 시간 : O(N) (모든 데이터를 확인하기 때문에 선형 시간 복잡도를 가짐) 2) 힙 - 삽입 시간 : O(logN) - 삭제 시간 : O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. (힙정..