백준 (227) 썸네일형 리스트형 백준 20033 - Square, Not Rectangle https://www.acmicpc.net/problem/20033 얼마나 큰 정사각형을 만들 수 있는지를 물어보므로 결정할 수 있는 높이 H를 다음 함수를 사용하여 구할 것이다. $f(H) = $ 높이가 $H$일 때 길이가 $H$ 이상인 선분을 구할 수 있는지의 여부 그러면 $f(H)$의 치역은 true 혹은 false로 결정될 수 있고 true라면 $H$를 더 크게, false라면 $H$를 더 작게 잡을 수 있다. 여기서 파라메트릭 서치를 사용하면 $f(H) = True$인 $H$의 최댓값을 빠르게 구할 수 있고 문제의 목적은 정사각형을 만드는 것이므로 이렇게 구한 $MAX(H)$가 답이다. 따라서 우리는 $f(H)$를 구할 때 $H$ 이상의 너비를 확보할 수 있는지 구하면 된다. 구현더보기12345.. 백준 1398 - 동전 문제 https://www.acmicpc.net/problem/1398 1398번: 동전 문제첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다.www.acmicpc.net 힌트 1더보기동전 교환 문제를 그리디 하게 풀려면 주어진 동전들의 값이 서로 서로소가 아니어야 함이 알려져 있다. 일단 적당한 범위 안에서의 답을 dp로 모두 구해놓고 dp로 도출한 해와 그리디로 푼 해의 차이를 비교해 보자. 유의미한 결과를 얻을 수 있는가?힌트 2더보기30, 40, 80, 90 해설더보기적당히 큰 범위 내에서 dp로 해를 찾은 뒤 그리디하게 구한 해와 비교해보자. 그러면 다음 사실을 발견할 수 있다. 해당 문제의 답을 $f(x).. 백준 2040 - 수 게임 https://www.acmicpc.net/problem/2040 이 문제는 대단히 교육적인 문제이므로 꼭 공부하는 것을 추천한다. 게임 전략 A와 B 둘 다 최적으로 플레이를 한다고 했다. 이를 수식으로 표현하면 어떻게 될까? A의 합을 $sum_{A}$, B의 합을 $sum_{B}$라고 하면 A와 B의 목표는 다음과 같이 정리할 수 있다. A는 $sum_{A} - sum_{B}$를 최소화시켜야 한다. B는 $sum_{A} - sum_{B}$를 최대화시켜야 한다. (혹은 $sum_{B} - sum_{A}$를 최소화시켜야 한다.) 그러면 저 값을 최적화 하는 문제로 표현할 수 있고 이는 동적 계획법으로 시도해볼 수 있을 것이다. 그런데 어떻게 동적 계획법을 해야 할까? 테이블을 다음과 같이 정의한다. d.. 백준 12986 - 화려한 마을 2 https://www.acmicpc.net/problem/12986 $O((N+Q)\sqrt N \log N)$ 솔루션 - Mo's + Indexed heap Mo's 알고리즘 적용을 위해 쿼리를 정렬한다. 그리고 -100000부터 100000까지의 값을 index로 취급하면 가장 많이 출연한 원소의 횟수를 indexed heap로 찾을 수 있다. 그러면 각 쿼리를 처리하면서 원소의 출연 횟수를 구역을 횡단할 때마다 $O(\log N)$의 시간 복잡도로 갱신하게 되고 쿼리의 답은 max indexed heap의 top이 된다. 시간 복잡도 : $O((N+Q)\sqrt N \log N)$ 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22.. 백준 17353 - 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 https://www.acmicpc.net/problem/17353 사전 지식 imos법을 알면 풀이를 쉽게 이해할 수 있다. 이 포스트에서는 imos법을 알고 있다는 가정 하에 설명하도록 한다. 공차가 1인 등차 수열 이 문제는 공차가 1인 등차수열을 구간에 더하면서 포인트 쿼리를 수행한다. 여기서 포인트 쿼리를 구간 쿼리로 바꿔보자. 점 x에 떨어진 별의 개수가 아닌 구간 [1, x]의 합을 구하는 쿼리로 바꾼다. 왜 이렇게 쿼리를 바꾸냐면 쿼리 1을 스위핑 덧셈 문제로 바꾸기 위함이다. 얘를 들어 다음 배열을 살펴보자. 1 2 3 4 5 이 배열의 원소들 $a_{1}, a_{2},... $을 $imos(i) - imos(0)$의 형태로 구하려면 어떻게 할까? 1 1 1 1 1 -5 이렇게 배열을 구.. 이전 1 2 3 4 5 6 7 8 ··· 46 다음
