본문 바로가기

728x90
반응형

코드포스

[Codeforces] Round #709 (div. 2) A ~ D 풀이 2021.03.21 22:20 ~ 00:35 본 라운드 참여 (performance = 1844) 테크노컵은 뭔가 항상 어려운 느낌이다... 생각보다 퍼포먼스가 나쁘지 않게는 나왔는데, 개인적으로 요즘 코포 폼이 조금 올라왔다고 생각해서 더 아쉬운 기분이 든다. A. Prison Break (*800) 모든 칸들에서 밖으로 나갈 수 있기 위해서 제거해야 하는 벽의 수의 최소를 구하는 문제이다. 답은 가로 * 세로, 즉 칸의 개수이고 대회중에는 직관적으로 빠르게 해결했다. 정확한지는 모르겠으나 증명을 하자면, 각 칸마다 해당 칸에서 시작해서 밖으로 나갈 수 있는지 없는지를 상태로 표현하고, 벽이 제거된 이웃한 칸은 하나의 칸으로 합쳐진다고 생각하자. 벽을 하나 제거했을 때 밖으로 나갈 수 없었던 2개 이상..
[Codeforces] Educational Round 102 A ~ E 풀이 2달 만에 본계로 참가했다. 부계로 계속 못 올라가는 게 현타 와서 마음을 다 비우고 본계로 했는데 약간 올랐다... 한동안 1800 퍼포 이상을 찍어본적이 없었는데 아이디에 적응하는 건가....? CF 1473A. Replacing Elements 배열의 어떤 원소를 다른 두 원소의 합으로 바꿀 수 있다. 이때, 배열의 모든 원소를 d 이하로 만들 수 있는지에 대한 문제이다. 기본적으로 주어지는 모든 원소가 d 이하이면 아무런 작업을 하지 않아도 된다. 만약 d보다 큰 원소가 하나 이상 존재한다면, 해당 원소를 바꿔주는 최적의 경우는 배열의 모든 원소 중 제일 작은 값 2개를 골라 바꿔주는 경우이므로, 배열을 오름차순으로 정렬하여 A[1] + A[2]가 d이하이면 YES이다. [소스코드] #includ..
[Codeforces] Round #694 (Div. 2) 풀이 2021. 01. 05 23:35 본 라운드 참가 실력이 정체되어있다. 예전엔 더 올라갈 수 있는데 운이 안 따라주는 느낌이었다면 지금은 느낌이 좀 다르다.... 재활이 꽤 오래 걸릴 것 같다. 1471A. Strange Partition 주어진 배열에서 인접한 두 원소를 대신해서 두 원소의 합으로 대체할 수 있다. 배열의 원소는 1개만큼 줄어든다. 이 연산을 원하는 만큼 한 후에, 배열의 각 원소를 x으로 나눈 값을 올림 하여 모두 더한 합의 최솟값과 최댓값을 구해야 한다. 최대인 경우는 연산을 한번도 하지 않은 원래의 배열에서 합을 구해주는 경우이고, 최소인 경우는 연산을 n-1번 적용한, 즉 배열의 원소가 1개만 남았을 때이다. [소스 코드] #include using namespace std; u..
[Codeforces] Educational Round 76 (A ~ E) 풀이 2021.01.01 23:00 virtual 참가 / Performance = 1841 [풀이] 1257A. Two Rival Students 수직선상에 두 사람이 서있고, 한번 작업을 수행하면 두 사람의 거리를 1만큼 더 멀게 할 수 있다. 최대 x번 작업을 수행할 수 있으므로, 멀어질 수 있을 만큼 최대한 이동시켜준다. int main(void) { int T; cin >> T; while (T--) { int n, x, a, b; cin >> n >> x >> a >> b; if (a > b) swap(a, b); cout T; while (T--) { int x, y; cin >> x >> y; if (x >= y) cout > n; vector cnt(n + 1); int ans = MAX; f..
코드포스 블루, 퍼플 달성 후기 및 일지 & 공부법 (21.05.31 오렌지를 달성했습니다! https://rebro.kr/145) 블루를 찍고 후기를 쓰려고 하였으나 정말 운이 좋게 빠르게 퍼플을 찍고 이제야 쓴다. 사실 아직 완전한 퍼플은 아니라고 생각한다. 오렌지, 레드도 아닌데 뭘 이렇게 난리를 치냐라고 생각할 수도 있지만... (약간 그렇긴 하다) 이 글을 쓰는 가장 큰 이유는, 내가 민트에서 블루를 가고 싶어서 몇개월동안 허덕일 때 정말 스트레스를 많이 받아서, 다른 사람들의 조언을 얻으려고 막 검색을 해봐도 다들 내 눈에 보이지도 않는 '오렌지, 레드 가는 방법'이나 아니면 정말 당연한 조언들뿐이었다. 그래서 불과 한 달 전의 나처럼, 민트나 블루를 가고 싶어 하는 사람들이 매우 많다는 것을 알기 때문에, 혹시나 도움이 되지 않을까 싶어서 글..
완전 탐색 (Brute-Force Search / Exhaustive Search) 알고리즘 1. 완전 탐색이란? 컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. '무식하게 푼다'라는 의미인 Brute-Force (브루트 포스)라고도 부른다. 이름이 거창하게 지어져 있지만 사실 완전 탐색 자체로는 알고리즘이라고 부르긴 그렇고, 문제 푸는'방법'이라고 이해하면 편할 것 같다. 알고리즘을 모르는 사람이 프로그래밍 문제를 푼다면, 당연히 가능한 모든 경우들을 다 구해서 그중에 만족하는 답을 찾아낼 것이고 이 과정 자체가 완전 탐색이다. 대신에 이 방식은 절대 답을 못 구하는 경우는 없으므로 나름 강력한 방법이다. 예를 한번 들어보자. "10개의 정수 원소로 이루어진 수열이 있다. 이 수열에서 두 원소를 선택해서 구한 합의 최댓값을 구하시오. " 이..