woolog

문제 : codeforces.com/contest/987/problem/E Problem - E - Codeforces codeforces.com 풀이참고 : jeonggyun.tistory.com/125?category=737081 Codeforces Round #485 (Div. 2) 풀이 문제 코드 * div1과 div2는 문제를 공유하므로 혹시 없는 문제는 같은 Round의 다른 division을 찾아보시기 바랍니다 A. Infinity Gauntlet 생략. 저는 map 만들어놓고 하나씩 지웠습니다. B. High School: Become.. jeonggyun.tistory.com 최근 에디토리얼을 보다가 그건 이문제와 유사하니 이것도 한번 풀어보라 해서 풀게된 문제. 길이가 n인 수열이 주어..

codeforces.com/contest/1513 그동안 문제 풀고 틀린 건 그냥 넘어가는 경우가 많다 보니 비슷한게 또 나오면 또 틀렸던 경우가 많아서(모르는건 모르는거더라..) 가급적 풀이를 보고 이해할 수 있는 데까지 이해해 보기로 했다. A. Array and Peaks 길이 n인 배열에서 peak의 개수가 k인 임의의 배열을 만든다. index가 0부터 시작하는 기준 홀수번째 index의 위치들이 peak가 될 수 있는 위치이며, k가 이 수보다 많으면 불가능하다. 가능한 경우 k개의 peak의 위치의 가장 큰 수 부터 순서대로 집어놓고, 나머지 peak가 아닌 부분에는 수가 감소하는 순서로 그대로 넣으면 된다. #include using namespace std; typedef long lon..

참고 사이트 : www.geeksforgeeks.org/determine-whether-universal-sink-exists-directed-graph/ introduction to algorithm 책의 22장 그래프 22.1_6번 문제이다. 방향 그래프 G에 대해 인접 행렬이 주어졌을 때, universal sink(진입차수가 [v]-1이고, 진출차수가 0인 노드)의 존재여부를 O(n)에 판단하는지 여부를 보이는 문제인데 인접행렬의 시간복잡도가 O(n^2)인 반면 , O(n)에 해결해야 하기 때문에 모든 edge의 정보를 다 봐서는 해결할 수 없다. 인접행렬의 한 성분 a[i][j]의 값이 0이면, j의 indegree가 [v}-1 보다 작아지므로, j번 노드가 sink가 아님을 알 수 있다. 반대..

www.acmicpc.net/problem/1398 tag : 그리디,디피 설명 : 동전 문제를 풀 때, 그리디로 해결하는 경우, 또 DP로 해결하는 경우 2가지가 있었다. 그리디로 풀 수 있는 조건은 무조건 큰 단위 동전을 많이 쓰는 것이 가장 이득인 경우 이며, 이를 만족하려면 각 동전들이 서로 배수 관계를 이루어야 한다.( ex 1원 10원 100원..) 문제에서 먼저 같은 규칙을 갖는 작은 단위부터 생각을 해보자. 1,10, 25원 동전이있을때, 25원 동전을 쓸 수 있다고 무조건 쓰는 것이 가장 이득이 아님을 알 수 있다. 이는 25원이 10원의 배수가 아니여서 이기도 하지만, 가장 간단한 예시로 40원을 25원을 쓴 경우 (25*1 + 10 *1 + 1*5 ) 이렇게 총 7개가 필요하지만 25..

cp-algorithms.com/ Main Page - Competitive Programming Algorithms cp-algorithms.com 러시안- 갓들이 알고리즘 정리 및 설명 한 것을 영어로 번역해서 모아둔 사이트이다. 틈틈이 하나씩, 혹은 문제 풀다 막힐 때 하나씩 보면서 공부하려고한다.

www.acmicpc.net/problem/1114 알고리즘 : 이분탐색(파라메트릭) + 그리디 몇주 전 풀고 올려야지! 하고 생각만 하다 이제야 올리는 문제다. 처음에 문제 분류가 그리디 + 이분탐색으로 되있어서 난 그리디 못하니까 이분탐색만 써서 풀어야지 했다가 여러번 삽질하고서야 둘다 써야 된다는걸 알았다. 이분 탐색으로 일단, 최대로 자르는 통나무의 길이가 x일때 조건에따라 자르는게 가능한지 아닌지를 찾아준다. 왜 이런식으로 잡는지, 파라메트릭으로 왜 되는지 다시 한 번 집고 넘어가자면 f(x) : 최대 통나무의 길이를 x로 잡을때, 조건에 따라 자르는 것이 가능하다 (boolean 값 return) 라고 하면, x의 증가에 따라 f(x)의 값이 ... 0 0 0 0 0 0 1 1 1 1 1 1...

https://www.acmicpc.net/problem/3830 dijoint -set에 추가적으로 d[u] = u와 u의 set 상에서의 조상의 거리 를 나타내는 배열을 관리해주면 된다. 이 문제를 계속 틀리면서, disjoin-set 자료구조에 대해 다시한번 정리할 필요성을 느꼈다. p[u] = 이 노드가 속하는 set의 조상 노드의 번호를 나타내는 번호. find나 merge를 처리하는 중에 갱신된다. find() 연산이 dijoint-set에서 하는 역할은 2개이다. 1) 이 노드가 속하는 set의 조상 노드의 번호를 return 2) p[]배열을 갱신해준다, 즉 자기의 조상을 가리키게 갱신해준다(경로압축) disjoint-set은 find와 merge 연산을 통해서 갱신, 유지되기 때문에, 추..

https://www.acmicpc.net/problem/1750 1750번: 서로소의 개수 가능한 경우의 수는 (2,3), (4,3), (2,4,3)이다. www.acmicpc.net 바텀업 2차원 디피로 풀 수 있는 문제이다. 주어진 수열을 처리하기 쉽게 정렬해준뒤 (이때, 중복을 생각하지 않아도 된다고 생각하면 안된다 수열 S = {2,2,3},이라고할때, {2,3}이 0번째 인덱스의 2와 1번째 인덱스의 2를 사용하는 2가지 경우가 나올 수 있기 때문이다. (같은 수더라도 고른 위치에 따라 경우가 다르다)) 2차원 테이블 dp[i][j] = i번째 인덱스까지 보고있을 때, 최대공약수가 j인 것의 총 개수 v = 수의 리스트 1) dp[i][v[i]]=1; for (int j = 1; j n; ve..

태그 : 분할정복 https://www.acmicpc.net/problem/14601 14601번: 샤워실 바닥 깔기 (Large) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 7) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K) www.acmicpc.net 처음에는 k의 크기가 large문제임에도 7인걸로 보아서 3개를 깔을수있는 완전탐색 분기를 어떻게하면 효율적으로 짤까 생각했었다. 완탐이 아직 부족한가보다 하고 이 문제를 쳐보니까 이산수학, 그 중에서도 수학적 귀납법 으로 증명할 수 있는 트로미노 타일링이라는 유명한 문제였고, 이 문제에서 요구하는 타일을 전부 칠하는 과정 또..

https://www.acmicpc.net/problem/6066 6066번: Buying Hay Farmer John is running out of supplies and needs to purchase H (1