Priority Queue
-
[Algorithm] - HEAP(우선 순위 QUEUE)Algorithm/Algorithm 2022. 9. 1. 16:56
Heap - 우선 순위 Queue Pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 , 우선 순위가 가장 높은 원소가 나온다. 원소의 추가 O(LogN) 우선 순위 높은 ITEM 확인 O(1) 우선 순위 높은 순서 제거 O(LogN) 이진 검색 트리와 Heap 은 다른 자료 구조다. import heapq BOJ 1715번 - 카드 정렬하기 IDEA 1. 작은 값 2개 값을 더하는게 최소의 경우이다. ( GREEDY ) -> 작은 값을 더하지 말고 다른 값을 더하였을 경우보다 더 작은 경우가 발생 불가능! 2. 수의 범위가 1000일 때, 10만개인 경우에 INT형의 범위를 벗어나는가? -> INT형의 범위를 벗어나지 않아 별도로 생각하지 않아도 된다. 3. 예외 처리 1개만 들어온 경우는 최소..
-
[Programmers] - 더 맵게Algorithm/프로그래머스 2022. 7. 7. 13:01
[Programmers] - 더 맵게 https://school.programmers.co.kr/learn/courses/30/lessons/42626?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 모든 매운 지수들을 K이상으로 만든다. K보다 작은 값들은 2가지를 합쳐 스코빌을 높일 수 있다. 이 때 몇번만에 모든 스코빌 지수를 K보다 크게 할 수 있는가? 알고리즘 가장 작은 수들을 계속하여 합쳐야 함으로 우선순위 Queue 알고리즘을 사용하였다. Heapq를 통하여 가장 작은 숫자를 O(logN)에 뽑아내어 갱..
-
[BOJ] 2170번 - 선 긋기Algorithm/BOJ 2022. 6. 11. 13:56
[BOJ] 2170번 - 선 긋기 https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 주의할 점이 선을 긋는다고 하여 0부터 시작하는 것이 아닌 음수부터 시작이 된다 및 여러 번 그은 부분이나 한번 그은 부분이나 동일하게 계산되어야 한다. 알고리즘 그리디 알고리즘을 이용하여 풀었다. 시작점이 작은 좌표부터 시작하여 가장 긴 값을 찾아가는 형태로 찾아가면 최소 최대 길이를 구할 수 있다. 최소 값을 갱신하면서 찾아야 하기..