Algorithm 195

순열 (Permutation)

* 순열 (Permutation) : 서로 다른 n개의 원소에서 r개를 중복을 허용하지 않고 선택하여 순서 있게 늘어 놓은 것을 nPr로 표시한다 문제. { 1, 2, 3, 4 } arr 배열의 4개의 원소에서 3개를 중복을 허용하지 않고 선택하여 순서 있게 나열하는 모든 경우의 수를 출력하시오. (Java) 풀이.Permutation을 구현하려면 어떻게 해야 할까? 아래 그림을 보고 힌트를 얻어보자. 재귀(Recursive) - dfs를 이용하여 풀 수 있을 것 같다. int[] arr = { 1, 2, 3, 4 }; 1) arr[0] → arr[1] → arr[2] → arr[3] 순서로 진행하자. 2) 첫 번째로, arr[0]의 값은 [0], [1], [2], [3]과 swap될 수 있다.3) 두 ..

Algorithm/기타 2016.11.04

BOJ#1004_어린 왕자

* 문제https://www.acmicpc.net/problem/1004 * 풀이 (생각의 흐름)주어진 예제 그림에서 힌트를 얻었다.→ 출발점을 감싸고 있는 원의 수 + 도착점을 감싸고 있는 원의 수 : 주어진 예제에서는 OK→ 그러나 한 원이 출발점과 도착점을 모두 포함하는 경우 : NG→ 따라서 위 경우의 수를 제외해야 함 ※ 출발점을 감싸고 있는 원의 수 + 도착점을 감싸고 있는 원의 수 - 두 점을 모두 포함하는 원의 수 = 출발점이나 도착점 1개만 포함하고 있는 원의 수 * 코드 for (int j = 0; j < n; j++) { st = new StringTokenizer(br.readLine()); Circle c = new Circle(Integer.parseInt(st.nextToken..

Algorithm/수학 2016.11.04

삽입 정렬(순차/일반), 선택 정렬

1. 일반 삽입 정렬(Insertion Sort) : 이미 정렬되어 있는 배열에 추가 요소를 적절한 위치에 삽입(끼워넣기)함으로써 정렬을 수행하는 알고리즘이다. : 평균/최악 시간복잡도 O(n^2)으로 느린 정렬 방식이다. : 정렬 수행 시 추가 저장 공간이 필요하지 않는 In-Place 알고리즘이다. : 구현이 용이하다. // 일반 삽입 정렬 static void insertionSort(int[] data) { int pos, tempValue; System.out.println("\n\n"); for (int i = 1; i < data.length; i++) { System.out.print(i + "회전 : "); System.out.print(Arrays.toString(data)); Syst..

Algorithm/기타 2016.11.04