전공
-
백준 1865(웜홀)전공/알고리즘 2020. 7. 10. 00:21
https://www.acmicpc.net/problem/1865 1865번: 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀 www.acmicpc.net 운동하려고 노트북 켰다가 학교 학회의 갓 906bc의 답변을 받고 깨달았다. 그래서 지금 정리하지 않으면 내일 또 귀찮아 할까봐 지금 쓰게되었다. 이 문제는 사이클이 존재하냐 안 하냐의 문제이다. 과연 사이클은 어떻게 알 수 있을까? 다수 vs 다수 최단거리를 구하는 걸 두번하면 되지 않을까 생각을 한다. 결론은 플로이드 와샬을 두번? 사용하면 어떨까. 만약에 그러니깐, 최단 거리로 가려고 하는..
-
백준 1738(골목길) 벨만포드전공/알고리즘 2020. 7. 9. 18:05
https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 �� www.acmicpc.net 벨만포드 알고리즘을 알고 있으면 딱 봐도 벨만포드 알고리즘을 사용하는 문제같다. 왜냐하면 음수간선이 존재하고, 사이클이 존재하는지도 확인을 해야하는 문제이기 때문. 문제에서 지나갈 때마다 계속해서 돈을 줍고, 잃는다고 하니 그냥 일반 최단거리 문제처럼 풀 수 있다. 아 그런데 여기서 돈을 최대한 적게 뺏기고, 많이 얻어야 하므로, 최대거리를 구하는 문제가 된다. 역시 ..
-
백준 11657(타임머신)전공/알고리즘 2020. 7. 3. 17:29
https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 개빡대가리였었던 문제 N개의 도시가 있고, M개의 이동경로가 있다. 만약 1번의 도시에서 나머지 도시까지 최단경로로 갈때, 그 최단거리를 구하는 문제. 다익스트라 하지만 다 익스트라에서는 음수의 간선을 사용할 수 없다. 왜냐하면 일단 다익스트라는 순환구조가 불가능하기 때문이다. 그렇기 때문에 음수의 간선이 들어가면 계속해서 순환하는 경우..
-
백준 1068(트리)전공/알고리즘 2020. 7. 1. 15:18
https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 어떤 트리에서 어떤 index이하의 subtree를 모두 제거 했을때 리프노드의 갯수를 구하자 리프노드는 트리에서 자식이 없는 노드를 리프노드라고 한다. 그렇다면 트리를 구성해서, root부터 자식 노드를 방문, 만약에 자식 노드가 없는 경우 +1 하면 된다. 그리고 어떤 index의 subtree를 제거해야 하므로 index를 방문하면 그냥 스킵. 여기서 두가지 상황이 나온다. 만약에 제거..
-
백준 2263(트리의 순회)전공/알고리즘 2020. 7. 1. 12:57
https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net https://xkdlaldfjtnl.tistory.com/44 백준 4256(트리) https://www.acmicpc.net/problem/4256 4256번: 트리 문제 이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며 xkdlaldfjtnl.tistory.com 이 문제와 완벽하게 동일한 문제. 단지 차이점은 문제의 예시가 좀..
-
백준 4256(트리)전공/알고리즘 2020. 6. 30. 17:09
https://www.acmicpc.net/problem/4256 4256번: 트리 문제 이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. 노드 n�� www.acmicpc.net 이진 트리의 전위, 중위, 후위 순회에 대한 문제다. 일단 전위 순회의 결과와 중위 순회의 결과로 후위 순회를 구할 수 있도록 문제가 주어진다고 했다. 그러면 어떻게 전위 순회와 중위 순회로 후위 순회를 구할 수 있을까. 전위는 방문이 먼저인 VLR구조이고, 중위는 LVR구조이다. 방문을 먼저한다는게 후위 순회를 위해서 이진트리구조를 알 수 있는 핵심이라고 생각한다. 무조건 root부터 순회를 시작..
-
백준 1967(트리의 지름)전공/알고리즘 2020. 6. 30. 14:52
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 �� www.acmicpc.net 트리의 지름 트리에서 가장 먼 거리의 두 지점을 이은 거리가 그 트리의 지름이다. https://blog.myungwoo.kr/112 트리의 지름 구하기 트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다: 1. 트리에서 임의의 정점 $x$를 blog.myungwoo.kr..
-
백준 17396(백도어)전공/알고리즘 2020. 6. 30. 12:51
https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는� www.acmicpc.net N개의 분기점이 있다. 이 분기점만 지날 수 있으며, 만약에 와드가 있으면 지나가지 못한다. 0 -> N-1까지가는 최단 거리를 구하여라. 최단거리 문제는 다익스트라 따라서 다익스트라로 구현한다. 여기서 N값이 10만이므로 인접행렬로는 구현이 불가능하다는 것을 알 수 있다 따라서 인접리스트를 이용한 다익스트라로 구현한다. 와드에 대한 처리는 단순하게 와드가 있다면 그 ..