HTD

#include #include #include #pragma warning(disable:4996) typedef struct Node { int value; struct Node* next; } Node; typedef struct Vertex { Node* header; } Vertex; typedef struct Edge { int v1; int v2; int w; } Edge; typedef struct Metadata { Vertex** vertices; int verticesCount; Edge** edges; int edgesCount; } Metadata; typedef struct Pair { int a, b; } Pair; typedef struct PriortyQueue { Pair..

https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net - 배경 Segment Tree의 Lazy Propagation을 안다는 전제로 글을 작성하였으니, 해당 개념에 대해서는 다음 링크를 참조하자. https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-10999%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-..

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net - 풀이 구현해야할 것은 크게 2가지다. 한 줄에서 가장 위에 있는 상어를 잡는 catchShark()와, 상어들을 이동시키는 moveSharks() 함수이다. 전자는 매우 간단하게 구현이 가능하다. 하지만 문제는 후자이다. moveSharks() 함수는 모든 살아있는 상어들을 반복문으로 돌면서, 각각의 위치와 속도, 그리고 방향에 따라 nextPosition을 구해준다. 다음..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net - 관찰 처음에 든 생각은, 모든 벽들부터 시작하는 탐색을 해주는 것이었다. 하지만 이것은 시간복잡도가 너무 크다. 예제 입력 2를 살펴보자. 위와 같이 구분되는 각각의 공간들을 묶어서 값을 저장하고, 이렇게 한 이후에, 모든 벽들에 대해서 (인접한 공간들의 크기의 합) + 1을 해주면 된다. - 풀이 1. 탐색은 2개로 분류된다. 첫번째는 공간의 크기를 조사하는 탐색이며, ..

https://www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net - 관찰 단순히 rotate() 함수 하나 만들어서 cube[6][3][3]의 데이터를 적절히 변화시키기만 하면 된다. 하지만 구현이 그렇게 단순하지는 않다. 총 2개의 사항을 구현해야한다. 첫째로, 하나의 면을 돌렸을 때 영향을 받는 다른 4개의 면의 데이터 변경이며, 두번째로, 돌린 면의 3x3의 회전이다. 또한 clockwise/inverse라는 방향도 고려해야하는데, 사실 clockwise ..

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net - 관찰 여러 경우에 대한 그림을 그려보면 알겠지만, (0, 0)~(N-1, M-1)로 시작하는 순차적인 탐색을 해보면, 이전 탐색과 동선이 겹치는 경우가 있다. 이 경우에는 하나의 '그룹'으로 묶을 수 있으며, 모든 탐색을 마친 뒤 최종적으로 남는 그룹별로 SAFE ZONE을 설치하면 된다. - 풀이 0. count 변수에 '그룹'의 갯수를 저장하며, 이것을 ..

https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net - 관찰 예제 입력 1의 카드들을 정렬해보면 다음과 같다. 2 3 4 5 7 8 9 이제 K번 주어지는 철수가 내는 카드들을 살펴보자. 4를 내면 5가 나와야하고, 1을 내면 2가 나와야한다. -> 이진탐색 lower_bound를 입력값 + 1에 대해 해준다.(4를 냈다면 5를 찾는 탐색을 진행) 다음으로 카드가 1 2 3 4가 있는데, 0을 ..

https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net #include #define REP(i, a, b) for(int i=(a);i> N >> K; // Get (K!(N-K)!)^1000000005 long long t = getFactorial(K) * getFactorial(N - K) % MOD; long long res = getPower(t, MOD - 2); // res * N! cout

https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 10 = 2 * 5에서, 2와 5의 승수만을 고려하여 풀 수 있다는 아이디어를 내야한다. nCr = n! / (r! * (n-r)!)의 각각의 팩토리얼에서 2, 5의 승수를 가져와서 연산을 해주면 된다. 예를 들어, 5C3 = 5!/(3!*2!) = (1*2*3*4*5) / ((1*2*3) * (1*2))에서 5!, 3!, 2!에는 각각 2^1, 5^1 / 2^1 / 2^1가 포함되며 2^(-1), 5^0이므로 0의 개수가 0이다. 만약 어떤 조합에서 2^..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net #include #include #pragma warning(disable:4996) typedef struct Node { int var; int index; struct Node* next; }Node; typedef struct Stack { int size; Node* top; }Stack; Node* getNode(int var, int index) { Node* res = malloc(sizeof..