초보 개발자의 일기

플로이드 워셜 알고리즘 플로이드 워셜 알고리즘 -모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용 -소스코드가 다익스트라에 비해 짧아서 구현이 쉽다. -플로이드 워셜 알고리즘은 2차원 테이블에 최단 거리 정보를 저장한다. 플로이드 워셜 알고리즘의 점화식 그림으로 설명 초기 그래프 상태 현재 상태에서 갈 수 있는 곳을 전부 표에 적고 갈 수 없는 곳은 무한으로 설정한다. 단계 1 1번 노드를 통해 가는 경우를 고려해 테이블을 갱신한다. 단계 2 2번 노드를 통해 가는 경우를 고려해 테이블을 갱신한다. 단계 3 3번 노드를 통해 가는 경우를 고려해 테이블을 갱신한다. 단계 4 4번 노드를 통해 가는 경우를 고려해 테이블을 갱신한다. 최종적으로 나온 결과는 이렇게 된다. 플로이드 ..

최단경로 알고리즘 최단경로 알고리즘: 가장 짧은 경로를 찾는 알고리즘 노드: 각 지점은 그래프에서 노드로 표현 간선: 지점 간 연결된 도로는 그래프에서 간선으로 표현 최단 경로 알고리즘은 대표적으로 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 이렇게 3개이다. 이 중에서 다익스트라 최단 경로 알고리즘, 플로이드 워셜을 공부해보자. 다익스트라 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 음의 간선이 없을 때 정상적으로 작동 알고리즘의 원리 출발 노드를 설정 최단 거리 테이블을 초기화 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계..

문제 입력 첫째 줄에 N, M이 주어진다. (1

문제 입력 첫째 줄에 N이 주어진다. (1

문제 입력 첫째 줄에 식량창고의 개수 N이 주어진다.(3

문제 입력 첫째 줄에 정수 X가 주어진다. (1 d[i//3]+1: d[i]=d[i//3]+1 if i%5==0 and d[i]> d[i//2]+1: d[i]=d[i//2]+1 print(d[a]) Solution # 정수 X를 입력 받기 x = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 1000001 # 다이나믹 프로그래밍(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) # 현재의 수가 3으로 나누어 떨어..

다이나믹 프로그래밍 연산속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘, 메모리 공간을 약간 더 사용해 연산 속도를 비약적으로 증가시킬 수 있는 방법, 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 방법 예시 1. 피보나치 수열 점화식 프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현이 가능하다. 피보나치 함수 코드 # 피보나치 함수(Fibonacci Function)을 재귀함수로 구현 def fibo(x): if x == 1 or x == 2: return 1 return fibo(x - 1) + fibo(x - 2) print(fibo(4)) 이렇게 코드를 작성하면 심각한 문제가 발생할 수 있다. f(6)에서의 호출 과정..

문제 입력 첫째 줄에 정수 N이 주어진다. (1