4Legs_Archives

문제 링크 : www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 문제 유형 구현, 시뮬레이션 이전 문제인 [백준] 17822 원판 돌리기 와 같이, 상어를 클래스 형태로 구현한다. 동일 칸에서는 작은 상어가 반드시 남게 되므로, 상어의 이동은 번호가 높은 순으로 진행한다. 이렇게 하면 따로 예외 처리를 하지 않고도 덮어쓰기 개념으로 겹치는 상어에 대한 처리를 할 수 있게 된다. 이 풀이에서는 상어의 냄새가 어떤 상어..

문제 링크 : www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 문제 유형 구현, 시뮬레이션 이런 시뮬레이션 형태의 구현 문제는, 어떠한 동작을 수행하는 매개체를 클래스 형태로 구현하면 비교적 깔끔하게 구현이 가능하다. 이 문제에서는 각 원판을 disk라는 클래스로 정의하고, 이 클래스 내부에 회전 및 인접 값 제거 메소드를 구현했다. 각 원판의 숫자들은 deque 형태로 저장해 회전 구현을 쉽게 할 수 있도록 했고, 인접 값 참조를 쉽게 할 ..

문제 링크 : 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 만약 한 사원에 대해, 그 사원의 직속 부하(즉, 인접 자식 노드)로부터 전파가 완료되는 시간을 모두 알고 있다고 가정해보자. 이 때, 전파 시간이 오래 걸리는 사원에게 먼저 전파하는 것이 총 전파 시간을 줄이는 데 반드시 좋을 것이다. 직속 부하에게는 한 번에 한 명에게만 전파가 가능하기 때문이다. 따라서 각 직속 부하들로부터 완료되는 전파 시간들을 큰 순으..