문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 방법 만약 음식을 스코빌 지수로 정렬한 다음 앞에서부터 하나씩 k와의 비교를 통해($O(N)$) 작으면 섞어주고 다시 배열에 삽입해 주는 과정을 반복하게 된다면 ($O(N)$) 총 $O(N^2)$의 시간 복잡도를 갖게 된다. 📌 그렇다면 이 문제에서 가장 필요한 상황은 무엇일까 삽입과 조회를 할때 계속 최솟값을 찾을수 있는 상황. -> 최소힙? 힙(Heaps) 성질: 최대..
정의 이진 트리의 한 종류(이진 힙 - binary heap) 루트 노드가 언제나 최댓값 또는 최솟값을 가짐 최대 힙(max heap), 최소 힙(min heap) 완전 이진 트리여야 함 📌 재귀적으로도 정의가 가능하다. max heap의 경우 어느 노드를 루트로 하는 서브트리인 경우에도 모두 최대 힙의 조건을 만족한다. 이진 탐색 트리와의 비교 원소들은 완전히 크기 순으로 정렬되어 있는가? 이진 탐색 트리 O, 힙 X 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가? 이진 탐색 트리 O, 힙 X 부가 제약 조건은 어떤것인가? 힙은 이진 탐색 트리에 비해 완전 이진 트리여야 한다는 부가 제약 조건을 갖고 있다. 최대 힙(Max Heap)의 추상적 자료 구조 연산의 정의 __init__() : 빈 최..
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/142085 문제 풀이) heap을 이용해 풀수 있었다. 문제 풀이 과정은 다음과 같다. enenmy list의 원소들을 순서대로 탐색하며 다음과 같은 절차를 밟는다. 1) n(내가 보유하고 있는 병사수)가 enenmy[i](i번째 스테이지 적의 수) 수보다 많다면 내가 보유하고 있는 병사수에서 빼준다. 이러면 특정 스테이지에서 무조건 막히게 되있는데 이때 최대힙을 이용한다. 최대힙에서 heappop()을 하게 되면 내가 지나온 스테이지중 가장 많은 적의 수가 나오게 되있다. 힙에는 내가 스테이지를 클리어하며 소모된 병사의 수(=enemy수)가 저장되어 있다고 가정한다. 2) 이때 부터 ..
