밤이 블로그

* 순열 (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) 두 ..

* 문제https://www.acmicpc.net/problem/1005 * 풀이건물 X를 지은 다음에 건물 Y를 건설할 수 있다.어떤 일에 선, 후 관계/순서가 있으므로 위상정렬을 이용해보았다. - 위상정렬 설명http://navercast.naver.com/contents.nhn?rid=2871&contents_id=91824 Queue q = new LinkedList(); // indegree가 0인 노드들을 Queue에 넣는다. for (int i = 1; i

* 문제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..

* 문제https://www.acmicpc.net/problem/1002 * 풀이 : 두 원의 위치 관계를 수학식으로 표현할 수 있어야 한다. d < r - r' ≤ d ≤ r + r' < d 1) 두 좌표가 같은 경우 반지름까지 같은 경우 : -1 (무한대) 반지름이 다른 경우 : 0개 2) 두 좌표가 다른 경우 d < r - r' or r + r' < d : 0개 r - r' = d or d = r + r' : 1개 r - r'

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..