Algorithm/BOJ
-
[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..
-
[BOJ] 도시 분할 계획Algorithm/BOJ 2020. 10. 19. 20:50
[1647] 도시 분할 계획 www.acmicpc.net/problem/1647 Solution 마을을 정점으로 하는 최소 간선 트리(MST)를 만드는 문제 전체 마을을 두 개로 분할해야하기 때문에 간선의 개수가 N-2개가 되는 순간 종료하면 된다. 소스코드 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 import jav..
-
[BOJ] 녹색 옷 입은 애가 젤다지?Algorithm/BOJ 2020. 10. 19. 19:56
[4485] 녹색 옷 입은 애가 젤다지? www.acmicpc.net/problem/4485 Solution 각 동굴의 칸을 정점으로 정의하고, 다익스트라를 활용했다. map의 (0, 0)을 다익스트라의 시작점으로 정하고 (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 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 8..
-
[BOJ] 치즈Algorithm/BOJ 2020. 10. 19. 14:56
[2636] 치즈 www.acmicpc.net/problem/2636 Solution map의 (0, 0) 위치에서 치즈의 개수가 0이 될 때 까지 bfs 함수를 실행한다. 팀색 중에 치즈의 바깥부분, 1인 부분을 찾으면 map에서 0으로 바꾸고 visited 배열에 방문표시를 해준다. 한 번의 bfs 탐색마다 1씩 증가하는 시간을 answer 변수에 담고, 마지막 치즈 개수는 count 변수에 bfs 함수가 끝날 때 마다 업데이트 한다. 소스코드 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 5..
-
[BOJ] 후보 추천하기Algorithm/BOJ 2020. 10. 4. 16:05
[1713] 후보 추천하기 www.acmicpc.net/problem/1713 Solution 문제에서 주어진 조건대로 구현하면 되는 문제 idx, like, order 속성을 가진 Student 객체를 만들어 추천받은 순서 대로 우선순위 큐에 넣었다. 우선순위 큐의 정렬 조건은 like, 추천수가 작은 Student가 먼저 빠져나오고 추천수가 같은 경우에는 order, 들어간 순서가 오래된 Student가 먼저 나오도록 했다. 추천받을 학생이 이미 우선순위 큐에 들어있는 경우에는 해당 학생은 like, 추천수를 업데이트 한 후 다시 넣어줬다. 우선순위 큐에 들어있는 Student를 뽑지 않고 큐 들어있는 상태에서 like를 업데이트 하면 큐의 정렬 조건에 반영되지 않으므로 모든 Student 객체를 뽑..
-
[BOJ] 다리 만들기 2Algorithm/BOJ 2020. 9. 8. 19:46
[17472] 다리 만들기 2 www.acmicpc.net/problem/17472 Solution 다리 만들기 2 문제는 기존의 다리 만들기 문제와 세 가지 다른점이 있다. 다리의 모양에 제한이 있는 것과 한 개의 다리가 아닌 모든 섬을 연결하는 다리를 만드는 것 그리고 다리의 길이는 최소 2 이상이어야 한다는 것이다. 모든 섬을 연결하는 최소 비용의 다리를 만든다는 점에서 Spanning Tree idea를 떠올려야 한다. 먼저 각각의 섬을 구분하기 위한 numbering 작업을 수행한다. MST(최소 신장 트리)를 구하기 위해 크루스칼 알고리즘을 사용했다. map의 모든 cell에 대해 DFS로 섬과 섬을 연결하는 비용(거리)을 구해 우선순위 큐에 넣는다. 이때 주의할 점은 다리는 'ㅡ' 혹은 'l..