밤이 블로그

BOJ#3665 최종 순위 * 문제https://www.acmicpc.net/problem/3665 * 풀이위상 정렬 문제입니다. - 위상 정렬 설명 : http://terms.naver.com/entry.nhn?docId=3579618&cid=59086&categoryId=59093 첫 예제를 통해 어떻게 문제를 풀지 생각해보겠습니다. 5 4 3 2 1 1. 간선과 indegree를 아래와 같이 추가합니다. 간선의 경우 인접리스트보다는 인접행렬로 구현하는게 더 효율적일 것 같습니다. 5->4, 5->3, 5->2, 5->14->3, 4->2, 4->13->2, 3->12->1 [0, 4, 3, 2, 1, 0] int[][] graph = new int[n + 1][n + 1];// n^2 으로 인접행렬..

BOJ#10814 나이순 정렬 * 문제https://www.acmicpc.net/problem/10814 * 풀이PriorityQueue를 이용해보았습니다.나이순으로 정렬하고나이가 같은 경우 입력 순서대로 출력되는 것을 보장하지 않으므로 order 변수를 하나 추가해서 해결하였습니다. (다른 풀이)정렬할 필요 없이 ArrayList의 배열을 선언하고 나이 idx에 맞게 이름을 추가해주면 됩니다. * 나의 코드https://github.com/stack07142/BOJ/blob/062e7ce8f6877dc0ca458b108ed6b2cc8c2b4fbe/BOJ%2310814_SortByAge/src/Main.java import java.io.*; import java.util.PriorityQueue; im..

BOJ#11650 좌표 정렬하기 * 문제https://www.acmicpc.net/problem/11650 * 풀이쉬운 문제이지만 실수했던 점 -> x에 대해 확실히 기준을 세워줄 것 틀림@Override public int compareTo(Coordinate o) { return this.x o.x ? 1 : this.y < o.y ? -1 : 1; } * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%2311650_Aligning..

BOJ#2252 줄 세우기 * 문제https://www.acmicpc.net/problem/2252 * 풀이 어떤 일에 선/후 관계나 순서가 있으므로 위상 정렬을 이용해보았습니다. -> 위상 정렬 설명 : http://navercast.naver.com/contents.nhn?rid=2871&contents_id=91824 주의할 점으로는32000 * 32000 배열이 선언이 안되므로 (Heap 사이즈)ArrayList를 사용했습니다. * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%232252_Lineup/src import java.io.*; import java.util.*; /** * BOJ#2252 줄세우기 * https://www.acmic..

BOJ#13415 정렬 게임 * 문제https://www.acmicpc.net/problem/13415 * 풀이시간 제한 때문에 생각할게 많은 문제입니다.주어진 정렬 Order를 모두 수행하는 경우 시간 초과가 발생하기 때문입니다. 알고리즘 #1. 필요 없는 정렬 Order는 무시한다.ex)104 1 5 2 3 10 8 11 15 663 24 55 43 22 13 1 오름차순을 (+), 내림차순을 (-)라고 했을 때,+3 → -2 → +4 → -5 → +5 → -4 → +3 → -2 → +2 → -1 → +3 → -1 에서+3 → -2 → +4 → -5 → +5 → -4 → +3 → -2 → +2 → -1 → +3 → -1 회색 음영은 수행하지 않아도 되므로결국 +5 → -4 → +3 → -1 으로 줄일..

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