Dev_Diary

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

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 백준 2230 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우 dev-diary-0717.tistory.com 전형적인 투포인터 문제로 2230 ..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소수 / 누적합 / 투포인터를 결합한 문제입니다. 소수 리스트를 만들 때 최적의 수로 만들지 않으면 시간이 부족했습니다. def solution(N): # 소수 리스트 만들기 # 0 은 누적합 만들기 쉽게 하려고 붙임 prime_list = [0] + find_prime(N) # 소수 리스트 누적합 리스트 만들기 subsum_prime = make_subsum(prime_list) # 투포인터 start = 0 end = 1 # 경우의 수 cnt = 0 while True: # end 가 인덱스를 넘어가면 끝 if ..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 투포인터와 누적합을 같이 사용하면 쉽게 풀 수 있습니다. 누적합 리스트를 만든 뒤 백준 2230 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우 dev-diary-0717.t..

https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 전형적인 투포인터 문제입니다. 두 포인터의 차이가 목표보다 크면 하위 포인터를 옮겨 차이를 줄이고 목표보다 작으면 상위 포인터를 옮겨 차이를 늘리면서 최소 길이를 비교해나갑니다. def solution(N, M, data_list): # 정렬 data_list = sorted(data_list) # 차이의 최솟값 min_sub = 2000000000 # 투포인터 left = 0..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 가장 작은 로프를 제외하며 계산하면 쉽게 풀 수 있다. def solution(N, data_list): # 리스트 정렬 data_list = sorted(data_list) # 최댓값 max_value = 0 # 정렬 후 낮은 밧줄부터 제거하면서 비교 # 중간값만 빼볼 필요는 없음 for idx in range(N): # 제일 낮은 값 X 밧줄 수 value_sum = data_list..

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net B 를 정렬하면 안된다는 조건이 까다로웠다. A를 B로 정렬하는 방법을 찾는다면 풀 수 있다. def solution(N, A, B): # 리스트 정렬 A = sorted(A) # A를 정렬한 인덱스 리스트와 와 B 를 병합 A_index_list = list(range(N)) A_index_list = zip(A_index_list, B) # B 에 따라 A_index_list 를 정렬 ..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디 알고리즘 문제로 리스트 정렬의 키를 지정할 수 있으면 쉽게 풀 수 있습니다. def solution(N, data_list): # 시작시간에 맞추면 최대 회의수를 구할 수 없음 # 1~4, 2~3, 3~4 가 있으면 1~4 는 1번 2~3, 3~4 는 2번 # 끝나는 시간에 맞춰 정렬해야 한다 # 끝나는 시간이 1순위, 시작시간이 2순위로 정렬 data_list = sorted(data_list, key=lambda x:(x[1], x[0])) # 끝나는 시간 end = 0 # 데이터 인덱스 idx = 0..