CS/Algorithm10 [Algorithm] TSP 세일즈맨 알고리즘 TSP 알고리즘: Traveling Sales Person Problem 은 1 부터 n 까지 도시를 방문하고 다시 처음으로 돌아오는 경로중 가장 작은 비용을 선택하는 문제 1. 완전 탐색 = O(N!) -> n 이 조금만 커도 안됨 2. DP 이미 방문한 노드들의 경로는 다음 경로를 결정할때 영향을 주지 않는다. 다만 이전에 방문 했는지 여부는 영향을 끼친다. 그 이후 값중 최소가 되는 경로를 TSP ( here , visit )로 나타내자. (1 ) visit 를 어떻게 표현할것인가 -> 비트마스크 (방문했으면 1, 아니면 0) // 방문여부만 중요 ex ) 2, 3, 7번 방문 = 1000110 (2) 점화식? here 이후의 선택은 방문하지 않은 i 노드로 가는 경로를 w[ here ] [ i ].. 2017. 6. 28. [Java] 백준9663 N-Queen https://www.acmicpc.net/problem/9663 가로세로대각선으로 움직일 수 있는 막강한 말인 Queen을 서로 공격할 수 없는 위치에 놓는 경우의 수를 구하는 문제. 한줄에 하나의 Queen밖에 못 놓으므로 맵을 다 선언해주지 않아도 됨.N크기의 배열을 선언한 후 재귀로 경우의 수를 구한다.조건 1. 같은 열에 있거나조건 2. 대각선에 위치할 경우를 제외하고 찾는다. import java.util.Scanner;public class Problem9663_NQueen {static int path[] = new int[16];static int n;static int ans;public static void main(String[] args) {Scanner sc = new Scann.. 2017. 5. 21. [Java] 백준 2252 쉬운 위상정렬 https://www.acmicpc.net/problem/2252 배열에 컬렉션프레임웍을 선언해 놓은 뒤 후위 노드들을 add해 주었다.위상정렬 개념을 익히기에 좋은 문제다. import java.util.LinkedList;import java.util.Scanner;public class Problem2252_TopologicalSort2 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();LinkedList graph[] = new LinkedList[n+1];int indegree[] = new int[n+1];for(int i=1; i 2017. 5. 21. [Java] 백준 1005 위상정렬 https://www.acmicpc.net/problem/1005 위상정렬 (TopologicalSort) 알고리즘은 선행되어야 할 노드와 그 후위 노드를 정렬하는 알고리즘 이다.나는 배열에 컬렉션프레임웍을 선언하여 후위노드들을 add해주었다. import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class Problem1005_TopologicalSort {public static int time[];public static int maxtime[];public static int N, K, W;public static LinkedList graph[]; //인접 리스트 그래프public static int .. 2017. 5. 21. 이전 1 2 3 다음
