yunny.world

https://codeforces.com/contest/1796/problem/C Problem - C - Codeforces codeforces.com 이 문제를 풀면서 본 조건이 자주 나오는 것 같아 정리해 두려고 한다. 물론 웰노운이다. 그냥 자동적으로 떠올릴 수 있도록 하기 위해서 글을 쓴다. A set of positive integers S is called beautiful if, for every two integers x and y from this set, either x divides y or y divides x (or both). 위 조건이 주어졌을 때 가장 먼저 떠올려야 하는 것은 제곱수이다. 즉, 위 조건을 만족하는 집합은 \( a^x (x >= 0) \) 이다. 증명은 귀류법..

https://icpc-sinchon.io/ Main | ICPC Sinchon 신촌지역 대학교 프로그래밍 동아리 연합 icpc-sinchon.io 0. 오늘 치룬 캠프 콘테스트 결과에 만족스럽지 않아서 게임하다가 문제 좀 풀려하는데, 귀찮아져서 후기글을 써볼까한다. 개인적으로 대회 결과에 미련이 많이 남는 것 같다... 1. 강의 개인적으로 친해지고 싶었던 학교 선배들이 중급 강의를 하신다길래 사실 안듣을려 했다가 듣게 되었다. 초급, 중급 강의를 모두 들었던 작년 여름과는 달리 이번에는 중급 강의만 들었었다. 저번에는 없었던 게임이론, 기하와 같은 강의들이 진행되어서 새로운 알고리즘도 많이 배웠다고 생각한다. 사실 강의만 듣고, 주어진 문제들을 모두 푼다고 해서 그 알고리즘을 자유자재로 쓸 수 있는 ..

https://codeforces.com/contest/1792/problem/D Problem - D - Codeforces codeforces.com 이 문제를 풀다가 이 성질을 알아내서 정리해 두려 한다. 고수들은 이미 다 알고 있었겠지? 여기서 순열의 정의는 다음과 같다. a permutation of length m is a sequence of m distinct integers from 1 to m. 결론부터 말하자면, 순열 A의 인덱스 배열을 B라 하면, B도 순열이고, 순열 B의 인덱스 배열은 A이다. 예시를 살펴보면 쉽게 감을 잡을 수 있다. A: 3 4 5 2 1 → B: 5 4 1 2 3 B: 5 4 1 2 3 → A: 3 4 5 2 1 증명은 아직 잘 모르겠다. 생각나면 추가하도록..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 일단, 문제를 다음과 같이 해석할 수 있다. (인덱스 → 선택된 학생의 번호) 의 간선들로 이루어진 그래프에서 사이클을 구성하지 않는 정점의 개수를 구하라. https://yunny-world.tistory.com/56 [BOJ] 11581번 : 구호물자 https://www.acmicpc.net/problem/11581 11581번: 구호물자 서기 2050년 엄청나게 강력한 폭풍이 인천을 강타했..

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개..