Dev_Diary

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 필요한 기능을 구분해서 구현할 수 있다면 비교적 쉽게 풀 수 있는 문제입니다. 맵을 탐색하는 함수, 벽을 배치하는 경우의 수를 구할 수 있는 함수를 구현하면 풀 수 있습니다. from collections import deque from itertools import combinations import copy def solution(N, M, data_list): # 벽을 배치할 위치를 찾음 wall_lis..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 그리디 알고리즘으로 풀 수 있는 문제로 어떤 순서로 더했을 때 최소가 될지 생각해보면 쉬운 문제입니다. def solution(N, data_list): # 데이터 리스트 정렬 # 누적합 리스트 만들기 위해 0 추가 data_list = [0] + sorted(data_list) # 누적합으로 변경 for idx in range(len(data_list)): # 0 번 인덱스 스킵 if idx: data_list[idx] +=..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 2를 곱한 수와 10을 곱하고 1을 더한 수가 같을 수 없다는 점을 착안하고 목적수에 도달만 하면 무조건 리턴하게 하면 됩니다. 처음에는 dp 를 사용하려 했지만 메모리 초과때문에 저장하지 않고 비교만 해야합니다. from collections import deque def solution(A, B): # 큐 queue = deque([[A, 1]]) # 계산 while True: # 큐가 비면 끝 if not queue: return -1 # 현재 수, 카운트 now_num, cnt = queue.popleft() # ..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net Set 을 사용할 줄 안다면 쉽게 풀 수 있는 문제입니다. def solution(never_listen_list, never_look_list): # set 으로 변환 never_listen_set = set(never_listen_list) never_look_set = set(never_look_list) # 교집합 never_lisok_set = never_listen_set & neve..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 플루이드-워셜 알고리즘을 써도 괜찮지만 결국 한 지점에서 다른 지점까지의 최소거리의 합을 구하면 되는 문제이기 때문에 다익스트라 알고리즘을 여러 번 써서 풀었습니다. import heapq def solution(N, M, data_list): # 트리 tree = [[] for _ in range(N+1)] for data in data_list:..

https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 백터의 합 이라는 개념을 알고 있다면 쉽게 풀 수 있습니다. 또 벡터의 수가 적기 때문에 완전탐색을 통해 풀 수 있습니다. 더불어 콤비네이션을 구하는 내장 함수인 itertools.combinations 를 사용하면 쉽게 풀 수 있습니다. from itertools import combinations def solution(N, vector_list): # 주어진 벡터중 절반은 더하고 절..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net BFS 로 풀다가는 큐와함께 속도 터져나가는 문제입니다. 위상정렬 알고리즘을 통해 큐에 진입되는 조건을 지정해줘야 풀 수 있습니다. 간단하게 설명하자면 특정 노드에서 들어가고 나가는 노드의 수를 기록해 들어가는 노드가 적은 순서로 탐색하는 알고리즘입니다. 특정 노드를 방문하는 조건이 여러 개일 때 사용하는 알고리즘입니다. from collections import deque import sy..

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 기존 다익스트라에서 거친 경로를 구해야 했기 때문에 추가적인 조치를 취해야했다. 또 이미 현재 누적된 가중치가 해당 노드의 가중치의 최솟값보다 크면 미리 중지해 실행 시간을 줄여야했다. import heapq def solution(V, E, K, data_list): # data_list 정리 simple_data = [[] for _ in range(V+1..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라를 여러 번 사용해서 푸는 문제 같지만 입력받은 가중치를 사용해 X -> 다른 노드 의 다익스트라와 가중치의 방향을 반전시켜 X -> 다른 노드의 다익스트라를 더한 값을 비교하면 된다. 가중치의 방향을 반전시키면 다른 노드에서 X 로 오는 거리를 구할 수 있기 때문이다. import heapq def solution(N, M, X, data_list): # ..

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 전형적인 다익스트라 알고리즘 문제입니다. heapq 를 사용하면 쉽게 풀 수 있습니다. import heapq def solution(V, E, K, data_list): # data_list 정리 simple_data = [[] for _ in range(V+1)] for start, end, weight in data_list: simple_data[sta..