넘치게 채우기

https://www.acmicpc.net/problem/18353BOJ - 병사 배치하기문제 유형: LIS(Longest Increasing Subsequence), 다이나믹 프로그래밍문제 난이도: Silver II시간 제한: 1초메모리 제한: 256MB 문제N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같..

https://leetcode.com/problems/target-sum/leetcode - Target Sum문제 유형: 다이나믹 프로그래밍문제 난이도: Medium 문제You are given an integer array nums and an integer target.You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate ..

https://www.acmicpc.net/problem/6118BOJ - 숨바꼭질문제 유형: bfs, 그래프문제 난이도: Silver I시간 제한: 1초메모리 제한: 256MB 문제재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있다. 모든 헛간은 M(1재서기는 발냄새가 지독하기 때문에 최대한 냄새가 안나게 숨을 장소를 찾고자 한다. 냄새는 1번 헛간에서의 거리(여기서 거리라 함은 지나야 하는 길의 최소 개수이다)가 멀어질수록 감소한다고 한다. 재서기의 발냄새를 최대한 숨길 수 있는 헛간을 찾을 수 있게 도와주자! 입력첫 번째 줄에는 N과 M이 공백을 사이에..

https://www.acmicpc.net/problem/1806BOJ - 부분합문제 유형: 부분합, 투 포인터, 슬라이딩 윈도우문제 난이도: Gold IV시간 제한: 0.5초메모리 제한: 128MB 문제10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N (10 ≤ N  출력첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다. 풀이슬라이딩 윈도우를 이용하면 된다.매번 right를 더해줄 때마다, left쪽에서 뺄 수 있는만큼 빼본다.right를 한칸 밀면, left쪽에서는 sum이상인동..

https://leetcode.com/problems/find-minimum-diameter-after-merging-two-trees/description/leetcode - Find Minimum Diameter After Merging Two Trees문제 유형: 트리, bfs, 그리디문제 난이도: Hard 문제There exist two undirected trees with n and m nodes, numbered from 0 to n - 1 and from 0 to m - 1, respectively. You are given two 2D integer arrays edges1 and edges2 of lengths n - 1 and m - 1, respectively, where edges..

https://www.acmicpc.net/problem/1647BOJ - 도시 분할 계획문제 유형: 최소 신장 트리문제 난이도: Gold IV시간 제한: 2초메모리 제한: 256MB 문제동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다.마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된..

https://leetcode.com/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level/description/leetcode - Minimum Number of Operations to Sort a Binary Tree by Level문제 유형: 정렬, 트리, bfs문제 난이도: Medium 문제You are given the root of a binary tree with unique values.In one operation, you can choose any two nodes at the same level and swap their values.Return the minimum number of operations neede..

https://www.acmicpc.net/problem/15681BOJ - 트리와 쿼리문제 유형: 트리, dfs문제 난이도: Gold V시간 제한: 1초메모리 제한: 128MB 문제간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자. 입력트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105)이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)이는 U와 V를 양 끝점으로 ..

https://leetcode.com/problems/find-building-where-alice-and-bob-can-meet/description/leetcode - Find Building Where Alice and Bob Can Meet문제 유형: 이진 탐색, 모노토닉 스택문제 난이도: Hard 문제You are given a 0-indexed array heights of positive integers, where heights[i] represents the height of the ith building.If a person is in building i, they can move to any other building j if and only if i  and heights[i] Yo..

https://www.acmicpc.net/problem/1197BOJ - 최소 스패닝 트리문제 유형: 최소 신장 트리, 최단 경로문제 난이도: Gold IV시간 제한: 1초메모리 제한: 128MB 문제그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 ..