넘치게 채우기

https://www.acmicpc.net/problem/16975BOJ - 수열과 쿼리 21문제 유형: 세그먼트 트리(with lazy propagation)문제 난이도: Platinum IV시간 제한: 2초메모리 제한: 512MB 문제길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다.2 x: Ax 를 출력한다. 입력첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 1,000,000)셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.넷째 줄부터 M개의 줄에는 쿼리가 한 줄..

https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/description/?envType=daily-question&envId=2025-02-21leetcode - Find Elements in a Contaminated Binary Tree문제 유형: 트리, 해시문제 난이도: Medium 문제Given a binary tree with the following rules:root.val == 0For any treeNode:If treeNode.val has a value x and treeNode.left != null, then treeNode.left.val == 2 * x + 1If treeNode.val has a..

https://www.acmicpc.net/problem/10999BOJ - 구간 합 구하기 2문제 유형: 세그먼트 트리 (with lazy propagation)문제 난이도: Platinum IV시간 제한: 2초메모리 제한: 256MB 문제어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째부터 4번째 수에 6을 더하면 1, 2, 9, 10, 5가 되고, 여기서 2번째부터 5번째까지 합을 구하라고 한다면 26을 출력하면 되는 것이다. 그리고 그 상태에서 1번째부터 3번째 수에 2를 빼고 2번째부터 5번째까지 합을 구하라고 한다면 22가 될 것이다. 입력첫째 줄에 수의 개수 N(1 ≤ N ≤..

세그먼트 트리References:https://youtu.be/-dUiRtJ8ot0?si=SRjeBHChrzUaN-id  세그먼트 트리란, 1차원 배열에서의 구간 연산에 대해 빠르게 구하는 자료구조이다.구간 [l, r]에 대해서 기존의 naive하게 업데이트 및 연산하는 것은 O(N)의 시간이 걸리지만,세그먼트 트리를 이용하면 O(log N)의 시간이 걸린다. 세그먼트 트리는 트리이지만, 배열 기반의 이진트리로 간단하게 표현될 수 있다.이진트리의 특성상, 0-based의 기준, 인덱스 i 노드의 왼쪽 자식은 i*2+1, 오른쪽 자식은 i*2+2에 위치한다.1-based의 기준, i노드의 왼쪽 자식은 i*2, 오른쪽 자식은 i*2+1이다. 세그먼트 트리에서,루트 노드는 모든 구간에 대한 연산 결과를 저장한..

https://www.acmicpc.net/problem/2533BOJ - 사회망 서비스(SNS)문제 유형: 트리, 다이나믹 프로그래밍문제 난이도: Gold III시간 제한: 3초메모리 제한: 256MB 문제페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데,  이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다.예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다.   친구 관계..

https://leetcode.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/description/leetcode - The k-th Lexicographical String of All Happy Strings of Length n문제 유형: 백트래킹, 수학, 조합론, 해 구성하기문제 난이도: Medium 문제A happy string is a string that:consists only of letters of the set ['a', 'b', 'c'].s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).For e..

https://codeforces.com/contest/2064/problem/DCodeforces Round 1005(Div. 2) - D. Eating문제 유형: 그리디, 비트마스킹, 이진 탐색시간 제한: 5초메모리 제한: 512MB 문제There are n">n slimes on a line, the i">i-th of which has weight wi">wi. Slime i">i is able to eat another slime j">j if wi≥wj">wi≥wj; afterwards, slime j">j disappears and the weight of slime i">i becomes wi⊕wj">wi⊕wj.The King of Slimes wants to ru..

https://www.acmicpc.net/problem/1300BOJ - K번째 수문제 유형: 매개변수 탐색(parametric search), 이진 탐색, 행렬문제 난이도: Gold I시간 제한: 2초메모리 제한: 128MB 문제세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.배열 A와 B의 인덱스는 1부터 시작한다. 입력첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다. 출력B[k]를 출력한다. 풀이n이 정해져 있고 2D배열 A에..

https://leetcode.com/problems/construct-smallest-number-from-di-string/description/leetcode - Construct Smallest Number From DI String문제 유형: 백트래킹, 비트마스킹, 문자열 처리, 그리디문제 난이도: Medium 문제You are given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.A 0-indexed string num of length n + 1 is created using the following conditions:num..

https://codeforces.com/contest/2064/problem/CCodeforces Round 1005(Div. 2) - C. Remove the ends문제 유형: 그리디, 해 구성하기, 모노토닉, 구간합, 브루트 포스시간 제한: 3초메모리 제한: 256MB 문제You have an array a">a of length n">n consisting of non-zero integers. Initially, you have 0">0 coins, and you will do the following until a">a is empty:Let m">m be the current size of a">a. Select an integer i">i where 1≤i≤m">..