woolog

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

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

https://www.acmicpc.net/problem/2336 정렬과 새그먼트 트리를 이용한 구간최소를 이용하여 푼다는 것을 듣고 시작했는데도, 입력 자체를 잘못 접근해서 삽질을 많이했던 문제다. 우리가 얻어야 하는 정보는 학생 K의 각각의 등수이다. 근데 문제에서 주어지는 정보는 "각 시험에서 1등인 학생부터 N등인 학생이 순서대로 주어진다" 1 2 3 4 5 6 7 for(int i = 1; i Colored by Color Scripter http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호 www.acmicpc.net 알고리즘 분류) greedy 그리디 하면 제일 처음 풀게되는 회의실 배정 문제와 같이, 물건을 내릴 위치는 정해져 있으므로, 가장 먼저 내릴..