Carpe Diem Carpe Diem

다익스트라(dijkstra) 알고리즘 : start 지점에서 다른 정점까지의 최단 경로를 찾는 알고리즘 1. 노드의 개수, 간선의 개수를 입력 받는다. 2. 시작 노드 번호를 입력 받는다. 3. 시작 노드 번호에서 다른 노드로 가는 각각의 최단 거리를 출력한다. import heapq import sys n=int(sys.stdin.readline()) m=int(sys.stdin.readline()) graph=[[] for _ in range(n+1)] distance=[int(1e9)]*(n+1) # 최단거리 테이블 무한으로 초기화 for _ in range(m): start,end,price=map(int,sys.stdin.readline().split()) graph[start].append((..

N=7, M=7일때 dp[i]와 dp[i-day]+page 중 더 큰 값을 dp[i]에 넣는다! (day,page) 0 1 2 3 4 5 6 7 (2,200) 0 0 200 200 200 200 200 200 (4,40) 0 0 200 200 200 200 240 240 (5,20) 0 0 200 200 200 200 240 240 (1,20) 0 20 200 220 220 220 240 260 (2,15) 0 20 200 220 220 235 240 260 (3,10) 0 20 200 220 220 235 240 260 (1,10) 0 20 200 220 230 235 245 260 n,m=map(int,input().split()) bag=[] for i in range(m): day,page=map..

0-1 Kanpsack 알고리즘 배낭문제: 일정한 가치와 무게가 정해져있는 짐들을 배낭에 담을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제 가방의 가치: value 가방의 무게: weight 최대이윤=dp[n]이라고 할때 dp[i]=max(dp[i],dp[i-weight]+value) 129865 평범한 배낭 n,k=map(int,input().split()) bag=[] for i in range(n): w,v=map(int,input().split()) bag.append((w,v)) bag.sort(key=lambda x:x[1]) dp = [0]*(k+1) for w, v in bag: for i in range(k, w-1, -1): dp[i] = max(dp[i], dp[i-..

n,m=map(int,input().split()) nlist=list(map(int,input().split())) nlist.sort() answer=[] def dfs(depth,n,m): if len(answer)==m: print(*answer) return x=0 for i in range(depth,n): if x!=nlist[i]: # x가 list의 숫자와 같지 않다면(중복되는 수열 여러번 출력x) answer.append(nlist[i]) dfs(i,n,m) #비내림차순 x=nlist[i] answer.pop() dfs(0,n,m)

최단 경로를 찾아야 하므로 너비 우선 탐색(BFS) 사용 2차원 배열을 문자열로 바꿔준 뒤 BFS를 처리해준다는 것이 관건이다.. 나는 이 생각을 해내지 못해서... 결국 구글링... # 2차원 배열을 문자열로 정렬시킨다고 생각 # [[1,2,3],[4,5,6],[7,8,0]] -> '123456780' from collections import deque graph_to_str="" for i in range(3): graph_to_str+="".join(list(input().split())) # 입력받은 2차원 리스트 문자열로 바꾸기 visited={graph_to_str:0} #key: 현재 퍼즐 모습, value: 움직인 횟수 queue=deque([graph_to_str]) dx=[-1,1,0..

1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. n,m=map(int,input().split()) answer=[] def dfs(depth,n,m): if len(answer)==m: print(*answer) return for i in range(depth,n+1): answer.append(i) dfs(i,n,m) answer.pop() dfs(1,n,m)

(2)와 다른 점은 n개의 수를 담은 list가 주어졌다는 것이고, 중복이 허용된다는 것이다. 따라서 dfs(i+1,n,m)이 아니라 dfs(i,n,m)을 해주어야한다. n,m=map(int,input().split()) nlist=list(map(int,input().split())) nlist.sort() answer=[] def dfs(depth,n,m): if len(answer)==m: print(*answer) return for i in range(depth,n): answer.append(nlist[i]) dfs(i,n,m) answer.pop() dfs(0,n,m)

(1)과 다른 점은 오름차순으로 나열된다는 것이다. 따라서 answer에 숫자가 이미 있는지 없는지 확인해보는 코드를 추가해야한다. n,m=map(int,input().split()) visited=[False]*(n+1) answer=[] def dfs(depth,n,m): if len(answer)==m: print(*answer) return for i in range(depth,n+1): if i not in answer: answer.append(i) dfs(i+1,n,m) answer.pop() dfs(1,n,m)