본문 바로가기

분류 전체보기

 (42)
Atcoder 문제 Brave CHAIN https://atcoder.jp/contests/abc176/tasks/abc176_f F - Brave CHAIN AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 대회 때 중요 로직들을 생각해냈지만 구현 실수 + 경우를 충분히 계산하지 못해서 맞왜틀만 외치다가 못 푼 문제입니다... 애초에 대회 때 16명 밖에 못 풀었어서 풀었으면 지금까지 앳코더 친 라운드 중에 최고점을 찍을 뻔 했지만.. 다음으로 기약을 하게되었습니다 크흑.. 이 문제는 개인적으로 엄청 흥미로운 문제였고 제 기억에 남기고 싶어서 블로그에 쓰게 되었..
Boj 8222 Distance https://www.acmicpc.net/problem/8222 정수론 문제입니다.. 전 정수론 문제를 좋아하지 않지만 한 번씩 풀어줘야 감을 잃지 않기 때문에 풀어봤습니다. 일단 이 문제는 정수론보단 구현에서 더 애를 먹었습니다.... ( 제가 구현을 진짜진짜진짜 못해서... ) 문제 요약을 하자면 배열 $ 1
삼각형 안에 점의 개수 구하기 $ N^{3} $ 으로 삼각형 안에 점의 개수 구하는 방법입니다. 조건이 한 개 있는데 세 점이 같은 직선 위에 없을 때만 성립합니다. 좌표 평면에 점이 N개가 주어져 있다고 가정하겠습니다. 그럼 N개의 점 중에서 3점을 골라서 삼각형을 만들 수 있는 가짓수는 $ \binom{n}{3} $ 일 겁니다. 우리가 그럼 구하고자 하는 것은 각각 $ \binom{n}{3} $ 개의 삼각형 안에 들어있는 점의 개수 입니다. 어떻게 구하면 될까요... 삼각형을 구한 뒤 그 삼각형 안에 점의 개수를 일일히 세는 방법은 시간복잡도가 $ N^{4} $ 일겁니다. $ N^{3} $ 으로 줄일려면 간단한 아이디어가 필요합니다. 이렇게 $ PABC $ 사각형이 있다고 가정하겠습니다. 그리고 $ dp[A][B][C] $ 를 삼..
Codeforces Global Round 4 풀이 https://codeforces.com/contest/1178 A번 1번 원소 >= x번 원소 * 2 인 지점을 다 더해준 값을 y 라고 합니다. y + (1번 원소)가 전체 배열의 합의 절반보다 strictly 하게 크면 YES 이고 아니면 NO 입니다. B번 처음에 vv 가 w 를 만들 수 있는 모든 경우의 수를 구합니다. 즉 vvovvovv 가 있으면 3일 겁니다. dp 배열로 구성합니다. if(s[x] == 'v') dp[x] = dp[x+1] + 1; if(dp[x]>=2) ans++; }else{ dp[x] = 0; } 이런 식으로 하면 모든 경우의 수가 ans 가 될 것입니다. 그런 다음 처음부터 보면서 o 를 기준으로 왼쪽 오른쪽에 vv의 경우의 수를 곱해주면 됩니다. C번 (1,1) 지..
Codeforces Global Round 9 풀이 문제가 아이디어 성이 깊었으며 어려운 알고리즘을 요구하는 문제도 많이 없었기에 참가자 모두가 즐겼을 법한 셋이였습니다. A번 홀수개의 배열이 주어지고 각 배열의 값의 부등호를 바꾸어서 $$a_{i+1} - a_{i}$$ 이 양수 또는 0이 (n-1)/2 개 음수 또는 0이 (n-1)/2 개를 만족하는 것입니다. 답은 간단합니다. 모든 값을 일단 양수로 만든 뒤 짝수번 째 값을 음수로 만드는 것입니다.그러면 각 배열의 값에 상관없이 음 양 음 양 .. 이런 식으로 됩니다. B번 각 배열의 값이 그 지점과 인접한 원소의 갯수보다 크거나 같은 지를 비교하고만약 모든 배열의 값이 크거나 같으면 전체 배열을 돌면서 각 지점마다 인접한 원소의 갯수를 출력해주고아니면 NO 를 출력하면 됩니다. C번 이제부터 문제가 ..
BCC 정점 기준으로 간선 기준으로 BCC 를 나누는 것은 구글에 치면 있기에 정점 기준 BCC 를 쓸려고 합니다. 나중에 까먹지 않을라고 쓰는 것이 큽니다. 알고리즘은 간단합니다. dfs를 돌면서 어떤 정점에서 역방향 간선이 있으면 그곳은 사이클이 있기 마련입니다. 그랬을 때 역방향 간선이 가르키는 정점의 부모 정점 이하의 지나왔던 정점은 사이클일 것입니다. 그리고 그 역방향 간선이 가르키는 정점과 부모 정점 끼리 또 사이클을 만들면 그 전 사이클에다 추가해야 될 것입니다. 이 것이 알고리즘의 끝입니다. 코딩이 중요한데 stack으로 관리합니다. stack 두개로 관리하면서 한 개는 지나온 정점 두 번째는 지나온 정점이긴 하지만 사이클이 없는 제일 마지막 정점(?) 이라 생각하면 되겠습니다. 그럼 스택 두 번째에서 사이클이..
재밌는 문제들 ( 계속 업데이트 ) 수학 부문 1. codeforces 1269 D 아이디어가 참신함. 2*1, 1*2 막대기가 도미노에 놓아질 때 어떤 점을 중심으로 상하좌우로 연결됨으로 체스판 같은 모양이 나옴 그래서 도미노에서 검은 점과 흰 점의 갯수의 더 작은 값이 답인 문제 이런 문제는 접근 방법에 대해서 깨닳음을 주기에 너무 좋았다.
19.12.17 608(div2) D -> 그 당시 대회 할 때 감기 기운이 있어서 집중이 안됐다 ㅠㅠ 이걸 왜 못 풀었을까 할 정도로 쉬운 문제.. 608(div2) E -> 수학 문제. 난 조금 복잡하게 풀었는데 짧게 짠 사람들도 많았다. 저녁에 약속이 있어서 많이 풀지는 못했다 흑흑 ( 애초에 오전엔 놀고 오후엔 요리 공부한다고 별로 안했다 ㅎㅎ..) 낼 할 것 1. Li-Chao Tree 공부 , 백준에 있는 문제도 풀기 2. 저녁에 약속 있어서 못할 듯한 코포 글로벌 라운드 virtual 돌기 3. virtual 돌면서 못 푼 문제들 풀기 4. NERC 문제 풀기 ( 100명 이상 푼 문제에 한해서 )

티스토리툴바