Dev_Diary

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 기본적인 구현문제입니다. 작은 기능들을 나누어 함수화하면 쉽게 풀 수 있습니다. 회전할 톱니를 체크하는 함수, 톱니를 회전시키는 함수로 쪼개어 풀었습니다. from collections import deque def solution(gear_list, K, data_list): # 데큐로 치환 gear_list = [deque(gear) for gear in gear_list] # 데이터 리..

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): # ..