alpyrithm_알파이리즘

11404 플로이드 www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 � www.acmicpc.net 문제 풀기 전 공부할 것 : 플로이드-와샬 풀이 최소 비용을 구하는 문제로 플로이드 와샬을 이용해서 해결하면 된다. 도시 a에서 도시 b로 가는 비용을 초기화한다. 그리고 3중 for문을 통해 i에서 j로 갈 때 k 도시를 거쳐서 가는 경우가 최소 비용이면 이를 업데이트한다. import sys input = sys.stdin.readline n = int(in..

16953 A → B www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 풀기 전 공부할 것 : 그래프 탐색, 너비 우선 탐색 풀이 1 bfs를 이용해서 해결한다. que에 (a, 1)을 넣는다. popleft를 통해 뽑은 숫자에서 가능한 연산을 한다. 만약 2를 곱했을 때 b보다 크다면 que에 넣지 않는다. 만약 1을 수의 가장 오른쪽에 추가했을 때 정수가 b보다 크면 que에 넣지 않는다. from collections import deque a, b = map(int, input().split()) res = -1 que = deque([(a, 1)]) while que: ..

1717 집합의 표현 www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 �� www.acmicpc.net 문제 풀기 전 공부할 것 : 자료구조, 분리 집합 풀이 Union-Find를 이용해서 해결할 수 있다. parent를 자기 자신으로 초기화한다. 부모를 찾는 find 함수를 만든다. 합집합 연산을 하여 같은 부모를 갖도록 union 함수를 만든다. 연산을 입력받아 0이면 union으로 합집합 연산을 하고 1인 경우 find를 통해 부모를 찾고 부모가 같..

1302 베스트셀러 www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 문제 풀기 전 공부할 것 : 정렬 풀이 books dictionary를 만들어 책의 이름을 key로 하고 하루 동안 팔린 책의 개수를 value로 저장한다. 저장한 dictionary를 orders list에 (책의 이름, 팔린 책의 개수) 형태로 저장한다. orders를 많이 팔린 책의 개수, 사전 순으로 정렬한다. import sys input = sys.stdin.readline..

2056 작업 www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 �� www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍, 그래프 이론, 위상 정렬 풀이 K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이므로 dp로 해결할 수 있다. 해당 작업에 걸리는 시간을 times에 저장하고 선행 작업을 graph에 저장한다. for문을 돌면서 해당 작업에 필요한 선행 작..

1766 문제집 www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 풀기 전 공부할 것 : 그래프 이론, 자료 구조, 우선순위 큐, 위상 정렬 풀이 가능하면 쉬운 문제부터 풀어야 하고 문제는 난이도 순서로 출제되어 있으므로 heap을 사용해서 해결하면 된다. import heapq import sys input = sys.stdin.readline n, m = map(int, input().split()) problems = ..

2252 줄 세우기 www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net 문제 풀기 전 공부할 것 : 그래프 이론, 위상 정렬 풀이 1 키를 비교한 두 학생의 번호 A, B를 입력받고 heights에 A 다음에 B가 와야 한다는 것을 저장하고 students에 B 앞에 A가 와야 하므로 +1을 한다. students의 값이 0인 곳은 앞에 와야 하는 학생이 없으므로 먼저 줄을 세운다. i 학생을 줄을 세우면 i 학생 다음에 와야..

2493 탑 www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 �� www.acmicpc.net 문제 풀기 전 공부할 것 : 자료구조, 스택 풀이 1 탑의 높이를 입력받는다. 탑의 높이와 인덱스를 같이 저장한다. 탑이 empty가 아니라면 수신할 수 있는 탑을 찾을 때까지 stk에 저장하고 있는다. heapq를 이용해 높이가 낮은 탑부터 pop해서 계산을 여러 번 하지 않아도 되게 한다. import heapq n = int(input()) height = list(map(int, in..