CS/Algorithm90 [알고리즘][DP][1010] 다리놓기 [알고리즘][DP][1010] 다리놓기 * 풀이 핵심은 선이 겹칠 수 없다는 것이다. 단순히 콤비네이션을 이용하여 풀 수 있지만 DP로 풀어보려하다 삽질을 많이 했다. 선이 1개일 때와 선이 2개 이상일 때를 구분지었다. 두번째 선부터 선이 겹치지 않는 것을 고려해줘야하기 때문! arr[n][m] 가 n에서 m으로 가는 선이라고 했을 때 m은 최소한 n과 같아야 한다. 왜냐하면 n-1, n-2 ...가 선을 하나씩 차지했을 것이기 때문! * 코드 12345678910111213141516171819202122232425262728293031323334353637package algorithm_DP; import java.util.Scanner; public class q_1010 { static int .. 2018. 4. 13. [알고리즘][플로이드와샬][1389] 케빈 베이컨의 6단계 법칙 [알고리즘][플로이드와샬][1389] 케빈 베이컨의 6단계 법칙 * 문제 https://www.acmicpc.net/problem/1389 과거에 '링크'라는 책에서 이 법칙을 본 적이 있는데 알고리즘으로 풀면서 고생하니 더욱 인상깊은 법칙..... 아무튼 풀이는 이렇다! 초반에는 별 생각없이 DFS로 풀려고 덤볐다가 뭔가 잘못됐다는 것을 깨닳고 다시 풀기 시작했다. 이러한 문제에 가장 보편적으로 적용되는 알고리즘이 플로이드 와샬 알고리즘이라는 것을 처음 알게 되어 이에 대해 공부하고 다시 풀었다. 알고리즘 자체도 이해가 쉽지 않았지만 몇몇 분들이 친절하게 설명을 해주셔서 보다 쉽게 이해했다. * 풀이 플로이드 와샬 알고리즘을 적용하여 푼다. 해당 알고리즘에 관한 설명은 http://heekim0719... 2018. 4. 12. [알고리즘] 플로이드-와샬 알고리즘 [알고리즘] 플로이드 와샬 알고리즘 * 플로이드 와샬 알고리즘이란? - 그래프에서 모든 꼭지점 사이의 최단 경로의 거리를 구하는 알고리즘이다. - 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. - 3중 for문 중 제일 바깥쪽 반복문은 겨쳐가는 꼭지점이다. 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점 - 시간 복잡도는 3중 for문으로 인한 O(n^3) 이다. - 다익스트라, 벨만 포드 알고리즘은 하나의 시작점에 대해 최단 경로를 찾아주지만 플로이드 워셜 알고리즘은 모든 정점에 대해 모든 다른 정점에 대한 최단 경로를 다 구해준다. - 많은 시간이 소요되지만 이 알고리즘을 이용해 해결해야 할 상황도 존재하므로 중요! (참조 : 위키백과, http://www.crocus... 2018. 4. 12. [알고리즘][DFS][11403] 경로찾기 [알고리즘][DFS][11403] 경로찾기 https://www.acmicpc.net/problem/11403 [풀이]DFS의 기본 개념을 알고 있다면 쉽게 풀 수 있는 문제이다. 기본에 충실한 문제라서 더욱 중요하기 때문에 더욱 잘 기억해 둬야겠다고 생각한 문제이다. 1. 입력을 받은 뒤 깊이탐색을 하고 그것을 check배열에 입력한다.2. check배열을 그대로 result배열에 넣어주면 된다. [코드] 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152package algorithm_DFS; import java.util.Arrays;import java.util.Scanner; .. 2018. 4. 11. 이전 1 ··· 10 11 12 13 14 15 16 ··· 23 다음