넘치게 채우기

https://www.acmicpc.net/problem/2042BOJ - 구간 합 구하기문제 유형: 세그먼트 트리문제 난이도: Gold I시간 제한: 2초메모리 제한: 256MB 문제어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다. 입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 ..

https://leetcode.com/problems/design-a-number-container-system/description/leetcode - Design a Number Container System문제 유형: 우선순위 큐, 힙, 해시문제 난이도: Medium 문제Design a number container system that can do the following:Insert or Replace a number at the given index in the system.Return the smallest index for the given number in the system.Implement the NumberContainers class:NumberContainers() Initial..

https://www.acmicpc.net/problem/2263BOJ - 트리의 순회문제 유형: 트리, dfs, 분할 정복문제 난이도: Gold I시간 제한: 5초메모리 제한: 128MB 문제n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 입력첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 출력첫째 줄에 프리오더를 출력한다. 풀이중위순회의 정보는 노드들간의 좌우관계를 알려준다.후위순회에서의 마지막원소는 항상 루트노드의 값이다.즉, 루트노드를 중위순회..

https://leetcode.com/problems/find-the-number-of-distinct-colors-among-the-balls/description/leetcode - Find the Number of Distinct Colors Among the Balls문제 유형: 해시문제 난이도: Medium 문제You are given an integer limit and a 2D array queries of size n x 2.There are limit + 1 balls with distinct labels in the range [0, limit]. Initially, all balls are uncolored. For every query in queries that is of the ..

https://www.acmicpc.net/problem/16566BOJ - 카드 게임문제 유형: 분리 집합, 이진 탐색, 유니온-파인드문제 난이도: Platinum V시간 제한: 1.2초메모리 제한: 512MB 문제철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다.N개의 빨간색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 M개의 카드를 고른다.N개의 파란색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 M개를 고른다.철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.철수와 민수는 고른 카드 중에 1장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번..

https://leetcode.com/problems/tuple-with-same-product/description/leetcode - Tuple with Same Product문제 유형: 수학, 해시문제 난이도: Medium 문제Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where a, b, c, and d are elements of nums, and a != b != c != d. 독립적인 정수 배열 nums가 주어집니다.a*b = c*d인 (a, b, c, d)튜플조합의 개수를 모두 구하시오. 풀이하나의 조합을 구하면, 8개의 튜플을..

https://www.acmicpc.net/problem/17143BOJ - 낚시왕문제 유형: 구현, 시뮬레이션문제 난이도: Gold I시간 제한: 1초메모리 제한: 512MB 문제낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.낚시왕이 오른쪽으로 한 칸 이동한다.낚시왕이 있는 열에 있..

https://leetcode.com/problems/check-if-one-string-swap-can-make-strings-equal/description/leetcode - Check if One String Swap Can Make Strings Equal문제 유형: 투 포인터문제 난이도: Easy 문제You are given two strings s1 and s2 of equal length. A string swap is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices.Return true if it is possible ..

https://www.acmicpc.net/problem/2162BOJ - 선분 그룹문제 유형: CCW, 선형대수, 기하학, 유니온-파인드, 분리 집합문제 난이도: Platinum V시간 제한: 2초메모리 제한: 128MB 문제N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다.N개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한 선분의 개수는 몇 개일까? 이 두 가지를 구하는 프로그램을 작성해..

https://leetcode.com/problems/maximum-ascending-subarray-sum/description/leetcode - Maximum Ascending Subarray Sum문제 유형: 슬라이딩 윈도우문제 난이도: Easy 문제Given an array of positive integers nums, return the maximum possible sum of an ascending subarray in nums.A subarray is defined as a contiguous sequence of numbers in an array.A subarray [numsl, numsl+1, ..., numsr-1, numsr] is ascending if for all i wh..