🦕 공룡이 되자!

import heapq import sys input=sys.stdin.readline INF=int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수, 간선의 개수를 입력받기 n, m = map(int, input().split()) # 시작 노드 번호를 입력받기 start = int(input()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기 graph = [[] for i in range(n+1)] # 최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n+1) # 모든 간선 정보를 입력받기 for _ in range(m): a, b, c = map(int, input().split()) # a번 노드에서 b번 노드로 가는 비용이 c..

힙 라이브러리 사용 # 최소 힙 import heapq # 오름차순 힙 정렬(Heap Sort) def heapsort(iterable): h=[] result=[] # 모든 원소를 차례대로 힘에 삽입 for value in iterable: heapq.heappush(h, value) # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기 for i in range(len(h)): result.append(heapq.heappop(h)) return result result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]) print(result) 실행결과 >>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # 최대 힙 import heapq # 내림차순 힙 정렬(Hea..

다익스트라 알고리즘 특정 노드에서 다른 노드까지의 최단 경로 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않음 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류(DP로도 분류가 되기도 함) 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 전체적인 흐름 출발 노드 설정 출발 노드를 기준으로 각 노드의 최소 비용 저장 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 위 과정 3~4를 반복 알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있음 처리 과정에서 더 짧은 경로를 찾으면 ‘이제..

플로이드 와샬 알고리즘 모든 노드를 방문하는 최단경로 # 전체적인 예시로써만 참고! # 비용 배열 values=[2**31-1 for i in range(n)] # 문제에서 가져온 듯 # 방문 배열 visited =[False for i in range(n)] # 0번 노드를 시작점으로 설정 start=0 visited[start]=True values[start]=0 # 방문하지 않은 노드가 있다면 while False in visited: # 노드 완전 탐색으로 비용 및 배열의 거리 값 최소화 for i in costs:#?? 이건 어디서 나왔지? 이것도 예시 각 노드별 비용으로 예상이됨 if(visited[i[1]]==False and i[0]==start): values[i[1]]=min(valu..

def solution(N, number): answer = -1 dp = [] # N 갯수 파악 위한 리스트 for i in range (1,9) : result = set() # 연산 결과 값 n2 = int(str(N)* i) # N으로 만들 수 있는 숫자 result.add(n2) for j in range(0,i-1): # ex) 3 = 2연산1 또는 1연산2 또는 3 for op1 in dp[j]: for op2 in dp[-j-1] : result.add(op1 - op2) result.add(op1 + op2) result.add(op1 * op2) if op2 != 0: result.add(op1 // op2) if number in result: answer = i break dp.ap..

풀이 1 def solution(triangle): answer=0 result=[ [] for i in range(len(triangle))] result[0].append(triangle[0]) # 0 result[1].append(triangle[0][0]+triangle[1][0]) result[1].append(triangle[0][0]+triangle[1][1]) # 1 result[2].append(result[1][0]+triangle[2][0]) result[2].append(max(result[1][0]+triangle[2][1],result[1][1]+triangle[2][1])) result[2].append(result[1][1]+triangle[2][2]) # 2 # 위에 있는 ..