전체 글32 [자료구조] 우선순위 큐(Priority Queue)란? 우선순위 큐(PQ: Priority Queue)란? 기존의 큐는 먼저 들어온 순서대로 First In, First Out (FIFO)을 만족하지만, 우선순위 큐는 우선순위가 더 높은 원소에 대하여 IO 먼저 진행한다. 우선순위 큐(Priority Queue) 구현은 어떻게 할까? 일반적으로 힙(Heap)을 이용한다. (힙이란?) 배열이나 연결리스트를 사용하지 않는 이유는? (찬희님의 블로그) → 삽입 과정에서 소요되는 시간이 O(n)으로 비교적 길기 때문에 값이 클 수록 우선순위가 높다고 가정했을 경우, 아래와 같이 최대힙을 사용하여 우선순위 큐를 구현해 준다. 힙의 성질에 따라, n번째 노드의 자식들은 2n, 2n+1번째에 채워지게 된다. n번째 노드의 부모는 n / 2 번째에 위치한다. PQ의 Pus.. 2021. 11. 17. [자료구조] 힙(Heap)이란? 힙(Heap)이란? 완전 이진 트리로 이루어진 자료구조! (자식이 두개이며, leaf는 왼쪽부터 채워진다) 느슨한 정렬 상태를 유지한다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리 최대값(최소값)을 빠르게 찾을 수 있도록 한다. 종류 최대힙과 최소힙으로 구분할 수 있다. 최대힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 (부모 키 값 >= 자식 키 값) 최소힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 (부모 키 값 1; i /= 2) { if (heap[i / 2] > heap[i]) { swap(i / 2, i); } else { break; } } } 삭제 (Delete) Heap에서의 삭제는 Root 삭제.. 2021. 11. 16. [LeetCode][Greedy] 55. Jump Game 문제 링크 https://leetcode.com/problems/jump-game/ Jump Game - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that positio.. 2021. 10. 4. [내 생각] 최근 떠오르는 IT 트렌드? (뒷북이려나) 2021. 08. 05 무더운 어느 날 저녁, 오늘은 재택 근무 날이라 퇴근하구 여유있게 잠시 카페에 왔다. 여름휴가에 백신휴가까지.. 사무실 자리를 오래 비우다 보니 일하는게 어색했다 (ㅋㅋ) 시원한 에어컨 바람에 아이스 아메리카노까지.. 그리고 거기에 카페 재즈 음악? 내가 너무나도 like like하는 조건이다!😍 개인 프로젝트를 해야겠다는 생각이 항상 자리하던 와중.. 제대로 해보자는 마음으로 최근에 지인들과 함께 프로젝트를 시작했다! 그 어느 것도 정해지지 않은 상태에서 시작한 프로젝트이다 보니 어떤 걸 만들어 보면 좋을까 생각하는 시간이 많아졌다. 모티브 하거나 인사이트를 얻기 위해 최근 hot한 플랫폼들을 떠올려 보았다! 🔥 가장 먼저 떠오른 플랫폼은 당근마켓! 🥕 (바니바니 바니바니) 중고.. 2021. 8. 5. 이전 1 2 3 4 5 6 ··· 8 다음
