동빈나22 [이취코] 전보 (Python3) Problem: 최단 경로 알고리즘 - 다익스트라 (Dijkstra) 다익스트라를 적용한 코드 ''' ⭐️⭐️⭐️⭐️⭐️ ''' import heapq import sys input = sys.stdin.readline INF = int(1e9) # 무한, 10억 n, m, start = map(int, input().split()) graph = [[] for i in range(n + 1)] distance = [INF] * (n + 1) for _ in range(m): x, y, z = map(int, input().split()) # X에서 Y로 가는 거리 비용이 Z graph[x].append((y,z)) def dijkstra(start): q = [] # 시작노드로 가기 위한 최단 거리 0.. 2024. 3. 6. [이취코] 병사 배치하기 (Python3) Problem: 다이나믹 프로그래밍 (Dynamic Programming) DP를 적용한 코드 n = int(input()) arr = list(map(int, input().split())) arr.reverse() d = [1] * n for i in range(1, n): for j in range(0, i): if arr[j] < arr[i]: d[i] = max(d[i], d[j] + 1) # print(d) print(n - max(d)) ''' 7 15 11 4 8 5 2 4 reverse() 4 2 5 8 4 11 15 ''' 2024. 3. 6. [이취코] 효율적인 화폐 구성 (Python3) 처음에 짠 코드 n, m = map(int, input().split()) costs = [int(input()) for _ in range(n)] count = -1 d = [0] * 10000 for cost in costs: if m % cost == 0: count = m // cost else: count = -1 print(count) DP를 적용한 코드 n, m = map(int, input().split()) cost = [int(input()) for _ in range(n)] d = [10001] * (m+1) d[0] = 0 for i in range(n): # 3 for j in range(cost[i], m+1): # cost ~ 7 if d[j - cost[i]] != 10001.. 2024. 3. 6. [이취코] 정렬된 수열에서 특정 수의 개수 구하기 (Python) 처음에 짠 코드 n, m = list(map(int, input().split())) arr = list(map(int, input().split())) start = arr[0] end = arr[-1] count = 0 while start m: end = mid - 1 else: start = mid + 1 print(count) BS를 적용한 코드 from bisect import bisect_left, bisect_right def count_by_range(array, left_value, right_value): right_index = bisect_right(array, right_value) left_index = bisect_left(array, left_value) return rig.. 2024. 3. 6. [이취코] 떡볶이 떡 만들기 (Python) 처음에 짠 코드 import sys n, m = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split())) sorted_arr = sorted(arr) end = sorted_arr[n-1] # 19 start = sorted_arr[0] for i in range(end - 1, start, -1): count = 0 for j in range(len(sorted_arr)): if sorted_arr[j] - i >= 0: count += sorted_arr[j] - i if count == m: break print(i) BS를 적용한 코드 n, m = list(map(int, input().spli.. 2024. 3. 6. [정렬 알고리즘] 문제: 두 배열의 원소 교체 https://youtu.be/KGyK-pNvWos?si=UmTopIc_Gx-Xh8nV 본 내용은 위의 유투브를 참고해서 작성했음을 밝힙니다! 두 배열의 원소 교체 문제 해결 아이디어 n, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) a.sort() # 배열 A는 오름차순 정렬 수행 b.sort(reverse=True) # 배열 B는 내림차순 정렬 수행 # 첫 번재 인덱스부터 확인하며, 두 배열의 원소를 최대 k번 비교 for i in range(k): if a[i] < b[i]: a[i], b[i] = b[i], a[i] else: break print(sum(a)).. 2024. 2. 13. 이전 1 2 3 4 다음
