Redddy's Devlog

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드 워셜 알고리즘은 플로이드와 워셜이 개발한 알고리즘으로 그래프의 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 데이크스트라 알고리즘과 비슷하게 단계별로 거쳐 가는 노드를 기준으로 최소값을 갱신하지만, 데이크스트라 알고리즘은 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾아서 방문하였다면 이 플로이드 워셜 알고리즘은 아묻따 모든 노드를 탐색한다. 인접 행렬 형태의 2차원 테이블을 만들어 최단 거리 정보를 저장한다. 이전에 한번 한 연산은 다시 반복하지 않는다는 점에서 다이나믹 프로그래밍 유형에 속한다. 이 알고리즘은 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인하여 갱신해준다. a에서 ..

다이나믹 프로그래밍 (Dynamic Programming) 다이나믹 프로그램은 동적 계획법이라고도 불리운다. 다이나믹 프로그램의 기본 모토는 중복되는 연산을 줄이는 것이다. 한번 실행한 연산들은 DP 테이블(리스트)에 저장해두고 그 연산이 필요할 때마다, 연산을 하지 않고 그 DP 테이블에서 연산데이터를 호출하는 방식이다. 이런 기법은 메모제이션 기법이다. 다이나믹 프로그래밍의 대표적인 예제로 피보나치 수열이 있다. 피보나치 수열의 점화식은 a(n) = a(n-1) + a(n-2), a(1) = 1, a(2) = 1 이다. 즉 이전 데이터와 전전 데이터를 더하여 현재 데이터가 된다. 피보나치 수열을 재귀적으로 구현한 코드는 다음과 같다. # 피보나치 함수(Fibonacci Function)을 재귀함수로 ..

📕 문제해석 기타 연주를 하는데 각 곡마다 볼륨을 변경하려고 한다. 곡마다 변경할 수 있는 숫자가 정해져있다. 그 숫자로 현재 볼륨에서 더하거나 뺄 수가 있다. 볼륨이 음수가 나오면 안되고 주어진 볼륨 값을 넘을 수도 없다. 이때 최대 볼륨은? 📖 문제풀이 1. n, s, m과 v를 입력받고 m 길이를 가진 리스트 n+1개를 만든다. (다이나믹 프로그래밍을 위한) 2. 현재 볼륨을 체크한다. 3. 시작 볼륨에서 주어진 v[i]를 더할 수 있다면 더하고 뺄 수 있다면 빼준다. 0

처음에는 단순히 itertoors에서 combinations를 import해서 사용했는데 예상했던대로 시간초과가 나왔다. (요즘 문제 푸는데 시간초과가 너무 많이 나와...ㅜ) 그래서! 조합을 combinations를 사용하는 것이 아니라 식을 factorial을 불러와서 조합의 경우의 수를 만들어 주었다. 📚 풀이 1. math 모듈을 가져와 factorial을 사용한다. 2. mCn 을 factorial을 사용해서 만든다면 => (m!/(m-n)!)/n! 3. 2번에서 사용한 식을 컴퓨터에서 실행하면 오차가 발생한다. (23 24 입력시 23.9999996이 나옴) 그래서 어차피 몫과 값이 다를리가 없기 때문에 /가 아닌 //를 사용해준다. 💻 코드 import sys, math input = sys..