yunny.world

x와 가장 가까운 수 y의 후보는 x보다 큰 수 중 최소 x보다 작은 수 중 최대 이므로 lower_bound 결과 그보다 하나 앞에 것 만 비교해서 작은 것을 뽑으면 O(logn)에 x와 가장 가까운 수 y를 찾을 수 있다. ll x, y; ll dist = INF; vector v; auto i = lower_bound(v.begin(), v.end(), x); if (i != v.end()) if (*i - x < dist) { dist = *i - x; y = *i; } if (i != v.begin()) if (*(--i) - x < dist) { dist = *i - x; y = *i; } https://www.acmicpc.net/problem/23876 (Connecting Two Barn..

Vermeil의 추천 문제.. 감사요! 이런 발상 쓰는 문제 처음 만나봐서 신기해서 글로 써둘까 한다. https://www.acmicpc.net/problem/9446 9446번: 아이템 제작 첫째 줄에는 아이템 종류의 수 n과 제작 방법의 수 m이 주어진다. (1 ≤ n ≤ 10,000, 0 ≤ m ≤ 100,000) 둘째 줄에는 각 아이템의 가격 ci가 아이템 번호가 증가하는 순서대로 주어진다. (0 ≤ ci ≤ 109) www.acmicpc.net 풀이 일단 이 문제의 핵심은 x + y → a 와 같이 제작할 수 있다면, 간선 x → a의 비용은 y까지의 최소 비용, 간선 y → a의 비용은 x까지의 최소 비용 이라는 점이다. 처음에는 0번 정점에서 시작해서 아이템을 구매하는 것을 의미하는 간선을..

-@yunny_world & *s3..g3 & s#100.. 앞으로 가능한 자주 solved.ac에서 위와 같이 문제 뽑아서 1시간 동안 푸는 연습을 해야겠다. BOJ 23057 도전 숫자왕(S2) 더보기 문제 요약: N개의 숫자 카드 합보다 작거나 같은 수 중, 카드에 적힌 수의 합으로 만들 수 없는 수의 개수를 구하자. 풀이: N

https://www.acmicpc.net/problem/18240 18240번: 이진 탐색 트리 복원하기 가능한 수열이 있다면 첫째 줄에 수열 A1, A2, ..., AN의 값을 공백으로 구분하여 출력한다. 가능한 수열이 여러 개라면 아무거나 출력해도 좋다. 가능한 수열이 없다면 첫째 줄에 -1을 출력한다. www.acmicpc.net 풀이 이진 탐색 트리의 모양이 정해지면, (중위순회의 방문 순서) = (그 노드의 값)으로 해당 노드의 값을 찾을 수 있다. 다만, 이진 탐색 트리를 만들 수 없는 경우가 생기는데, 바로 앞에 깊이 i인 경우가 없는데 깊이 i+1인 경우가 나오는 경우이다. 이 경우를 자세히 살펴보면 아래와 같다. dep[i - 1] < dep[i] / 2 + 1 인 경우에는 깊이 i의 ..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 가장 큰 수를 만들기 위해선 수를 문자열로 보았을 때, 앞쪽 수가 무조건 큰 것이 유리하다. 따라서, 오름차순 모노톤 스택을 관리해 주면 된다. 즉, 스택의 안쪽에 있을수록 큰 숫자가 존재하도록 한다. 구체적으로는, (스택의 top 0) 일때, 스택에서 pop하면서 k를 1씩 감소하면서 관리하면 된다. 숫자를 정확히 k개 지우는 것을 처리하기 위해 다음과 같이 처리해주었다. (k > 0)일때만 스택에서 pop을 하도록 하여, 숫자를 k개..

