Algorithm
-
위상 정렬(Topological Sort)Algorithm/이론 2020. 11. 29. 19:04
위상 정렬 방향이 있는 그래프의 순서 정렬 위상 정렬이 가능하려면 DAG(Directed Acycle Graph, 방향성이 있으며 사이클이 없는 그래프)이여야 한다. 위상 정렬을 구현하는 방법에는 DFS를 사용하거나 indegree 배열을 사용하여 구현하는 방법이 있다. 본 포스팅에서는 후자를 선택하여 구현하는 방법을 알아볼 것이다. 필요한 자료구조 & 변수 변수 설명 List graph 그래프 관계 표현을 위한 2차원 인접 리스트 int[] indegree 해당 노드를 가리키는 간선의 갯수를 담기 위한 배열 Queue q indegree 값이 0이 된 노드를 담기 위한 Queue List result 결과를 담기 위한 리스트 Flow 1. indegree가 0인(=나를 가리키는 노드가 없는) 노드들을 ..
-
[BOJ] 행성 터널Algorithm/BOJ 2020. 11. 28. 17:20
[2887] 행성 터널 www.acmicpc.net/problem/2887 Solution 행성들을 잇는 최소 간선 트리를 만드는 간단한 문제이다. 처음에는 행성을 이을 수 있는 모든 간선을 미리 구해서 푸는 방식으로 접근했는 데 메모리 초과로 틀렸다. int x, y, z -> 12byte이고, 행성 개수가 최대 10만개이기 때문에 (10만 * 10만 / 2) = 약 50억으로 12byte * 50억이라하면 메모리가 초과될 수 밖에 없었다. 문제를 다시 한 번 살펴보면 행성의 x, y, z 좌표를 각각 비교해서 최소 비용을 구하는 것이므로 모든 행성간의 비용을 계산할 필요 없이 좌표 별로 오름차순으로 정렬한 뒤 바로 옆 행성만 비교하면 된다. 예를들어 행성 A, B, C의 x좌표를 기준으로 정렬한 결과..
-
[BOJ] 진우의 민트초코우유Algorithm/BOJ 2020. 11. 27. 17:12
[20208] 진우의 민트초코우유 www.acmicpc.net/problem/20208 Solution 집 - 민초s - 집 까지 체력을 유지하면서 돌아올 수 있는 경우 중 최대 민초집 수를 구하는 문제 permutation으로 민초집 수를 늘리면서 & 순서를 달리한 경로를 pick 배열에 저장했고, 체력을 유지한 채 집까지 돌아올 수 있는 최대 민초집 수를 answer에 저장하여 풀었다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61..
-
[BOJ] 인구 이동Algorithm/BOJ 2020. 10. 28. 14:16
[16234] 인구 이동 www.acmicpc.net/problem/16234 Solution 문제에 명시된 국경선을 map[][]에서 1*1 크기의 칸으로 정의하였고, 인접한 국가와의 인구차가 범위 안에 있을 경우에 0으로 표시했다. 모든 국경선에 표시한 뒤 bfs 함수로 연합이 되는 국가의 인구수의 합과 평균을 구해 map[][]에 표시했다. 조건을 만족하는 국경선이 없을 때 까지 while문은 반복된다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 ..
-
[BOJ] 택배Algorithm/BOJ 2020. 10. 24. 01:56
[1719] 택배 www.acmicpc.net/problem/1719 Solution 모든 정점에 대해 다익스트라 함수를 실행하여 update된 prev[]의 정보를 활용해서 첫 번째로 경유하는 정점을 찾았다. 돌아서면 까먹는 다익스트라 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90..
-
[BOJ] 찾기Algorithm/BOJ 2020. 10. 23. 15:14
[1786] 찾기 www.acmicpc.net/problem/1786 Solution KMP 알고리즘을 사용해 원본 문자열 t에서 패턴 p를 찾았을 때 count 증가, StringBuilder에 순서 저장으로 구현 단순하게 모든 문자열을 일일이 비교하는 방법을 사용했을 때의 시간 복잡도는 O(NM) 이지만, KMP 알고리즘을 사용하면 O(N+M)의 시간 복잡도를 보인다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 import..
-
[BOJ] 미로만들기Algorithm/BOJ 2020. 10. 22. 15:02
[2665] 미로만들기 www.acmicpc.net/problem/2665 Solution 2차원 배열에 대해서 다익스트라로 풀이하는 문제 map[0][0]을 시작점으로 distance[0][0] = 0 으로 할당한 뒤, 4방향에 대해 흰방일 경우에는 방 교체 횟수를 그대로 update하고, 검은방일 경우에는 이전 방 교체 횟수 + 1한 값으로 update 하고 q에 add한다. 마지막으로 distance[n-1][n-1] 출력 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 5..
-
[BOJ] 복도 뚫기Algorithm/BOJ 2020. 10. 21. 16:21
[9373] 복도 뚫기 java www.acmicpc.net/problem/9373 Solution 넘나 어려운 문제. 답 안 봤으면 절대 못 풀었을거 같다 ㅠ^ㅠ.. n개의 센서와 벽을 정점으로 정의하고 벽-센서, 센서-센서를 잇는 간선으로 정의 하여 MST를 만든다. 모든 간선이 들어간 우선순위 큐에서 간선을 뽑으면서 복도를 지나갈 수 있는 센서의 반지름을 구하고 양 벽을 잇는 간선이 나올경우에 프로그램을 종료한다. 양 벽을 잇는 간선의 길이(w)가 복도를 지나갈 수 있는 최대 지름이기 때문이다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40..