CS/Algorithm 문제
[Programmers] H-Index
[Programmers] H-Index 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42747 💬설명 문제가 조금 헷갈리게 적혀있어서 이해하는데 시간이 오래 걸렸다. 포인트: h번이상 인용된 논문의 개수가 h개 이상인 것 중 최대 h값 선택 예시를 보면 이해가 된다. [3, 5, 6, 1, 0]이 있을 때 내림차순으로 정렬하면 [6, 5, 3, 1, 0]이다. index도 함께 표시하면 [6, 5, 3, 1, 0] 0, 1, 2, 3, 4 인데 여기서 얘기하는 조건을 만족 시키려면 h번 이상 인용되는 논문이 h개 이상, 즉, index >= citation이다. 그러니까 index값이 결국 h번이상 인용되는 논문 개수니까 (내림차순으로 정렬했기 때문)..
[Programmers] K번째수
[Programmers] K번째수 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42748 💬설명 그냥 문제에 나온대로 풀면 되는 문제 파이썬의 sort함수를 써서 쉽게 풀었다. 👩💻코드 def solution(array, commands): answer = [] for command in commands: i, j, k = command new_arr = array[i - 1: j] new_arr.sort() answer.append(new_arr[k - 1]) return answer
[Programmers] 이중우선순위큐
[Programmers] 이중우선순위큐 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42628 💬설명 python heapq를 이용해서 풀었다. 최대힙, 최소힙 모두 써줘야 했기 때문에 두 힙의 동기화가 중요했다. 최대값 pop할 때 최소힙에서도 삭제해주고, 최소값 pop 할때 최대힙에서도 삭제해주면 된다. + 다른 사람 코드도 찾아보니 굳이 두개의 heap을 사용하지 않고 최소힙에서 heapq.nlargest(n, hq) 이렇게 해주면 큰값 순서대로 n개 뽑힌다고 한다. 그럼 heapq.nlargest(1, hq)이렇게 해주면 된다. 👩💻코드 import heapq max_hq = [] min_hq = [] def solution(operation..
[Programmers] 디스크 컨트롤러
[Programmers] 디스크 컨트롤러 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42627 💬설명 우선순위 큐로 푸는 문제 기본 아이디어를 생각해내는건 어렵지 않았지만 문제 푸는 로직을 생각해내는게 조금 까다로웠다. 기본 아이디어: 특정 시점에 소요시간이 가장 작은 작업을 골라서 수행 풀이 while 모든 작업이 완료될 때까지: 1. 현재 가능한 모든 작업 heapq에 넣기 가능한 작업의 기준: 들어온 작업들 마지막으로 체크한 시간(pre_time) < 요청 시간
[BaekJoon] 백준 4358번 생태학
[BaekJoon] 백준 4358번 생태학 🎈문제 https://www.acmicpc.net/problem/4358 💬설명 문제에는 트라이 알고리즘이라고 적혀있었지만 dictionary로만 풀어도 풀리는 문제였다. 포인트 데이터가 크기 때문에 시간을 최대한 줄여줘야 했다. (pypy로 하지 않고 python으로 채점해도 되긴 함) 입력이 언제 끝나는지 따로 표시해주지 않는다. 입력이 끝났는지 따로 체크해줘야 함 출력 시 소수점 4째자리까지 반올림 해서 출력하라고 하는데 그냥 round만 쓰면 50 -> 50.0000으로 출력하지 않기 때문에 %.4f로 출력해줘야 한다. 👩💻코드 # BaekJoon4358.py import sys input = sys.stdin.readline dic = {} sum_t..
[BaekJoon] 백준 2170 선 긋기
[BaekJoon] 백준 2170번 선 긋기 🎈문제 https://www.acmicpc.net/problem/2170 💬설명 스위핑 기법으로 푸는 문제라고 한다.스위핑 기법이란 말 그대로 한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 쓸어가는 것이라고 보면 된다. 풀이 과정 시작점을 기준으로 sort한다. 다음 line이 이전 line에 포함되는 경우, 일부가 겹치는 경우, 아예 겹치지 않는 경우 이렇게 3가지로 나눠서 생각한다. 주의 데이터의 크기가 큰만큼 시간초과가 계속 났다. 해결책 import sys -> input = sys.stdin.readline arr 속에 line들을 tuple로 저장 (iteration 도는 속도가 tuple이 빠르다고...?) pypy로 채점 👩💻코드 # Ba..
[BaekJoon] 백준 21609번 상어중학교
[BaekJoon] 백준 21609번 상어중학교 🎈문제 https://www.acmicpc.net/problem/21609 💬설명 bfs, 구현 문제 따져줘야하는 조건이 많아서 까다로웠다. python으로 채점하면 시간초과가 나서 pypy로 채점해줬다. 좀더 깔끔하게 풀 수 있을 것 같은데 문제 잊었을 때 쯤 다시 풀어봐야겠다. 👩💻코드 # BaekJoon21609.py from collections import deque import copy N, M = map(int, input().split()) result = 0 dx = [0, 1, 0, -1] dy = [-1, 0, 1, 0] arr = [[] for _ in range(N)] for i in range(N): arr[i] = list(ma..
[Programmers] 더 맵게
[Programmers] 더 맵게 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42626 💬설명 처음에는 PriorityQueue로 풀었는데 시간초과가 나서 heapq를 이용해 풀었다. 둘다 push pop이 O(logn)인걸로 알고 있는데 의문이었다. 찾아보니까 PriorityQueue는 heapq의 함수들을 이용해서 만들어졌지만 thread-safe한 대신 속도가 느리다고 한다. (참고) heapq로 우선순위 고려해서 풀어준다. 👩💻코드 # 시간 초과 코드 from queue import PriorityQueue def solution(scoville, K): answer = 0 pq = PriorityQueue() # priority queue..