넘치게 채우기

https://www.acmicpc.net/problem/1967BOJ - 트리의 지름문제 유형: dfs / bfs문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB  문제트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때..

https://leetcode.com/problems/maximum-xor-for-each-query/description/?envType=daily-question&envId=2024-11-08leetcode - Maximum XOR for Each Query문제 유형: 비트마스킹, 비트 조작, 부분합문제 난이도: Medium 문제You are given a sorted array nums of n non-negative integers and an integer maximumBit. You want to perform the following query n times:Find a non-negative integer k  such that nums[0] XOR nums[1] XOR ... XOR nu..

https://www.acmicpc.net/problem/9465BOJ - 스티커문제 유형: 다이나믹 프로그래밍문제 난이도: Silver I시간 제한: 1초메모리 제한: 256MB 문제상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 ..

https://leetcode.com/problems/largest-combination-with-bitwise-and-greater-than-zero/description/?envType=daily-question&envId=2024-11-07leetcode - Largest Combination With Bitwise AND Greater Than Zero문제 유형: 비트마스킹, 비트 조작문제 난이도: Medium 문제The bitwise AND of an array nums is the bitwise AND of all integers in nums.For example, for nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1.Also, f..

https://www.acmicpc.net/problem/1043BOJ - 거짓말문제 유형: 유니온-파인드, BFS, DFS, 그래프 문제 난이도: Gold IV 시간 제한: 2초 메모리 제한: 128MB 문제지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히,..

https://leetcode.com/problems/find-if-array-can-be-sorted/?envType=daily-question&envId=2024-11-06leetcode - Find if Array Can Be Sorted문제 유형: 정렬, 비트마스킹, 슬라이딩 윈도우문제 난이도: Medium 문제You are given a 0-indexed array of positive integers nums.In one operation, you can swap any two adjacent elements if they have the same number of set bits. You are allowed to do this operation any number of times (incl..

https://www.acmicpc.net/problem/13549BOJ - 숨바꼭질 3문제 유형: 다익스트라문제 난이도: Gold V시간 제한: 2초메모리 제한: 512MB 문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있..

https://leetcode.com/problems/minimum-number-of-changes-to-make-binary-string-beautiful/description/?envType=daily-question&envId=2024-11-05leetcode - Minimum Number of Changes to Make Binary String Beautiful문제 유형: 문자열 처리, 그리디문제 난이도: Medium 문제You are given a 0-indexed binary string s having an even length.A string is beautiful if it's possible to partition it into one or more substrings such tha..

https://www.acmicpc.net/problem/12865BOJ - 평범한 배낭문제 유형: 다이나믹 프로그래밍, 배낭 문제문제 난이도: Gold V시간 제한: 2초메모리 제한: 512MB 문제이 문제는 아주 평범한 배낭에 관한 문제이다.한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 ..

https://leetcode.com/problems/string-compression-iii/description/?envType=daily-question&envId=2024-11-04leetcode - String Compression III문제 유형: 문자열 처리, 투 포인터문제 난이도: Medium 문제Given a string word, compress it using the following algorithm:Begin with an empty string comp. While word is not empty, use the following operation:Remove a maximum length prefix of word made of a single character c repeat..