heapq
-
[프로그래머스] - 이중우선순위큐Algorithm/프로그래머스 2022. 9. 5. 16:09
문제 [프로그래머스] - 이중우선순위큐 https://school.programmers.co.kr/learn/courses/30/lessons/42628# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. 명령어수신 탑(높이) I 숫자 큐에 주어진 숫자를 삽입합니다. D 1 큐에서 최댓값을 삭제합니다. D -1 큐에서 최솟값을 삭제합니다. 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어..
-
[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개만 들어온 경우는 최소..
-
[Algorithm] - 다익스트라Algorithm/Algorithm 2022. 8. 31. 00:51
다익스트라 방향, 무방향 그래프에서 하나의 시작점으로 부터 다른 Node까지의 최단 거리를 구하는 알고리즘 Edge에 음수인 가중치가 있다면 절대 사용 불가! 유사 알고리즘으로 A* 알고리즘이 존재하지만, 길찾기와 같이 Node가 엄청 많을 때 유사값을 찾는 용도이다. 거리가 확정되지 않은 Edge 중에서 가장 가까운 Edge를 선택한다는 그리디 알고리즘으로 부터 착안한다. O(V^2+E) => 갱신 가능 아래와 같은 그래프에서 1부터 시작한다면, 각 Node별로 최단 거리 값이 결과가 나타난다. 1에서는 갈 수 있는 Node가 2,3,4 총 3가지다. 이중에서 가장 작은 Edge는 Node 3과 연결된 2로 갱신 시키고 Node에 대해 확정을 시켜준다. 연결된 가장 작은 Edge는 Node 2와 연결된..
-
[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] 15903번 - 카드 합체 놀이Algorithm/BOJ 2022. 6. 10. 14:11
[BOJ] 15903번 - 카드 합체 놀이 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 알고리즘 그리디로 생각하여 풀었다. 작게 만들기 위해서는 작은 두수를 뽑아내서 갱신시켜주어야 한다. 이때 시간 복잡도가 가장 낮은 Heap을 이용 1. heapq를 이용하여 Data 초기화 2. 요청받은 갯수만큼 heapq 갱신 3. 갯수 출력 코드 #BOJ 15903번 import heapq n , m = map(i..
-
[BOJ] 11000번 강의실 배정Algorithm/BOJ 2022. 6. 8. 18:32
[BOJ] 11000번 - 강의실 배정 문제 : https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 알고리즘 그리디를 이용한 알고리즘으로 생각하여 풀었습니다. 가정) 현재까지의 강의실 시간 중에 가장 빨리 끝나는 시간보다 늦게 끝난다면, 현재 강의실에 이어서 하면 된다. 아니라면 강의실 추가 1. 강의실 시간을 시작 시간 , 끝나는 시간으로 재정렬 2. 순차적으로 강의실 시간을 보면서 현재까지의 가장 빨리 끝나는 시간과 비교 3-1. 만약 빨리 끝나는 시간보다 시작한 시간이 더 작다면, 강의실이..