재원블로그 재원블로그

이 문제는 세그먼트 트리를 이용해서 풀었다. N  이 문제에서 핵심은 A 배열을 앞에서부터 루프를 돌면서, 해당 A배열의 원소와 이어지는 B 배열의 인덱스보다 오른쪽에 연결된 것은 모두 교차한다는 사실을 찾아내는 것이다.이를 찾은 이후는 간단하게 풀 수 있다. segment의 리프 노드의 경우 해당 index가 연결되었는지(B 배열 기준으로) 여부를 저장하게 되고, 구간에 대해서는 해당 구간에 연결된 노드의 수를 리턴하게 된다. 세그먼트 트리 문제는 규칙성을 찾아 세그먼트 트리로 풀어내는 능력이 중요한 것 같다.#include #include #include #include #include #include using namespace std;#define MAX 500000typedef long long..

이 문제는 세그먼트 트리를 이용하여 풀었다. 이 문제의 핵심은 segment의 리프 노드를 1 ~ 1,000,000의 맛 사탕의 개수를 나타내는 것으로 생각할 수 있는지이다. 이걸 아직 생각 못했다.또한 두 번째는 query를 호출하고, cntInSection이 segment[node] 가 아닌 segment[node * 2]를 저장해야한다는 것이다.segment[node]로 해놓을 경우 실제로 rank가 제대로 계산되기 전에 start == end에 도착해버리고, 한 단계 낮은 값이 나올 가능성이 있다는 문제가 있다. 따라서 먼저 왼쪽 노드를 확인함으로써 이러한 문제를 해결할 수 있다. 한 가지 유의할 점은 A == 1일 때 query()를 호출한 값으로 update를 실행해야한다는 점이다. 나는 qu..

이 문제는 다이나믹 프로그래밍 문제이다. 이 문제에서 어려웠던 점은 합의 결과를 누적해서 리턴해줘야 한다는 점이다. 누적해서 리턴하지 않으면 당연히 모든 입력을 더한 값만이 나오게 된다.누적해서 리턴하는 것을 구현하기 위해 pair dp 배열을 사용했다. first는 실제 합한 자체의 결과이고, second는 누적 합을 저장하는 곳이다. dp 테크닉 자체는 행렬 곱셈 순서에 따른 연산 수를 구하는 테크닉과 동일하다. 어떤 구간에 대해 점화식을 세워서 문제를 풀었다.- dp[i][j] : 구간 [i, j]에서의 파일들을 하나로 합칠 때 필요한 최소 비용- dp[i][j] : for(k : i ~ j - 1) min(dp[i][j], dp[i][k] + dp[k + 1][j])이런식으로 점화식을 세워봤다. ..

이 문제는 투 포인터를 이용해서 풀었다. 예전에 이분 탐색으로 풀다가 계속 틀려서 때려쳤던 기억이 있다.이번에는 투 포인터가 먼저 보여서 투 포인터로 풀었는데, 한번에 풀 수 있었다.N 양 끝단에서 시작하는 투 포인터를 생각했다. 각 양쪽에서 서로를 향해 이동하는데, 각자의 다음 위치로 미리 이동한 후 더 절댓값이 작아지는 쪽으로 이동시키는 로직으로 알고리즘을 구성했다.#include #include #include using namespace std;vector input;int N;int absolute(int n) { return n >= 0 ? n : -n;}int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for (int i = ..

이 문제는 세그먼트 트리 연습 문제이다. 이 문제에서 조심할 점은 update 시 만약 수정할 index가 start ~ end 범위에 맞지 않을 때, segment[node]를 리턴하는 것이다.나는 여기서 INF를 리턴하도록 했었는데, 이런 식으로 하면 오답이 나온다. 또한 단순히 void update로 선언하여 합일 때의 코드처럼 짜면 정답이 나오지 않게 된다. 단순히 index가 start ~ end 범위 안에 있을 때segment[node] = min(segment[node], to) 이런 식으로 구현하게 되면 당연히 수정되지 않는다.이유는 기존 값이 바뀌는 값보다 작은 경우 갱신되지 않기 때문이다. 따라서 이 문제를 방지하기 위해서는 update가 init 함수와 비슷한형태를 취하도록 변경해야 ..

이 문제는 분할 정복을 이용해서 풀었다. 원래 세그먼트 트리로 푼다고 알고 있어서 세그먼트 트리를 만들고 있었는데, init 함수를 만들다 이미 값 계산이 끝난다는 사실을 알게 되었다.이 문제에서 가장 핵심은 절반으로 쪼갠 mid에 걸쳐 넓이의 최댓값을 구하는 것이다.이 부분을 해결하기 못했고, mid에서부터 좌우를 비교하여 더 높이가 높은 쪽을 선택하는 신박한 방법을 알게 되었다.이를 통해 start ~ end까지 한번씩만 탐색하여 가운데에 걸친 넓이를 구할 수 있었다. 이 방식으로 해결할 경우 O(N log N) 시간이 걸릴 것으로 예측된다. 정확히 절반씩을 쪼개며 들어가므로 log N 만큼의 높이가 생기고, 각 높이에서 N개의 노드를 순회할 것이기 때문이다.#include #include #incl..

이 문제는 우선순위 큐를 이용해서 풀었다. 시간 제한이 0.1초이므로 C++ 기준 1,000만 번의 연산만을 사용해야한다.또한 입력 정수 N의 최댓값이 100,000이므로 O(N log N) 알고리즘을 구현해야한다. 이 문제의 핵심은 우선순위 큐를 두개를 두는 것이다. 양쪽에 우선순위 큐가 있다고 생각하고, 왼쪽에는 최대 힙, 오른쪽에는 최소 힙을놓고 중간값을 찾는 것이다. 두 큐가 모두 비어있지 않을 때가 중요한데, 일단 범위에 맞게 현재 숫자를 집어넣고, 큐의 크기 비교를 통해 문제를 해결했다.숫자 개수의 합이 홀수일 때는 왼쪽 큐가 사이즈가 1 더 크게 만들고, 왼쪽 큐의 top을 출력하는 방식으로 구현했고,짝수일 때는 왼쪽과 오른쪽의 사이즈가 같게 만들어 왼쪽 큐의 top을 출력하는 방식으로 구현..

이 문제는 시뮬레이션 문제이다. 이 문제에서 핵심은 연쇄적으로 발생하는 기사들의 움직임을 구현하는 것이다. 나는 이걸 구현하기 위해 재귀를 사용했다.어떤 기사가 어떤 방향으로 움직여야할 때, 방패까지 포함한 자신의 경계를 구하고, 그 경계에서 다음 위치를 확인한 뒤 만약 다른 기사가 있어면 그 기사에 대해 재귀적으로 호출하는 방식으로 구현했다. 실제로 움직임을 구현할 때 주의해야할 점이 있는데, 우선 이미 움직인 기사를 또 움직이면 안된다. 내 코드의 경우 move 함수 안에서 candidate를 뽑아 진행하는데, 중복이 가능하여 처음에 오답이 나왔었다.또한 움직인 기사들 말고도 안 움직인 기사들도 다음 벡터에 남아야 한다. 너무 당연한 로직인데 항상 실수하는 부분인 것 같다.#include #inclu..