넘치게 채우기

https://leetcode.com/problems/divide-nodes-into-the-maximum-number-of-groups/description/leetcode - Divide Nodes Into the Maximum Number of Groups문제 유형: bfs, 그래프, 연결 컴포넌트, 이분 그래프문제 난이도: Hard 문제You are given a positive integer n representing the number of nodes in an undirected graph. The nodes are labeled from 1 to n.You are also given a 2D integer array edges, where edges[i] = [ai, bi] indicate..

https://www.acmicpc.net/problem/1562BOJ - 계단 수문제 유형: 다이나믹 프로그래밍, 비트마스킹문제 난이도: Gold I시간 제한: 2초메모리 제한: 128MB 문제45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다. 입력첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 풀이0~9이므로, 등장여부 상태를 비트마스킹을 이용할 수 있다. (처음에 상태추적을..

https://www.acmicpc.net/problem/17387BOJ - 선분 교차 2문제 유형: 선형대수, 수학, 기하학문제 난이도: Gold II시간 제한: 0.25초메모리 제한: 512MB 문제2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다. 입력첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 출력L1과 L2가 교차하면 1, 아니면 0을 출력한다. 풀이처음에는 직선의 방정식을 이용해서..

https://leetcode.com/problems/maximum-employees-to-be-invited-to-a-meeting/description/leetcode -Maximum Employees to Be Invited to a Meeting문제 유형: 위상 정렬, bfs, 연결 컴포넌트, 그래프문제 난이도: Hard 문제A company is organizing a meeting and has a list of n employees, waiting to be invited. They have arranged for a large circular table, capable of seating any number of employees.The employees are numbered from 0..

https://codeforces.com/contest/2063/problem/CCodeforces Round 1000(Div.2) - C. Remove Exactly Two문제 유형: 그리디, 그래프, 정렬, 트리시간 제한: 2초메모리 제한: 256MB 문제You are given a tree∗">∗ of n">n vertices. You must perform the following operation exactly twice.Select a vertex v">v; Remove all edges incident to v">v, and also the vertex v">v. Please find the maximum number of connected components after perf..

https://leetcode.com/problems/find-eventual-safe-states/description/leetcode - Find Eventual Safe States문제 유형: dfs, 위상 정렬문제 난이도: Medium 문제There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in gra..

https://www.acmicpc.net/problem/1799BOJ - 비숍문제 유형: 백트래킹, 브루트 포스, MITM(Meet-In-The-Middle)문제 난이도: Platinum V시간 제한: 10초메모리 제한: 128MB 문제서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. 에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는..

https://leetcode.com/problems/grid-game/description/leetcode - Grid Game문제 유형: 부분합, 구간합, 그리디문제 난이도: Medium 문제You are given a 0-indexed 2D array grid of size 2 x n, where grid[r][c] represents the number of points at position (r, c) on the matrix. Two robots are playing a game on this matrix.Both robots initially start at (0, 0) and want to reach (1, n-1). Each robot may only move to the right ((..

https://leetcode.com/problems/trapping-rain-water-ii/description/leetcode - Trapping Rain Water II문제 유형: 우선순위 큐, bfs문제 난이도: Hard 문제Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining. m x n의 정수 행렬 heightMap이 주어진다. 이는 2D의 높이 지도를 셀단위로 나타내는데, 비가 오고 난 뒤 물이 고이는 물의 총 양을 구하여라. 풀이처음에는 https://rivero..

https://www.acmicpc.net/problem/9527BOJ - 1의 개수 세기문제 유형: 누적합, 수학, 비트마스킹문제 난이도: Gold II시간 제한: 1초메모리 제한: 128MB 문제두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자. ∑x=ABf(x)\[\sum_{x=A}^{B}{f(x)}\]  입력첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 10^16) 출력1의 개수를 세어 출력한다. 풀이어떤 수 2^i-1에 대한 점화식은 다음과 같다: pows[i]는 (1  i비트의 ..