넘치게 채우기

https://leetcode.com/problems/maximum-beauty-of-an-array-after-applying-operation/description/leetcode - Maximum Beauty of an Array After Applying Operation문제 유형: 정렬, 슬라이딩 윈도우문제 난이도: Medium 문제You are given a 0-indexed array nums and a non-negative integer k.In one operation, you can do the following:Choose an index i that hasn't been chosen before from the range [0, nums.length - 1].Replace nums..

https://www.acmicpc.net/problem/1195BOJ - 킥다운문제 유형: 문자열 처리, 완전 탐색문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제세계적으로 유명한 엄지민 자동차 회사는 효율적인 킥다운 장치를 만들어달라는 의뢰를 받았다. 킥다운이란 자동차에서 낮은 기어로 바꾸는 장치를 의미한다. 연구 끝에 효율적인 킥다운 장치는 '이'와 '홈'이 불규칙하게 배열되어 있는 기어로 만들어져야 한다는 것을 알았다.첫 번째 그림과 같이 두 기어 파트가 서로 마주보고 있게 된다. 튀어나온 것이 기어의 이, 들어간 곳이 홈이다. 그리고 이들을 두 번째 그림과 같이 서로 맞물리게 끼우는 것으로 킥다운 장치를 만들 수 있다. 하지만 문제는 맞물리게 하였을 때 가로 너비가 짧을..

https://leetcode.com/problems/find-longest-special-substring-that-occurs-thrice-i/description/leetcode - Find Longest Special Substring That Occurs Thrice I문제 유형: 문자열 처리, 슬라이딩 윈도우문제 난이도: Medium 문제You are given a string s that consists of lowercase English letters.A string is called special if it is made up of only a single character. For example, the string "abc" is not special, whereas the stri..

https://www.acmicpc.net/problem/1005BOJ - ACM Craft문제 유형: 위상 정렬문제 난이도: Gold III시간 제한: 1초메모리 제한: 256MB 문제서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 위의 예시를 보자.이번..

https://leetcode.com/problems/special-array-ii/description/leetcode - Special Array II문제 유형: 이진 탐색문제 난이도: Medium 문제An array is considered special if every pair of its adjacent elements contains two numbers with different parity.You are given an array of integer nums and a 2D integer matrix queries, where for queries[i] = [fromi, toi] your task is to check that subarray nums[fromi..toi] is specia..

https://www.acmicpc.net/problem/1189BOJ - 컴백홈문제 유형: 백트래킹문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f       bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde       a...  abcd  abc.  abcd  a...  a.gh  abc. 거리 :  6     6     6     8     8    10    6위..

https://leetcode.com/problems/two-best-non-overlapping-events/description/leetcode - Two Best Non-Overlapping Events문제 유형: 이진 탐색문제 난이도: Medium 문제You are given a 0-indexed 2D integer array of events where events[i] = [startTimei, endTimei, valuei]. The ith event starts at startTimei and ends at endTimei, and if you attend this event, you will receive a value of valuei. You can choose at most two ..

https://www.acmicpc.net/problem/1183BOJ - 약속문제 유형: 수학, 정렬문제 난이도: Silver II시간 제한: 2초메모리 제한: 128MB문제마법사 N명이 머글 문화를 이해하기 위해 머글과 약속을 잡았다. 각 마법사는 한 명의 머글을 만날 예정이다. 하지만, 마법사는 약속 시간보다 빨리 또는 늦게 도착할 수 있기 때문에 고민에 빠졌다. 결국 기다리는 시간을 최소화 하기 위해 모든 약속 시간을 T씩 미루려고 한다. 기다리는 시간은 먼저 도착한 사람이 늦게 도착한 사람이 도착할 때까지 기다리는 시간을 의미한다.마법사의 약속 시간은 A1, A2, ..., AN이고, 도착 시간은 B1, B2, ..., BN이다. 약속 시간을 T만큼 미루면, 기다리는 시간의 합은 |Ai + T ..

https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag/description/leetcode - Minimum Limit of Balls in a Bag문제 유형: 이진 탐색문제 난이도: Medium 문제You are given an integer array nums where the ith bag contains nums[i] balls. You are also given an integer maxOperations.You can perform the following operation at most maxOperations times:Take any bag of balls and divide it into two new bags with a po..

기본적인 브루트 포스 방법은 O(2^n)이 걸린다.그래서, n=20인 경우에만 시간 효율적으로 사용할 수 있다. 개선해서, n MITM, Meet-in-the-Middle알고리즘이다. n길이의 배열 arr이 주어지고, 합이 s인 부분배열의 개수를 구한다고 해보자. 핵심 아이디어는 다음과 같다:배열을 절반으로 나눠서, 각각 브루트 포스로 모든 조합을 구한다. 각각 left, right라 한다.이진탐색을 이용할 것이기에, right를 정렬해준다.  left의 조합들에서 각각 right에서  target = s-leftsum값에 대해 upper_bound(target보다 초과인 큰 요소의 첫 인덱스), lower_bound(target이상인 요소의 첫 인덱스)를 구해서 upper_bound - lower_bo..