KEEP GOING

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 1. 정답 코드 import heapq from collections import deque # 보석의 개수, 가방의 개수 n, k = map(int, input().split()) jewel = [] for _ in range(n): # 보석의 무게, 보석의 가격 m, v = map(int, input().split()) jewel.a..

[회의실 배정] (하) https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 1. 큐 사용 from collections import deque n = int(input()) time = [list(map(int, input().split())) for _ in range(n)] # 종료 시간, 종료 시간이 같다면 시작 시간순으로 정렬 time.sort(key=lambda x:(x[1], x[0])) deq = deque(time) start, end = deq.popleft() count = 1 while deq: next_start, next_end = deq...

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 처음에 엥 이게 왜 dfs 문제지? 하고 while True 문을 이용해 물고기 이동, 제일 덩치 큰(번호가 높은) 물고기를 골라 상어의 식사를 마치고 상어가 벽을 만나면 그대로 종료하는 식으로 풀이하였다. 그러나.. 이 문제는 '상어가 먹을 수 있는 물고기 번호의 최댓값을 구하는 문제'이다. 따라서 벽을 만나지 않으면서 최대한 많은 물고기를 잡아먹도록 구현해야 한다. 그렇기 때..

[순위 구하기] https://leetcode.com/problems/rank-scores/submissions/ Rank Scores - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. rank : 동일한 값은 동일한 순위 부여 * 직업별로 순위를 매기고 싶은 경우) RANK() OVER (PARTITION BY JOB ORDER BY SAL DESC) SELECT score ,RANK() OVER(ORDER BY score DESC)as 'rank' FR..

[최단경로] (하) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 구현 import heapq def dijkstra(start): queue = [] distance[start] = 0 heapq.heappush(queue, (0, start)) while queue: cost, now = heapq.heappop(queue) # 저장된 비용이 현재 비용보다 적다면 무시 if cost > dista..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 1. combination 사용 from itertools import combinations while True: s = list(map(int, input().split())) if len(s) == 1 and s == [0]: break k = s.pop(0) for data in list(combinations(s, 6)): print(*data) print() 2. 백트래킹 구..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 1. union find로 구현 # 정점, 간선의 개수 n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] parent = [i for i in range(n+1)] def find(x, parent): if parent[x] != x: return find(parent..

* BFS (Breath-Frist Search) - 너비 우선 탐색 - 큐(deque) 사용 - 현재 위치에서 가장 가까운 노드들을 모두 방문 - 현재 위치 pop, 방문할 곳 append, 방문한 곳 check ☞ 미로 탐색 중 최단 거리를 찾는 문제 ☞ 임의의 경로를 찾는 문제 BFS 장/단점 - 장점: 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장함 - 단점: 경로가 매우 길 경우 탐색가지가 급격히 증가하여 많은 기억 공간이 필요함 해가 존재하지 않는다면 유한 그래프인 경우, 그래프 탐색 후 실패로 끝남 다만 무한 그래프인 경우에는 해를 찾지도 끝내지도 못한다. ex) 우리나라에서 직통도로로 연결된 지역 중, 서울과 경기도 사이에 존재하는 경로를 찾고싶을 때 깊이 우선 탐색의 경우(DF..