분류 전체보기
-
백준 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만이므로 인접행렬로는 구현이 불가능하다는 것을 알 수 있다 따라서 인접리스트를 이용한 다익스트라로 구현한다. 와드에 대한 처리는 단순하게 와드가 있다면 그 ..
-
백준 13549(숨바꼭질3)전공/알고리즘 2020. 6. 29. 15:11
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 어떻게 하면 원하는 값까지 도달할 수 있을까. dfs는 한곳을 엄청 깊게 판다. 그래서 원하는 값까지 도달하더라도 그 값이 최솟값이 아닐 가능성이 농후하다. 그래서 bfs bfs에 단순 queue로 구성을 하려니 순간이동할때는 시간 소모가 안된다고 한다. 그래서 만약 단순 queue로 구성을 한다고 하면 경로는 더 길지만 시간이 적게 걸리는 경우를 확인하지 ..
-
백준 1916(최소비용 구하기)전공/알고리즘 2020. 6. 29. 14:33
https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 제발 문제좀 제대로 읽자. 조건을 제대로 파악해야 찾을 수 있다. 그냥 다 익스트라로 풀린다. priority_queue를 이용한 다 익스트라의 일반적인 시간복잡도는 O(ElogV)이고 이 문제에서는 V = 1,000 E = 100,000 이므로 10^5로 간단하게 풀린다. 1. 하지만 이전 문제에서의 문제와 같이 한 지점에서 다른 지점까지의 경로는 하나 이상일 ..
-
백준 1753(최단경로)전공/알고리즘 2020. 6. 29. 14:06
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 엄청 단순한 다익스트라 문제. 문제에서 요구하는 바가 무조건 다익스트라이다. 근데 고비가 있었다. 이제까지 인접행렬로 문제를 풀었었기 때문에 이 문제 또한 인접행렬로 문제를 풀려고 했지만, vertex가 20,000 이므로 만약에 인접행렬로 푼다면 20000*20000 4억 메모리제한에 걸리게 된다. 따라서 인접리스트로 문제를 풀어야한다. 인접리스트를 사용하려면 vect..
-
백준 2665(미로만들기)전공/알고리즘 2020. 6. 28. 16:40
https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net N^2의 격자에 흰색과 검은색이 존재한다. 검은색은 벽으로 이루어져서 지나갈 수 없다. 하지만 벽을 부술 수 있다. 최소 몇번의 벽을 부셔야 시작점에서 종료지점까지 갈 수 있는가 어디 지점에서 어디 까지 가는 방법 => dfs, bfs 사실 먼저 dfs를 생각했다. dfs의 재귀함수로 몇 번의 벽을 부술지 기록하기가 더 쉽다고 생각했지만, 역시 문제점은 시간 만약에 dfs로 구현하게 된다면 벽이 보이는대..
-
백준 1719(택배)전공/알고리즘 2020. 6. 28. 15:51
https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net N개의 점이 있을 때, 각각의 점에서 나머지 점까지 최단 경로로 이동할 때, 가장 먼저 거쳐가야 하는 점을 찾는 문제이다. N개의 점에서 나머지 N개의 점까지의 최단 거리를 구하는 문제 => 플로이드 와샬 O(N^3) 200^3 = 8*10^6이므로 시간복잡도에서 문제가 되지 않는다. 그럼 이제 최단경로로 이동한다고 했을 때, 가장 먼저 들려야 하는 지점을 찾는게 문제인데 플로이드 와샬의 작..