RUBY

출처:: https://www.acmicpc.net/problem/1647 분류:: 최소 신장 트리 1. 문제 이해 및 해결과정 - 전체 그래프에서 2개의 최소 신장 트리를 만들어야 한다. => 최소한의비용으로 2개의 신장 트리로 분할하려면 어떻게 하면 될것인지 - 크루스칼 알고리즘으로 최소 신장 트리를 찾고 가장 큰 비용을 가지는 간선을 제거하자 2. 풀이방법 1. 크루스칼 알고리즘 #도시 분할 계획 # ''' 7 12 1 2 3 1 3 2 3 2 1 2 5 2 3 4 4 7 3 6 5 1 5 1 6 2 6 4 1 6 5 3 4 5 3 6 7 4 #출력 8 ''' import sys sys.stdin = open("input.txt","r") n,m=map(int,input().split()) pare..

출처:: 분류:: union-find 1. 문제 이해 및 해결과정 - 서로소 집합 알고리즘 문제, n과 m의 범위가 모두 10,000이상 => 경로 압축 방식의 서로소 집합 자료구조를 이용하여 시간복잡도를 개선해야함 2. 풀이방법 1. union-find #팀 결성 # import sys sys.stdin = open("input.txt","r") #0번 부터 n번까지 팀 존재, m은 연산의 개수 n,m=map(int,input().split()) parent = [0]*(n+1) def find_parent(parent,x): if parent[x]!=x: parent[x]=find_parent(parent,parent[x]) return parent[x] def union_parent(parent,a..

출처:: M기업 코딩 테스트 분류:: 플루이드 워셜 알고리즘 1. 문제 이해 및 해결과정 - N의 범위가 100이하로 매우 한정적 2. 풀이방법 1. 플루이드 워셜 #미래도시 # import sys sys.stdin = open("input.txt","r") INF = int(1e9) #10억 #노드의 개수 및 간선의 개수를 입력받기 n,m=map(int,input().split()) 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 #간선 정보 입력받기 for _ in range(m): a,b=map(int,input().split(..

그래프 : 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조 - 알고리즘 문제에서 '서로 다른 대체(객체)'가 연결되어 있다' => 그래프 알고리즘 을 떠올려야한다 - 구현 방법) 1. 인접행렬 : 2차원 배열을 사용하는 방식 - O(V^2)만큼의 메모리 공간 필요 - 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(1) 의 시간으로 알 수 있다. 2. 인접리스트: 리스트를 사용하는 방식 - O(E) 만큼의 메모리 공간 필요 - 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(V) 의 시간으로 알 수 있다. 서로소 집합(Disjoint Sets) : 서로소 집합이란 공통 원소가 없는 두 집합을 의미 ex) {1,2}, {3,4} * 서로소 집합 자료구조..

최단 경로 : 가장 짧은 경로를 찾는 알고리즘 = 길 찾기 문제 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(..