코딩

다익스트라 알고리즘 -한 지점에서 다른 특정 지점까지의 최단경로 import heapq start = int(input()) # 시작할 노드 설정 graph = [[] for i in range(n+1)] # n == 노드의 개수 distance = [1e9]*(n+1) def dijkstra(start): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now] < dist: continue for i in graph[now]: cost = dist + i[1] if cost < distance[i[0]]: distance[i[0]] = cost heapq.he..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net Input 4 7 6 13 4 8 3 6 5 12 DP 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1(6, 13) 0 0 0 0 0 0 13 13 2(4, 8) 0 0 0 0 8 8 13 13 3(3, 6) 0 0 0 6 8 8 13 14 4(5, 12) 0 0 0 6 8 12 13 14 현재물건(row), 현재 ..

www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net n, m = map(int, input().split()) times = list(map(int, input().split())) start, end = 0, 2_000_000_000_000_000_000 # N의 최댓값 x M의 최댓값 total_time= 0 # n명까지 놀이기구를 모두 타는데 걸리는 시간 while start = n: is_possible = True ..

programmers.co.kr/learn/courses/30/lessons/67260?language=python3 코딩테스트 연습 - 동굴 탐험 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[8,5],[6,7],[4,1]] true 9 [[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]] [[4,1],[5,2]] true 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[4,1],[8,7],[6,5]] false programmers.co.kr tech.kakao.com/2020/07/01/2020-internship-test/ 2020 카카오 인턴십 for Tech d..

www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net n = int(input()) data = [] for _ in range(n): days, cost = input().split(" ") data.append((int(days), int(cost))) dp = [0] * n if data[-1][0] == 1: dp[-1] = data[-1][1] # 마지막 날짜는 먼저 처리 for i in range(n-2, -1, -1): days, cost = data[i][0], data[i][1] if days + i < n: dp[i] = max(dp[i + days] + cost, dp[i+1]) ..

www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net import copy n = int(input()) arr = list(map(int, input().split())) dp = copy.deepcopy(arr) for i in range(n): for j in range(i): if arr[j] < arr[i]: dp[i] = max(dp[j] + arr[i], dp[i]) print(max(dp))

www.hackerrank.com/challenges/lilys-homework/problem Lily's Homework | HackerRank Help George figure out Lily's homework www.hackerrank.com def solution(arr): cnt = 0 n = len(arr) sorted_arr = sorted(arr) index_dict = {arr[i] : i for i in range(n)} for i in range(n): if arr[i] != sorted_arr[i]: get_index = index_dict[sorted_arr[i]] index_dict[ arr[i] ] = index_dict[ sorted_arr[i]] arr[i], arr[ge..