서랍장

2021 APC (아주대학교 프로그래밍) 대회 문제중 하나였다. 예전에 엘리베이터 관련 문제를 카카오 2차 기출에서 본 듯해서 그걸로 푸는건가? 했지만 해당 문제는 단지 dfs 탐색을 통해 일일이 체킹만 해주면 되는 문제이다. 다만 한가지 집고 넘어가야할 점이 있다. dfs 로 일일이 순회를 해주다가 해당 층에 사람이 없는 경우가 생기게 된다. 이렇게 되면 사람이 있는 층들 중에 한 곳으로 가야하는데 어떤 기준으로 갈 곳을 정해줄까? 에 대한 문제이다. 위상정렬 알고리즘에서 힌트를 가져왔다. 각 층을 원하는 사람의 수를 배열 하나 두어서 체킹해준 다음에 원하는 사람이 작은 층을 갈 곳으로 정하면 된다. 이렇게 되면 중간에 건너띄는 층 없이 모든 층을 깔끔하게 순회할 수 있기 때문이다. 이 점때문에 골드 ..

해당 문제는 아주대 프로그래밍 경시대회 div 1 문제 였다. 대회 때 문제를 보자마자 누적합이라는 걸 캐치한 뒤 빠르게 푼 기억이 있다. 일단 문제를 푸는 로직은 다음과 같다. 입력받는 스터디 시간들을 +1 -1 prefix 로직을 통해 체킹을 해준다. 체킹을 모두 완료한 뒤에 각각 시간대의 사람 수를 계산하고, 그 계산한 값으로 누적합 배열을 초기화해준다. 위 과정을 통해 누적합 배열을 초기화해주었다면 그 다음에는 m 만큼의 슬라이딩 윈도우를 만들어 O(N)의 복잡도로 가장 많은 사람들이 있는 시간 구역을 찾으면 끝이다. #include #include using namespace std; typedef long long LL; LL arr[200000]; LL cnt[200000]; LL sum[2..

간단한 BFS + 이분탐색 문제였다. 일단 입력 값을 보았을 때, node 의 개수가 10000개에 다리의 개수가 10만개이다. 때문에 전체를 다 탐색하게 되면 시간 초과가 발생할 수 있다. 때문에 다음과 같은 로직으로 푸는게 안전하다. 최소, 최대 cost 값을 찾은 다음에 이분탐색으로 적절한 cost 값을 찾는다. 각 cost 값 마다 bfs 를 통해 start - finish 경로가 있는지 확인한다. #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; int check[100001]; int start, finished; vector v[10000..

시뮬레이션 + 백트래킹 문제이다. 1차적으로 궁수 3명을 N+1 번째 행에 3명을 조합의 경우의 수로 세워둔다. 그 다음 2차적으로 시간을 N까지 증가시키면서 적들을 아래 칸으로 한칸씩 움직이도록 한다. 3차적으로 한 칸씩 움직인 적들 중 각 궁수에게 가장 가까운, 거리가 같다면 제일 왼쪽에 있는 놈을 찾는 O(NlogN) 로직을 짜준다. 그 후 하나하나 죽이면서 죽는 놈들을 세어주면 된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #define MAX_NUM 1000000009 using namespace std; typedef long long LL; typ..

해당 높이에 몇개의 장애물이 있는지 누적합을 사용하는 문제이다. +-prefix 를 사용하여 어디서부터 어디까지 +인지 체크해주면 간단하게 누적합을 구할 수 있으며, O(N)의 복잡도로 문제를 풀 수 있다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; int sum[500001]; int main() { int n, m, a, b, c; scanf("%d %d", &n, &m); for (int i = 1; i

백트래킹 문제이다. 일단 2차원 위치를 하나의 num으로 두고 나머지와, 몫으로 좌표를 설정하도록 한다. 그 후 하나씩 돌아가면서 해당 수만 직사각형 종이에 포함할 것인가 해당 수의 아래를 직사각형 종이에 포함할 것인가 해당 수의 오른쪽을 직사각형 종이에 포함할 것인가 를 하나씩 처리해주면서 문제를 풀면 간단하다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include using namespace std; // 입력값이 100만 -> nlogn 으로 끝내야 한다. int arr[5][5]; int check[5][5]; int dx[] = { -1, 0 }; int dy[] ..

+-누적합 문제이다. 값의 변경을 일일이 배열에 체킹해주면 터지게 된다. 때문에 이를 +-누적합을 통해 구해줄 수 있다. ground : 첫 값이 들어가있는 배열 arr : "+ -" 체킹 배열 sum : 최종적으로 몇 만큼 변경해야하는지 들어있는 배열 #include using namespace std; typedef long long LL; int sum[100001]; int arr[100002]; int ground[100002]; int main() { int n, m, a, b, c; scanf("%d %d", &n, &m); for (int i = 1; i

20만의 입력값에 대응하기 위해 nlogn 또는 n의 복잡도로 문제를 풀어야 한다. 이를 위해 누적합을 통해 문제를 풀 수 있다. 다만 전체 합에 대한 누적합과 각 색상에 대한 누적합을 따로 구하여 해당 값을 처리해주면 된다. 이를 2가지 방법으로 구현하였다. 각 색상에 대한 누적합을 구해놓고, 각각의 답을 구할 시에 이분탐색을 돌린다. 모든 명령어를 정렬한 뒤 색에 대한 누적합과 전체에 대한 누적합을 동시에 진행해준다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; typedef long long LL; typedef pair pii; LL input; LL arr[2001]; LL all_..

누적합과 조합 계산식이 필요한 문제다. 일단 입력값을 보면 100만임을 봐서 최소 O(NlogN) 의 복잡도 내로 끝내야 함을 알 수 있다. 허나 이 문제의 경우 각 누적합을 통해 O(N) 복잡도로 끝낼 수 있다. 로직은 다음과 같다. 입력되는 배열을 순서대로 sum 배열에 넣되 m으로 나눈 나머지 값을 쭉 넣어준다. sum 배열을 순회하면서 원소를 pai 배열에 체킹해준다. pai 배열에 체킹된 순서로 순회하면서 조합식을 더하면 답이 된다. 이렇게 pai 배열을 둔 이유는 sum[i] - sum[j] = 0 이 되는 경우의 수를 찾아야 하는데 결국 sum[i] == sum[j] 인 경우를 찾는 것과 다름이 없다. 따라서 같은 값을 가지는 sum 배열의 원소들을 쭉 체킹해준 다음 nC2의 조합식에 따라 ..

구간합을 구하는 간단한 문제였다. 세그먼트 트리 나 누적합 으로 풀면 간단하게 풀린다. 누적합 로직은 다음과 같다. (a~b)의 합 = b까지의 합 - (a-1)까지의 합 코드는 두가지 버전으로 작성해보았다. // 세그먼트 트리 로직 #include using namespace std; typedef long long LL; LL tree[300000]; LL query(int node, int s, int e, int l, int r) { if (e < l || r < s) return 0; if (l