알고리즘 문제/자료구조&알고리즘19 최단경로 예제 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수 및 간선의 개수를 입력받기 n, m = map(int, input().split()) # 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화 graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 for a in range(1, n + 1): for b in range(1, n + 1): if a == b: graph[a][b] = 0.. 2020. 10. 24. 최단 경로 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 # 간단한 다익스트라 알고리즘 import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수, 간선의 개수를 입력받기 n, m = map(int, input().split()) # 시작 노드 번호를 입력받기 start = int(input()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를.. 2020. 10. 23. 다이나믹 프로그래밍 예제 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 # 정수 X를 입력받기 x = int(input()) # 앞서 계산된 결과를 저장하기 위한 dp 테이블 초기화 d = [0] * 30001 # 다이나믹 프로그래밍(Dynamic programming) 진행(보텀업) for i in range(2, x+1): # 현재의 수에서 1을 빼는 경우 d[i] = d[i - 1] +1 # 현재의 수가 2로 나누어 떨어지는 경우 if i % 2 == 0: d[i] = min(d[i], d[i // 2] +1) if i % 3 == 0: d[i] = min(d[i], d[i // 3] +1) if i % 5 == 0: d[i] = min(d[i], d[i // 5] +1) Colored b.. 2020. 10. 22. 다이나믹 프로그래밍 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 # 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화 d = [0] * 100 # 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍) def fibo(x): print('f('+str(x)+')', end=' ') # 종료 조건(1 혹은 2일 때 1을 반환) if x == 1 or x == 2: return 1 # 이미 계산한 적 있는 문제라면 그대로 반환 if d[x] != 0: return d[x] # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 .. 2020. 10. 22. 다이나믹 프로그래밍 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 # 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화 d = [0] * 100 # 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍) def fibo(x): print('f('+str(x)+')', end=' ') # 종료 조건(1 혹은 2일 때 1을 반환) if x == 1 or x == 2: return 1 # 이미 계산한 적 있는 문제라면 그대로 반환 if d[x] != 0: return d[x] # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 .. 2020. 10. 22. 이진 탐색 예제 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 # 이진 탐색 소스코드 구현(반복문) def binary_search(array,target, start, end): while start target: end = mid -1 else : start = mid +1 return None # N(가게의 부품 개수) 입력 n = int(input()) # 가게에 있는 전체 부품 번호를 공.. 2020. 10. 22. 이전 1 2 3 4 다음