본문 바로가기
반응형

전체 글1308

[Jungol] 정올 1405 하노이3(4기둥) 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=681&sca=4030 Input 2 Output 3 1 : A->B 2 : A->D 1 : B->D ▶ hanoi4(n, 1, 2, 3, 4) : 1번 기둥에 있는 n개의 원판을 4번 기둥으로 이동시키는데 2, 3번을 여분의 기둥으로 이용 hanoi4(n, 1, 2, 3, 4)에서 n개의 원판 중 일부인 K개를 2번 기둥에 이동시키는 것을 hanoi4(k, 1, 3, 4, 2)라고 할 수 있습니다. (여분의 기둥을 한 개 활용하고자 하는 것이기 때문에 3번 기둥으로 이동한다고 생각해도 상관 X) (이때, K는 임의의 수가 될 수 없으면 최적화 수치가 필요합니다.) k개를 2번 기둥에 옮겨놓았.. 2021. 2. 27.
[Jungol] 정올 1912 미로탐색 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1185&sca=30 Input 5 6 1 3 3 4 4 2 2 1 1 4 4 5 Output 1 2 4 3 5 N이 작지 않은 숫자이기 때문에 인접행렬 보다는 인접리스트로 그래프 연결 정보를 표시합니다. 그래프 정보에 앞서 주어지는 Input Data 정렬되어 있지 않기 때문에 시간효율을 위해서는 mergeSort나 quickSort를 이용해서 정렬해야 합니다. ex) 정렬 시 양방향 연결을 고려해서 연결정보를 표시한 후 정렬 (2, 4) (1, 3)가 주어질 때 → (1, 3) (2, 4) 주어진 것들만 정렬하는 것이 아닌 → (1, 3) (2, 4) (3 1) (4 2) 양방향 정보를 배.. 2021. 2. 27.
[Jungol] 정올 1824 스도쿠 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1097&sca=3030 Input 0 3 5 4 6 9 2 7 8 7 8 2 1 0 5 6 0 9 0 6 0 2 7 8 1 3 5 3 2 1 0 4 6 8 9 7 8 0 4 9 1 3 5 0 6 5 9 6 8 2 0 4 1 3 9 1 7 6 5 2 0 8 0 6 0 3 7 0 1 9 5 2 2 5 8 3 9 4 7 6 0 Output 1 3 5 4 6 9 2 7 8 7 8 2 1 3 5 6 4 9 4 6 9 2 7 8 1 3 5 3 2 1 5 4 6 8 9 7 8 7 4 9 1 3 5 2 6 5 9 6 8 2 7 4 1 3 9 1 7 6 5 2 3 8 4 6 4 3 7 8 1 9 5 2 2 .. 2021. 2. 27.
[Jungol] 정올 1161 하노이1 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=441&sca=2070 Input 3 Output 1 : 1 -> 3 2 : 1 -> 2 1 : 3 -> 2 3 : 1 -> 3 1 : 2 -> 1 2 : 2 -> 3 1 : 1 -> 3 ▶ hanoi(원판 수, 시작 기둥 번호, 도착 기둥 번호) hanoi(3, 1, 3)으로 3번 기둥의 바닥에 3번 원판이 놓여야 하므로 1, 2번 원판을 2번 기둥으로 옮겨야 한다. 결과적으로 3번 원판이 없다고 생각하면, hanoi(2, 1, 2)로 나타낼 수 있다. 즉, 도착 기둥번호가 3번이 아닌 2번으로 하면서 원판 개수도 2개인 문제와 같다. 위의 작업이 끝나서 1, 2번 원판이 두번째 기둥에 있다.. 2021. 2. 27.
[BOJ] 백준 8980 택배 (Segment Tree + Lazy Propagation) Segment Tree + Lazy Propagation을 이용한 풀이입니다. 다른 풀이는 [BOJ] 8980 택배 참고 [BOJ] 백준 8980 택배 출처: https://www.acmicpc.net/problem/898 Input 4 40 6 3 4 20 1 2 10 1 3 20 1 4 30 2 3 10 2 4 20 Output 70 트럭이 이동할 때, 도착지가 가까울수록 짐 공간을 점유하는 시간이 적으므로 좋습니다. 따.. zoosso.tistory.com 출처: https://www.acmicpc.net/problem/8980: Input 4 40 6 3 4 20 1 2 10 1 3 20 1 4 30 2 3 10 2 4 20 Output 70 도착지 기준으로 박스들을 정렬한 뒤, (도착지가 가까울.. 2021. 2. 27.
[BOJ] 백준 8980 택배 출처: https://www.acmicpc.net/problem/898 Input 4 40 6 3 4 20 1 2 10 1 3 20 1 4 30 2 3 10 2 4 20 Output 70 트럭이 이동할 때, 도착지가 가까울수록 짐 공간을 점유하는 시간이 적으므로 좋습니다. 따라서 최대한 많이 싣기 위해서는 도착지가 가까운 순 (동일한 경우, 출발지가 빠른 순으로 박스 정렬) 박스를 실을 수 있는 개수가 한정적이므로 최대한 많은 박스를 실을려고 시도합니다. (일부 박스만 배달 가능) * 트럭이 마을 지나갈 때 짐이 얼마나 있는지 확인 ① 개수 = 10, 배달 구간 = 1 → 2 현재 트럭에 실린 짐이 없으므로 모두 싣습니다. ② 개수 = 20, 배달 구간 = 1 → 3 트럭에 실린 양은 10개 이므로 남은.. 2021. 2. 27.
BFS (Breadth-First Search, 너비 우선 탐색) BFS 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문합니다. Queue 이용 * DFS로 풀리는 문제는 일반적으로 BFS로도 풀 수 있습니다. Process ※ 깊이 우선 탐색과는 달리 너비 우선 탐색에서는 발견과 방문이 같지 않습니다. ① 아직 발견되지 않은 상태 ② 발견되었지만 아직 방문되지 않은 상태 (큐에 저장되어 있는 상태) ③ 방문된 상태 DFS와 BFS 비교 출처: 나무위키 경로 비교 BFS - Queue 이용 - 최소신장트리(Minimum Spanning Trees), 최단경로(Shortest Paths) 장점: 무한히 깊거나 무한에 가까운 트리인 경우에 효과적 단점: 목표 노드로 가는 경로들 모.. zoosso.tistory.com 활용 최단 경로를 찾을 때 유용 ※ BFS와 달.. 2021. 2. 27.
깊이 우선 탐색(depth-first search, DFS) DFS 그래프의 모든 정점을 방문할 때 최대한 깊숙히 정점을 방문하는 방식입니다. - Stack 이용 즉, 연결된 정점을 따라 계속 순회하다가 갈 곳이 없어지며 바로 이전단계로 가는 백트래킹 방식. (깊이 우선 탐색은 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' 들어가려고 시도하며, 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않습니다. 더 따라갈 간선이 없을 경우 이전으로 돌아갑니다.) 특징 - 찾고자 하는 해가 깊은 곳에 있으면 유용하지만 Stack OverFlow에 유의해야 합니다. - BFS의 경우에는 탐색과정에서 목표를 찾으면 최단경로에 해당되지만 DFS는 최단경로가 아닐 수 있습니다. ▶ DFS와 BFS 비교 DFS와 BFS 비교 출처: 나무위키 경로 비교 BFS - Queue 이용 .. 2021. 2. 27.
[BOJ] 백준 1922 네트워크 연결 출처: https://www.acmicpc.net/problem/1922 Input 6 9 1 2 5 1 3 4 2 3 2 2 4 7 3 4 6 3 5 11 4 5 3 4 6 8 5 6 8 Output 23 ▶ 가중치 합: 2 + 3 + 4 + 6 + 8 = 23 ▶ 최소 신장 트리를 구현하는 문제로, 크루스칼Kruskal 알고리즘 구현 최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal) 최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal) 최소 신장 트리(MST, Minimum Spanning Tree) ; 사이클을 형성하지 않으면서 모든 간선(Edge)가 최소로 연결된 그래프. ※ 신장 트리(Spanning Tree); 사이클을 형성하지 않지만 모든 노드가 간선(Edge)로 연결... 2021. 2. 27.
[BOJ] 백준 1197 최소 스패닝 트리 출처: https://www.acmicpc.net/problem/1197 Input 3 3 1 2 1 2 3 2 1 3 3 Output 3 Path: ① -- ② -- ③ cost: 1 2 = 3 ▶ 프림(Prim) 알고리즘 구현 시작정점으로 부터 가중치가 낮은 간선으로 정점을 연결해 나가는 방법 ※ 최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal) 최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal) 최소 신장 트리(MST, Minimum Spanning Tree) ; 사이클을 형성하지 않으면서 모든 간선(Edge)가 최소로 연결된 그래프. ※ 신장 트리(Spanning Tree); 사이클을 형성하지 않지만 모든 노드가 간선(Edge)로 연결. zoosso.tistory.com 시.. 2021. 2. 27.
반응형

티스토리툴바