python

문제https://www.acmicpc.net/problem/2252백준 문제집 - 0x1A강 - 위상 정렬 알고리즘: 위상 정렬풀이 위상 정렬 자체를 처음 접해봤던 파트다.위상정렬(Topological Sorting): DAG(방향 사이클이 없는 방향 그래프)의 노드들을 순서화BFS, DFS 모두 가능. 그래프는 단방향으로 저장한다. 전체 코드1️⃣ DFS 방식# 1. DFS 사용# 진입차수(in-degree) 불필요# 메모리: 39328KB / 시간: 156msfrom sys import stdininput = stdin.readlineN, M = map(int, input().split())graph = [[] for _ in range(N+1)]for _ in range(M): u, v = ..

문제https://www.acmicpc.net/problem/1781백준 문제집 - 0x17강 - 우선순위 큐 알고리즘: 그리디, 정렬, 우선순위 큐풀이 각 문제를 데드라인까지 풀어야 하며, 문제를 푸는 단위시간은 1.최대한 많은 컵라면을 받아야 한다.단순하게 컵라면 갯수를 기준으로 정렬했다가 실패했던 문제다.도움이 됐던 반례는 아래와 같다.1️⃣ https://www.acmicpc.net/board/view/1528282️⃣ https://www.acmicpc.net/board/view/123972 🗝️ 해결 방법은 데드라인 기준으로 정렬 후, 힙의 크기와 데드라인을 비교해가며 pop을 실행하는것이다.먼저 데이터를 (데드라인, 컵라면 갯수) 형태로 저장 후 오름차순으로 정렬한다.정렬한 리스트를 순회하..

문제https://www.acmicpc.net/problem/1655백준 문제집 - 0x17강 - 우선순위 큐 알고리즘: 우선순위 큐풀이 현재까지 주어진 수가 홀수개라면 중간값을, 짝수개라면 중간값 중 더 작은값을 출력해야한다. 이 문제는 두 개의 힙(left, right)으로 해결할 수 있다.left에는 중간값보다 작거나 같은, right에는 중간값보다 큰 수들이 들어가게끔 구성한다.즉 left는 최대 힙으로, right는 최소 힙으로 구현한다. 그리고 새로운 수 x가 주어질때마다 left와 right의 길이를 비교한다.- 두 힙의 길이가 같다면 left에 -x를 삽입 (주어진 수가 짝수개라면 더 작은값을 출력해야하므로)- 길이가 다르다면 right에 x를 삽입 힙에 삽입 후 left의 첫번째 원소값,..

문제https://www.acmicpc.net/problem/13975백준 문제집 - 0x17강 - 우선순위 큐 알고리즘: 그리디, 우선순위 큐풀이 최소 힙을 사용하는 문제다.사실 이러나 저러나 최종 파일 크기는 같을수밖에 없다.(어쨌든 N개의 파일을 모두 더해주는것이기 때문) 하지만 비용 == 두 파일을 합친 크기 이므로, 결국 매 턴마다 가장 작은 파일 두개를 뽑아 합치는것이 최소 비용인 셈이다. 전체 코드# 메모리: 138080KB / 시간: 7644msfrom sys import stdinfrom heapq import heappush, heappopinput = stdin.readlineT = int(input())for _ in range(T): K = int(input()) fil..

문제https://www.acmicpc.net/problem/23326백준 - 문제집 - 0x16강 - 이진 검색 트리 알고리즘: 이진 검색 트리, 트리를 사용한 집합과 맵풀이21944: 문제 추천 시스템 Version 2와 마찬가지로 무한 TLE♾️에 빠지게 했던 녀석이다. 1️⃣ 첫번째 시도명소들을 현재 위치: [현재 위치와 명소의 거리들] 형태의 딕셔너리로 구성.각각의 값 리스트는 최소힙으로 사용함.=> 어림도 없이 시간초과 2️⃣ 두번째 시도이진탐색 모듈로 bisect_left, insort_left 함수를 사용.명소들만 따로 리스트에 저장 후, 이진탐색으로 알맞은 인덱스를 찾아 삽입/삭제 + 탐색을 진행했음.=> 66% 정도까지 진행 후 시간초과 Python으로는 안되는건가? 했지만 PyPy3로..

문제https://www.acmicpc.net/problem/21944백준 문제집 - 0x16강 - 이진 검색 트리 알고리즘: 이진 탐색 트리, 트리를 사용한 집합과 맵풀이 21939: 문제 추천 시스템 Version 1 과 비슷하게 풀고 무한 TLE♾️에 빠졌던 문제다.좀 더 무식하게(?) 풀어야 AC를 받을 수 있다. 일단 문제의 조건을 정리해보면 다음과 같다. 입력 데이터 범위: 1 , 1  recommend: 알고리즘 분류가 G인 문제- 난이도 높고, 번호가 큰 문제- 난이도 낮고, 번호가 작은 문제 recommend2: 알고리즘 상관 X- 난이도 높고, 번호가 큰 문제- 난이도 낮고, 번호가 작은 문제 recommend3: 난이도 L 이상/미만인 문제, 알고리즘 상관 X- L 이상: 번호가 작은..