✏️ 알고리즘/PS 기록

[백준 12844번] XOR

12844번: XOR 크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다. www.acmicpc.net 목차 사전 지식 문제 풀이 사전 지식 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크) 느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)를 알고 있어야 한다. (링크) 문제 풀이 전형적인 느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)에 관한 문제이다. 느리게 갱신되는 세그먼트 트리를 ..

[AtCoder] ABC296 A~D 업솔빙

안녕하세요 Gliver 입니다. 이번 글은 앳코더 ABC296에 대해 업솔빙하는 글입니다. A번 - 단순 구현 문제이다. B번 - 단순 구현 문제이다. C번 - 약간의 사고력을 요구하는 문제이다. - 정렬을 하여 답이 되는 경우를 효율적으로 탐색하면 된다. D번 - 구현은 어렵지 않으나, 수학적인 사고력을 요구하는 문제이다. A. Alternately 연속하는 문자열이 있는지 물어보는 문제로, 탐색을 하며 arr[i-1]과 arr[i]를 비교함으로써 해결할 수 있다. A.cpp 한 번의 탐색으로 해결 가능하므로 시간 복잡도는 $O(N)$이다. ($1 \leq N \leq 100$) B. Chessboard column은 인덱스 순으로 a, b, c, d, e, f, g, h에 대응하며 row는 인덱스 순..

[백준 10999번] 구간 합 구하기2

10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 목차 사전 지식 문제 접근 문제 풀이 사전 지식 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크) 느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)를 알고 있으면 좋다 (링크) 문제 접근 백준 2042번 문제(링크)와 이번 문제의 차이점을 정확히 인지하는 것이 중요하다. 2042번 문제는 한 번에 한 개의 원소만 갱신..

[백준 10167번] 금광

10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이 www.acmicpc.net 목차 사전 지식 문제 접근 문제 풀이 사전 지식 2차원 좌표 압축에 대한 개념을 알고 있어야 한다. (링크) 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크) 가장 큰 연속합을 구하는 세그트리 문제를 이해하고 있어야 한다. (링크) 문제 접근 이 문제에 대한 순차적인 접근은 여기를 참고하기 바란다. 문제 풀이 이 문제의 핵심은 답이 되는 경우를 얼마나 효율적으로 탐색하는가이다. (좌표 압축을 ..

[백준 15561번] 구간 합 최대? 2

15561번: 구간 합 최대? 2 첫 번째 줄에 정수 N과 Q, U, V가 입력된다. (1 ≤ N, Q ≤ 105, - 5 ≤ U, V ≤ 5) 두 번째 줄에 정수 K1, K2, ..., KN이 주어진다. (-102 ≤ Ki ≤ 102) 세 번째 줄부터 쿼리가 www.acmicpc.net 목차 사전 지식 문제 풀이 사전 지식 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크) 가장 큰 연속합을 구하는 세그트리 문제를 이해하고 있어야 한다. (링크) 문제 풀이 $\small{U \times (K_i + K_{i+1} + \cdots + K_j) + V \times (j-i)}$ 의미 이 식은 $\small{(UK_i + UK_{i+1} + \cdots + UK_j) + ..

[백준 25639번] 수열과 최대 상승 쿼리

25639번: 수열과 최대 상승 쿼리 길이가 $N$인 수열 $a_1, a_2, ..., a_N$이 주어졌을 때, 다음과 같은 쿼리를 수행하는 프로그램을 작성해보자. 1 k x: $a_k$를 $x$로 바꾼다. 2 l r: 구간 $[l, r]$의 최대 상승 값을 출력한다. 구간 $[l, r]$의 최 www.acmicpc.net 목차 사전 지식 문제 접근 문제 풀이 사전 지식 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크) 특히, 세그먼트 트리가 쿼리를 처리하는 과정을 이해하고 있어야 한다. 문제 접근 문제에서 길이가 $N$인 배열($\small{a_1, a_2, \cdots, a_N}$)과 $Q$개의 쿼리(query)가 주어진다. 이 배열에서 아래의 두 개의 query..

[백준 2336번] 굉장한 학생

2336번: 굉장한 학생 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 세 개의 줄에는 각 시험에서 1등인 학생부터 N등인 학생이 순서대로 주어진다. 학생의 번호는 1부터 N까지 매겨져 있다. www.acmicpc.net 목차 사전 지식 문제 접근 사전 지식 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크) 문제 접근 먼저, 대단한 학생과 굉장한 학생의 정의를 정확히 이해해야 한다. 학생 A의 등수가 $(a_1, a_2, a_3)$이고 B의 등수가 $(b_1, b_2, b_3)$일 때, $\small{a_1 < b_1} \large{,}$ $\small{a_2 < b_2} \large{,}$ $\small{a_3 < b_3}$를 만족하면 A는 B보다 ..

[백준 12015번] 가장 긴 증가하는 부분 수열2 - 세그먼트 트리

12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 목차 사전 지식 DP 풀이 세그먼트 트리 풀이 가장 긴 증가하는 부분 수열 문제는 LIS(Longest Increasing Subsequences)로 잘 알려진 문제이다. 이번 글에서는 LIS 문제를 세그먼트 트리를 이용하여 풀어보겠다. 사전 지식 LIS의 DP(Dynamic Programming) 풀이를 이해해야 한다. (링크) 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크) DP 풀이 - $\scriptsize{O(N^2..