4Legs_Archives

문제 링크 : www.acmicpc.net/problem/7626 7626번: 직사각형 첫째 줄에 양의 정수 N이 주어진다. (1 ≤ N ≤ 200,000) 다음 N개 줄에는 공백으로 나누어진 네 값 "x1, x2, y1, y2"가 주어진다. 이 값은 직사각형 [x1,x2] × [y1,y2]를 나타낸다. 모든 좌표는 0보다 크거나 www.acmicpc.net [Swipping] BOJ 3392 화성 지도 문제 링크 : www.acmicpc.net/problem/3392 3392번: 화성 지도 첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 4legs-study.tistory.com 위 문제와 동일한..

문제 링크 : www.acmicpc.net/problem/3392 3392번: 화성 지도 첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30 www.acmicpc.net 스위핑(Sweeping) 알고리즘으로 해결할 수 있는 대표적인 유형의 문제이다. 스위핑 알고리즘을 간단히 말하자면, 일련의 자료들을 순서대로 한 번 훑으며 정답을 구하는 방법이라 할 수 있다. 개념이 가벼운 만큼 응용된 문제는 꽤 어려운 축에 속한다. 아무튼 이 문제를 스위핑 알고리즘으로 해결하기 위해 다음과 같은 예제를 풀어보자. ..

문제 링크 : www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net 굉장히 난해하고 어려운 문제다. 그나마 쉽게 접근하기 위해 원형으로 제시된 각 구역들을 선형으로 생각해보자. 그리고 다음과 같이 정의한다. - dp[k][2] : k열의 0행, 1행에 해당하는 구역 모두에 소대를 배치하지 않은 상태를 만드는 데 필요한 최소 소대 수 - dp[k][0] : k열의 0행까지만 소대를 배치한 상태를 만드는 데 필요한 최소 소..

문제 링크 : www.acmicpc.net/problem/16950 16950번: 레드 블루 스패닝 트리 2 첫 줄에는 세 정수 n, m, k가 주어진다. n은 그래프의 정점의 개수 (2 ≤ n ≤ 1,000)이고, m은 간선의 개수, k는 문제에 설명되어 있는 파란색 간선의 개수 (0 ≤ k < n) 이다. 다음 m개 줄에는 간선의 정 www.acmicpc.net [먼저 풀면 좋은 문제] [MST] BOJ 4792 레드 블루 스패닝 트리 문제 링크 : www.acmicpc.net/problem/4792 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 4legs-study.tistory.com..

문제 링크 : www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net [필요한 개념 : LCA (이분 탐색)] 최소 공통 조상 (LCA, Lowest Common Ancestor) 최소 공통 조상 (최소 공통 조상 (LCA, Lowest Common Ancestor) 최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다. 위와 같은 예시 트리 구조에서, 13, 15번 4legs-study..

문제 링크 : www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 문제에서 제시된 그래프가 트리임에 주목하자. 트리에서는 두 정점을 잇는 경로가 유일하기 때문에, LCA를 통해 트리에서 두 정점의 거리를 구할 수 있다. 최소 공통 조상 (LCA, Lowest Common Ancestor) 최소 공통 조상 (최소 공통 조상 (LCA, Lowest Common Ancestor) 최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을..

최소 공통 조상 (LCA, Lowest Common Ancestor) 최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다. 위와 같은 예시 트리 구조에서, 13, 15번 정점의 최소 공통 조상은 5번 정점이 된다. 마찬가지로, 13, 11번 정점의 최소 공통 조상은 1번 정점(Root)이 된다. LCA를 선형 탐색으로 구하기 : O(Depth) 트리에서 이러한 최소 공통 조상을 찾으려면 어떤 방식을 사용해야 할까? 가장 단순한 방법으로는, 두 포인터를 두고 가리키는 정점이 같아질 때까지 부모 노드로 거슬러 올라가면 될 것이다. 즉 Parent[x]를 정점 x의 부모 노드라 할 때, x = Parent[x] 연산을 반복하면 될 것이다. 하지만 구하고자 하는 두 정점의 ..

문제 링크 : www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 게임을 무한히 할 수 있는 경우는 어떤 경우일까? 일련의 순서로 각 칸을 방문할 때, 이미 한 번 방문했던 칸을 다시 방문할 수 있다면 게임을 무한히 진행할 수 있다. 즉, 게임판 내에서 사이클이 발생하는 경우이다. 따라서, 제시된 2차원 배열의 각 칸을 정점으로 하는 그래프를 구성한 후 1번 정점으로부터 시작해 백트래킹을 통해 최대로 갈 수 있는 거리를 구하면 된다. (이 과정에서 사이클을 발견..

문제 링크 : www.acmicpc.net/problem/2001 2001번: 보석 줍기 첫째 줄에 n, m, K가 주어진다. 다음 K개의 줄에는 보석이 있는 섬의 번호가 주어진다. 다음 m개의 줄에는 각 다리에 대한 정보를 나타내는 세 자연수 a, b, c(1 ≤ c ≤ 100)가 주어진다. 이는 a번 섬과 www.acmicpc.net 보석의 개수가 최대 14개이므로, 어떤 보석을 주운 상태인지 비트마스크를 통해 나타낼 수 있음을 캐치하자. 보석이 있는 섬에 도착했을 때, 보석을 주운 후 다음 섬으로 이동할 수도 있고 줍지 않고 이동할 수 있다. 위와 같은 예제 그래프에서, 1번 노드에서 출발해 최대로 보석을 주웠을 때의 개수는 4이다. 경로는 다음과 같다. ① 1번 섬에서 보석을 줍지 않고 5번 섬으..

문제 링크 : www.acmicpc.net/problem/4792 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내 www.acmicpc.net 다음과 같은 그래프에서, 파란색 간선을 최소로 사용하는 스패닝 트리를 찾아보자. 파란색 간선을 최소로 사용했을 때의 스패닝 트리이다. 이는 곧, 예시 그래프에서 스패닝 트리를 구성하기 위해서는 최소 2개의 파란색 간선이 필요하다는 것을 의미한다. 즉 5-7, 6-8의 파란색 간선을 사용하지 않고서는 예시 그래프의 스패닝 트리를 구성할 수 없다. 그렇다면 마찬가지로 이번에는 파란색 간선을 최..