4Legs_Archives

문제 링크 : www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 문제 유형 자료 구조, 트라이 트라이 자료구조로 해결이 가능한 문제이다. 트라이의 find 함수에서, 다음과 같은 경우에 반환값을 1 증가시켜 정답을 구하면 된다. 다른 문자열의 끝을 지나는 경우 (코드의 finish) 자식의 수가 2 이상인 트라이 객체를 지날 경우 root 트라이 객체일 경우 (최초 1번의 입력) [코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1..

문제 링크 : www.acmicpc.net/problem/8452 8452번: 그래프와 쿼리 첫 번째 줄에 그래프의 정점, 간선의 수와 질의의 수를 나타내는 n, m, q 가 주어진다. (1 ≤ n ≤ 1, 000, 1 ≤ m ≤ 100, 000, 1 ≤ q ≤ 200, 000) 정점들은 순서대로 1부터 n까지 번호가 매겨져 있고, 간선들 www.acmicpc.net 문제 유형 BFS, Dijkstra, 오프라인 쿼리 오프라인 쿼리(Offline Query)란, 주어지는 쿼리들을 받는 즉시 처리하지 않고 모두 저장해둔 뒤 임의의 순서로 쿼리를 해결하는 기법을 말한다. 이 문제에서는 모든 쿼리를 다 받은 뒤, 쿼리를 역순으로 처리함으로써 문제를 간단화하여 해결할 수 있다. 즉, 원래의 U k 쿼리는 그래프..

문제 링크 : www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 문제 유형 Deque, 슬라이딩 윈도우 덱(Deque)을 사용해 구간 별 최솟값을 찾는 문제이다. 덱은 front와 back의 두 포인터를 가진 자료구조로, 삽입이 양방향으로 가능한 벡터라고 생각하면 편하다. 덱의 이러한 특징으로, 우리는 덱의 원소들을 특정 우선순위에 맞게 유지시킬 수 있다. 즉, 다음과 같은 과정을 통해 덱을 항상 오름차순으로 유지시킨다. 현재 ..

문제 링크 : www.acmicpc.net/problem/1945 1945번: 직사각형 첫째 줄에 직사각형의 개수 N(1≤N≤10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 직사각형의 왼쪽 아래 꼭짓점의 좌표 xbl, ybl과 오른쪽 위 꼭짓점의 좌표 xtr, ytr이 순서대로 빈칸 하나를 사이에 www.acmicpc.net 문제 유형 Sweeping 다음과 같은 예제를 보자. 이 예제에서 각 직사각형을 관통하기 시작하는 직선과 관통이 끝나는 직선을 알기 위해서는, 다음 그림처럼 각 직사각형마다 두 개의 점만 알면 된다. 빨간색 점은 직사각형을 관통하기 시작하는 직선과의 교점이며, 파란색 점은 직사각형의 관통이 끝나는 직선과의 교점이다. 따라서 우리는 다음과 같은 순서로 이 점들을 훑으며 정답을 구..

문제 링크 : www.acmicpc.net/problem/1849 1849번: 순열 1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라 www.acmicpc.net 문제 유형 Segment Tree, 누적 합 문제에서 제시된 예제를 풀어보자. 이러한 과정을 통해 모든 수의 빈칸을 채우면 원하는 수열을 구할 수 있다. 하지만 이를 선형 탐색의 형태로 구현한다면 시간복잡도는 O(N^2)가 되므로, 주어진 시간 제한을 만족할 수 없다. 따라서, 각 수가 들어갈 인덱스를 찾는 데 적어도 O(logN) 의 시간복잡도를 가지도록 구현해야 한다. 전체 시간복잡도..

문제 링크 : www.acmicpc.net/problem/1289 1289번: 트리의 가중치 첫째 줄에 트리의 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N-1개의 줄에 대해 각 줄에는 세 개의 정수 A, B, W(1 ≤ A, B ≤ N, 0 ≤ W ≤ 1,000)가 입력되는데 이는 A점과 B점이 연결되어 있고 이 www.acmicpc.net 문제 유형 Tree DP, Math 어떤 한 서브트리에서 나올 수 있는 모든 경로를 구해 보자. 우선 root를 경유하지 않는 경로, 즉 root노드가 경로의 한쪽 끝인 경우이다. 이는 일반적인 재귀를 통해 모두 구할 수 있다. 문제는 root를 경유하는 경로이다. 이를 구하기 위해서는 root로부터 이어진 각 자식들의 서브트리 가중치를 서로 ..

문제 링크 : www.acmicpc.net/problem/16225 16225번: 제271회 웰노운컵 첫 줄에 짝수 N(2 ≤ N ≤ 200,000)이 주어진다. 다음 줄에 A[1], ..., A[N], 그 다음 줄에 B[1], ..., B[N]이 (1 ≤ A[i], B[i] ≤ 109) 주어진다. 모든 A[i]는 서로 다르고, 모든 B[i]도 서로 다르다. www.acmicpc.net 문제 유형 Greedy 문제 두 개를 선택했을 때, 항상 상대는 B값이 더 큰 문제를 가져간다 했으므로, 주어진 문제들을 B값의 오름차순으로 정렬해 보자. 정렬 후 알 수 있는 사실은 다음과 같다. 즉, 2k + 1 번까지의 문제 중에서 k + 1 개의 문제를 가져갈 수 있고, 이 때 문제를 어떤 조합으로 고르던 항상 배..

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

문제 링크 : 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) 알고리즘으로 해결할 수 있는 대표적인 유형의 문제이다. 스위핑 알고리즘을 간단히 말하자면, 일련의 자료들을 순서대로 한 번 훑으며 정답을 구하는 방법이라 할 수 있다. 개념이 가벼운 만큼 응용된 문제는 꽤 어려운 축에 속한다. 아무튼 이 문제를 스위핑 알고리즘으로 해결하기 위해 다음과 같은 예제를 풀어보자. ..