https://www.acmicpc.net/problem/11581 11581번: 구호물자 서기 2050년 엄청나게 강력한 폭풍이 인천을 강타했다. 강력한 폭풍의 영향으로 모든 사람은 대피소로 대피하였으며, 많은 도로가 유실되었다. 그나마 남아있는 도로도 모든 표지판과 가로등이 www.acmicpc.net 풀이 1번에서 DFS를 시작해서 사이클이 있는지 판단하면 된다. 이때, 정점을 3가지 상태로 표현해서 구현을 해야 한다. vi[i]의 값이 0일때, 아직 정점을 방문하지 않았다. 1일때, 정점을 방문 중이다. 2일때, 정점을 방문 완료했다. 정점을 방문 완료한 이후에는, 더이상 그 정점을 방문할 필요가 없다. 정점을 방문 중에, 그 정점이 호출되면 사이클이 존재한다. 코드 ll n; vector g[1..

https://www.acmicpc.net/problem/23743 23743번: 방탈출 첫 번째 줄에는 방의 개수 $N$과 설치할 수 있는 워프의 개수 $M$이 주어진다. ($2 \le N \le 200\,000$, $1 \le M \le 100\,000$) 다음 $M$개의 줄에는 워프의 정보를 나타내는 세 정수 $a_i$, $b_i$, $c_i$가 공백으 www.acmicpc.net 풀이 새로운 0번 정점을 정의해서, i번 정점과 t[i]의 시간을 가지는 간선을 이은 후, MST를 구하면 된다. 처음에, 모든 정점들이 연결되어 있지 않을 때 되게 귀찮다고 생각했었는데, 공식 풀이를 보고 새 정점 만든 뒤 기존 정점들과 잇는 방식을 이용해 해결할 수 있음을 알게 되었다. 이와 같은 테크닉을 최대 유량 ..

https://www.acmicpc.net/problem/16400 16400번: 소수 화폐 구매하려고하는 물건의 값 N(2 ≤ N ≤ 40,000, N은 정수)이 주어진다. www.acmicpc.net 접근 방법 dp로 풀어야겠다는 생각은 바로 했는데, 내가 세운 dp식이 중복을 처리해주지 못했다. 여기서 '동전 dp' 문제가 떠올랐어야 하는데, 3달 전에 풀어놓고 까먹고 있었다.. 화가 난다..게다가 3달 전에도 풀이를 보고 풀었었다.. 풀이 / 시간 복잡도 dp[j] += dp[j - i] (i는 1

BOJ 12845 모두의 마블(S3) 더보기 max 레벨 * (n - 1) + 나머지 모든 레벨 합 이 답이다. BOJ 25197 합주단 곰곰(G3) 더보기 어떤 한 곰곰의 색이 정해졌을 때, 다른 한 곰곰이 그 색과 같은 확률은 1/k, 이런 두 곰곰을 선택할 수 있는 횟수는 nC2 이므로, 기댓값의 선형성에 의해, k*nC2 가 답이다. BOJ 12842 튀김 소보루(S2) 더보기 나는 이분탐색으로 풀었다. wbcho0504님 코드를 보니, set 를 이용해 구현하여 풀 수도 있는 것 같다. 일단 어떤 시간 T를 기준으로 n-s개의 튀김 소보루를 다 먹거나, 아니게 되므로 이분 탐색으로 해당 갯수의 소보루를 다 먹는 최소의 T를 찾자. 찾은 T와 n-s의 차이를 이용해서 마지막으로 소보루를 집은 사람..

https://m.blog.naver.com/haybbang/221437143854 Visual Studio 콘솔 창 꺼짐 현상 해결 (Ctrl+F5 디버그하지 않고 시작) 종강하고 오랜만에 공부하려 마음을 먹고 비주얼 스튜디오에 새 프로젝트를 만들고 간단한 출력문부터 쳐봤... blog.naver.com https://2jinishappy.tistory.com/55 PS/알고리즘 문제풀이 처음 시작하기(3) - freopen 함수를 활용한 입출력 간소화 우리는 알고리즘 문제를 풀 때 엄청나게 많은 시행착오를 거친다 요즘에는 알고리즘 문제 사이트, 기업 코딩테스트, 대회 문제 등에서도 입출력 형식은 거의 정해져있다 보통 많은 테스트케이 2jinishappy.tistory.com https://miniol..