RUBY

최단 경로 : 가장 짧은 경로를 찾는 알고리즘 = 길 찾기 문제 ex) 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우, 모든 지점에서 다른 모든 지점까지의 최단경로를 모두 구해야하는 경우 등 - 코딩테스트) : 최단 경로를 모두 출력하는 문제 보다는 단순히 최단 거리 출력 - 최단 거리 알고리즘 1. 다익스트라 최단 경로 알고리즘 2. 플로이드 워셜 3. 벨만 포드 알고리즘 - 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다 *다익스트라 최단 경로 알고리즘 : 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘, 한 지점에서 다른 특정 지점까지의 최단경로 구하는 경우 - '음의 간선..

출처:: 분류:: 다이나믹 프로그래밍 1. 문제 이해 및 해결과정 - 그리디의 거스름돈 문제와거의 동일하나 화폐 단위에서 큰 단위가 작은 단위의 배수가 아니라는 점이 다르다 - 그리디처럼, 가장 큰 화폐 단위부터 처리하는 방법으로는 해결할 수 없고 , 다이나믹 프로그래밍을 이용해야한다. - 구현 1) a(i-k) 를 만드는 방법이 존재하는 경우, a(i) = min(a(i),a(i-k)+1) 2) a(i-k) 를 만드는 방법이 존재하지 않는 경우, a(i) = 21470000000(큰 수) 2. 풀이방법 1.bottom-up #효율적인 화폐 구성 # import sys sys.stdin = open("input.txt","r") n,m=map(int,input().split()) coin=[] INF=2..

출처:: 분류:: 다이나믹 프로그래밍 1. 문제 이해 및 해결과정 1) i-1번째 식량창고를 털기로 결정한 경우, 현재의 식량창고를 털 수 없다. 2) i-2번째 식량창고를 털기로 결정한 경우, 현재의 식량 창고를 털 수 있다. 1번과 2번 중 더 큰 값을 선택하면 된다 => a(i) = max(a(i-1),a(i-2)+k) 2. 풀이방법 1. bottom-up #개미 전사 # import sys sys.stdin = open("input.txt","r") dp=[0]*101 n=int(input()) arr=list(map(int,input().split())) dp[0]=arr[0] dp[1]=max(arr[0],arr[1]) for i in range(2,n): dp[i]=max(dp[i-1],dp..

출처:: https://hiruby.tistory.com/266?category=396294 분류:: 다이나믹 프로그래밍 1. 문제 이해 및 해결과정 1) 왼쪽부터 i-1의 길이가 덮개로 이미 채워져 있으면 2*1 덮개를 채우는 하나의 경우의 밖에 존재 하지 않음 2) 왼쪽부터 i-2의 길이가 덮개로 이미 채워져 있으면 1*2 덮개를 2개 덮는경우, 2*2 덮개 하나를 넣는 경우로 2가지가 존재한다 3) n-2 미만의 길이에 대해서 고려할 필요가 없다. 사용할 수 있는 덮개의 최대가 2*2이기 때문이다. => ai=a(i-1) + a(i-2) + a(i-2) 2. 풀이방법 1. 다이나믹 프로그래밍 #바닥 공사 # import sys sys.stdin = open("input.txt","r") n=int(..

출처 분류:: 다이나믹 프로그래밍 1. 문제 이해 및 해결과정 https://hiruby.tistory.com/258 2. 풀이방법 1. bottom-up #1로 만들기 # import sys sys.stdin = open("input.txt","r") n=int(input()) dp=[0]*30001 cnt=0 for i in range(2,n+1): #1뺴는 경우 dp[i]=dp[i-1]+1 if i%5==0: dp[i]=min(dp[i],dp[i//5]+1) if i % 3 == 0: dp[i] = min(dp[i], dp[i // 3] + 1) if i % 2 == 0: dp[i] = min(dp[i], dp[i // 2] + 1) print(dp[n]) 3. 오답원인 4. 알게된 점

출처:: 분류:: 이진탐색 , 파라메트릭 서치 1. 문제 이해 및 해결과정 - 전형적인 이진 탐색 문제, 파라메트릭 서치 유형 - 파라메트릭 서치(Parametric Search) : 최적화 문제를 결정 문제로 바꾸어 해결하는 기법, 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 사용 - 현재 문제에서 절단기의 높이는 최대 10억까지의 정수 -> 순차탐색은 시간초과, 큰 수를 보면 당연하단 듯이 이진탐색 떠올리자!! - 이진탐색으로 찾는 다면, 대략 31번 만에 경우의 수 모두 고려 가능 - 떡의 개수 N이 최대 100만개 이므로 , 최대 3000만번 정도의 연산으로 문제를 풀 수 있음 - 문제 제한 시간 2초이므로 최악의 경우 3000만번 정도 연산이 필요하면 2초 남짓 정답 2. 풀이방법 1...

출처:: 분류:: 이진탐색 1. 문제 이해 및 해결과정 1)이진탐색 풀이 - N개의 부품 M개의찾고자하는 부품 O(MlogN) -> 200만번의 연산 - N개의 부품 정렬 O(NlogN) => 시간복잡도 : O((M+N)logN) 2. 풀이방법 1. 이진탐색 #부품 찾기 # import sys sys.stdin = open("input.txt","r") n=int(input()) a=list(map(int,input().split())) m=int(input()) b=list(map(int,input().split())) a.sort() #이진탐색 수행하기 위해 def binary_search(arr,d): s=0 e=len(a)-1 while sd: e= m - 1 elif a[m]

출처:: 국제 알고리즘 대회 1. 문제 이해 및 해결과정 2번 풀이 - 두 배열의 원소가 최대 백만개 100,000개 까지 입력될 수 있으므로O(NlogN)을 보장하는 정렬알고리즘을 이용해야한다. 2. 풀이방법 1. 정렬 이용 #두 배열의 원소 교체 # import sys sys.stdin = open("input.txt","r") n,k=map(int,input().split()) A=list(map(int,input().split())) B=list(map(int,input().split())) A.sort() B.sort(reverse=True) for i in range(k): if A[i]A[j]: minindex=j minv=A[minindex] if maxv < B[j]: maxindex=j..