Dev_Diary

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..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리 순회 문제입니다. 큐를 사용해 상위 노드부터 내려오면서 트리를 재작성해서 풀었습니다. 상위에서부터 써내려갔기 때문에 방문한 적이 있다면 상위노드라는 점을 이용했습니다. from collections import deque def solution(N, data_list): # 임시 트리 # 인덱스 맞추기 위해 + 1 temp_tree = [[] for _ in range(N+1)] # 우선 데이터를 트리에 정리 for data in data_list: te..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 기본적인 트리 순회 문제입니다. 기본 구조만 만들어놓고 어느 타이밍에 읽어내느냐를 조절하면 쉽게 풀 수 있습니다. def solution(N, data_list): # 트리 사전 tree_dict = {} # 사전 작성 for data in data_list: tree_dict[data[0]] = [data[1], data[2]] # 순회 # 전위 순회 preorder_list = pr..