Heap 검색 결과
4 개의 검색 결과가 있습니다.
카테고리 없음

[백준 19598] 최소 회의실 개수 (python)

19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의 www.acmicpc.net heap을 사용하는 방법과 증감배열을 이용한 방법 2가지로 풀어보았다. heap 사용하는 방법 arr를 시작점을 기준으로 정렬을 한다. 존재하는 회의실의 끝나는 시간을 저장하는 heap rooms를 생성한다. arr를 돌면서 가장빨리 끝나는 회의실(rooms[0])과 비교한다. 크거나 같다면 pop한다. 작다면 회의실을 추가하는 것으로 answer을 더해준다. rooms에 추가해준다. ※ 참고 끝나는 시간을 기준으로 오름차순을 하면 안되는 이유 0 5 0 ..

2021. 7. 25. 01:44
개발/알고리즘

[프로그래머스] 지형 이동 (python)

코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr minheap을 사용하여 비용이 적게드는 칸으로 이동하자! 방문여부 체크하는 visited 배열을 생성한다. [비용, x좌표, y좌표]를 넣는 heap을 생성한다. 방문했다면 pass하고, 안했다면 비용을 추가해준다. 4방향 칸중에서 방문하지 않은 칸을 골라 height보다 차가 크다면 비용(abs(land[x][y] - land[nx][ny]))을 넣어주고, 작다면 비용을 0으로 넣어준다...

2021. 5. 9. 01:42
개발/알고리즘

[백준 1202] 보석 도둑 (python)

1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net Heap을 사용하자! 처음에는 보석 무게 minheap을 만들어 가능한 보석을 찾고 그중에서 maxheap을 통해 가장 큰 가치를 찾는다. 보석들을 [무게, 가치]를 담는 minheap(jewel)을 생성한다. 가방은 bag에 담아 허용치순으로 정렬해준다. 보석의 가치를 담는 maxheap(candidate)를 생성한다. 작은 가방부터 돌면서 가장 무게가 작은 보석(jewel[0][0])이 가방에 들어..

2021. 4. 27. 23:15
개발/알고리즘

[백준 1655] 가운데를 말해요 (python)

1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 두개의 heap을 이용하자! 작은 수들은 maxheap에 큰 수들은 minheap에 저장하여 중앙값을 찾는다. bigheap에 첫번째 수를 저장한다. (중앙값은 bigheap[0]) 두번째 수부터 중앙값(bigheap[0])보다 작다면 smallheap에 크다면 bigheap에 넣어준다. bigheap의 길이가 (i//2)+1개를 유지할 수 있도록 두 힙길이를 조절해준다. import sys import heapq input = sys.stdin..

2021. 4. 27. 21:58