4Legs_Archives

문제 링크 : programmers.co.kr/learn/courses/30/lessons/72414 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 문제 유형 Lazy Propagation ※ 이 풀이에서는 공식 해답과 다르게 Lazy Propagation을 사용하였다. 공식 해답의 풀이는 추후 추가 예정 세그먼트 트리(Segment Tree) : Lazy Propagation [선행 개념 : 세그먼트 트리] 세그먼트 트리(Segment..

문제 링크 : www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net [문제 유형] Tree DP, Greedy 만약 한 사원에 대해, 그 사원의 직속 부하(즉, 인접 자식 노드)로부터 전파가 완료되는 시간을 모두 알고 있다고 가정해보자. 이 때, 전파 시간이 오래 걸리는 사원에게 먼저 전파하는 것이 총 전파 시간을 줄이는 데 반드시 좋을 것이다. 직속 부하에게는 한 번에 한 명에게만 전파가 가능하기 때문이다. 따라서 각 직속 부하들로부터 완료되는 전파 시간들을 큰 순으..

문제 링크 : programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 플로이드-와샬 알고리즘 또는 다익스트라 알고리즘으로 해결할 수 있는 문제이다. 출발..

[선행 개념 : 세그먼트 트리] 세그먼트 트리(Segment Tree) [서론] 크기가 1000인 배열이 있다. 이 배열의 각 원소는 1부터 10까지의 수이다. 이때 i번째 원소부터 j번째 원소까지의 합을 구하고 싶다. 어떤 방법이 좋을까? 가장 먼저 떠오르는 것은 누적합을 4legs-study.tistory.com 이전에 살펴본 세그먼트 트리에서는 트리 값의 갱신을 하나의 인덱스에 대해서만 진행했다. 예를 들어, 인덱스 5에 해당하는 노드의 값을 변경하기 위해 (1-10) -> (1-5) -> (4-5) -> (5) 구간을 거쳐오는 식이다. 하지만 우리는 한 번에 여러 개의 리프 노드에 대한 갱신이 필요할 수도 있다. 그림과 같이 4-10에 대한 구간을 한 번에 갱신하고 싶거나 할 때 말이다. 하지만 ..

문제 링크 : 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) 최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을..