돌이 코딩하는 방

문제 태그 : https://www.acmicpc.net/problem/2472 정말 좋은 문제라고 생각한다. 여러가지 테크닉을 같이 써야 문제를 해결할 수 있다. 그런데 최근에 재채점을 당해 틀려서 다시 푼 김에 글을 작성하였다. 문제 소개 그래프가 주어지고 3개의 출발 지점이 주어진다. 만약 지점 A와 B가 존재해서 출발지점 3곳에 대해서 모두 B가 A보다 출발 지점까지의 거리가 짧으면 A에는 매장을 설치할 수 없다. 각 지점에 대해서 질의를 던지면 그 지점에 매장을 설치할 수 있는지 대답을 해야한다. 문제 풀이 일단 그래프 상에서 어떠한 한 노드를 중심으로 다른 모든 점까지의 거리를 각각 구하는 것은 다익스트라를 3번 돌리는 것으로 쉽게 처리해 줄 수가 있다. 다르게 말하면 우리는 모든 노드에 대해..

문제 태그 : https://www.acmicpc.net/problem/11001 문제 소개 각 날 별로 넣을 때의 가치와 꺼낼 때의 온도가 주어진다. 어떤 김치의 맛은 (숙성 시간)*(김치를 꺼낼 때의 온도)+(김치를 넣은 날 가치)로 정의된다. 만들 수 있는 가장 맛있는 김치의 맛을 구하여라. 문제 풀이 이 문제를 봤을 때는 이 문제가 DnC Optimization을 쓰는 문제인지 모르고 봤다. (DnC Optimization에 대한 설명글) 그리고 풀이를 들었기 때문에 상세한 의식의 흐름과정은 설명할 수가 없다. 그대신 식을 전개해 나가면서 왜 DnC 적용이 되는지를 살펴보려고 한다. 넣은 날의 가치를 $V_i$라고 하고, 꺼낼 때의 온도는 $T_i$라고 하자. 나는 j일때 넣은 김치가 제일 맛있을..

DP 문제에서 $O(N)$의 시간복잡도를 $O(lgN)$으로 줄여주는 또 다른 테크닉이다. DP에 DnC는 굉장히 안어울릴 것 같다. 사실 그렇긴 하다. 사용되어질 조건이 까다롭고, 이 문제에서 DnC를 사용할 수 있는 조건을 만족하는지 알기도 굉장히 어렵다. DnC Opmization을 사용하는 문제는 대체로 굉장히 까다롭고 어렵다. DnC Optimization이란? Divide and Couquer Optimization의 약자로 한글로 해석하면 분할정복 최적화 기법이다. 말 그대로 분할 정복을 사용해서 최적화를 시키는 기법이다. When? $DP[i]=\underset{1\leq j\leq N}{min}F(i,j)$ 에서 $DP[i]=F(i,j)$를 만족하는 $j$를$A[i]$라고 할 때, $If..

문제 태그 : https://www.acmicpc.net/problem/3998 문제 소개 N개의 질량조건이 주어진다. 이 중 가장 큰 값과 단백질의 전체 질량이 똑같은 단백질 구조 중 주어진 질량조건에 단백질의 prefix 질량과 suffix 질량이 가장 많이 포함되어있는 단백질 구조를 출력하시오. 예제) 353.16992는 가장 큰 값으로 단백질이 P하나와 Q두개로 이루어져 있다는 것을 알려준다. 이때 구조를 PQQ또는 QQP로 배치하게 되면 P=97.05276 Q=128.05858 PQ=225.11134 PQQ=353.16992 4개로 가장 많은 질량조건을 만족시킬 수 있다. 문제 풀이 일단 몇 가지 관찰을 하는 것이 중요하다. 정말 단순하고 간단한 것 일수 있지만, 하나하나가 정말 강력하게 작용하..

문제 태그 : https://www.acmicpc.net/problem/13409 ※ 내가 관찰로 푼 문제들 중 하나이다. 따라서 갑자기 생각난 아이디어와 노가다, 말도 안되는 관찰들로 풀이가 이루어 질 예정이다. ※ Blackking과 함께 풀었다. 문제 소개 N개의 상자 그룹이 있다. 각 상자그룹은 A박스와 B박스가 쌓여있는 형태이다. 이 중 몇 그룹을 사용해서 게임을 진행할 것이다. 돌아가면서 A는 A박스와 그 위에 쌓인 박스 모두를 제거하고, B는 B박스와 그 위에 쌓인 모든 박스를 제거한다. 이렇게 진행하며 더이상 할 행동이 없는 사람이 지게 된다. 이때 공정한 게임이 될 수 있는 최대 박스의 갯수를 구하시오. (단, 공정한 게임은 먼저 하는 사람에 따라 승패가 바뀌는 게임이다.) 사고의 흐름 ..

문제 태그 : https://www.acmicpc.net/problem/15134 ※ 내가 관찰로 푼 문제들 중 하나이다. 따라서 갑자기 생각난 아이디어와 노가다, 말도 안되는 관찰들로 풀이가 이루어 질 예정이다. ※ 2018 NEERC가 끝난 후 LOTUS와 함께 풀었다. 문제 소개 테스트 케이스 별로 a,b,c,d 숫자 4개가 주어진다. 총 구슬의 갯수 $n=2^a+2^b+2^c+2^d$이다. 이때 우리는 n개의 구슬인 1묶음을 1개의 구슬씩 n개의 그룹으로 나누어야 한다. 이때 한 번의 행동으로 다음과 같은 작업을 할 수 있다. - (A,B,C) 그룹의 크기가 A인 모든 그룹을 각각 크기가 B인 그룹과 C인 그룹으로 나눈다. (이때 $A=B+C$) 이때 그룹의 최대 크기가 1이 될때까지 걸리는 행동..

최근에 어려운 문제들을 도전해 보면서 느꼈는데 난 관찰에 제일 강한 것 같다. 그냥 문제에서 얻을 수 있는 단서를 관찰하는 능력도 떨어지지는 않지만, 내가 직접 손으로 예제를 만들고 풀어보면서 답을 찾은 경우가 굉장히 많다. 직접 혼자 게임을 진행하며 승리 방법과 조건을 찾는다던가, 작은 모든 경우에 대해 다 해보면서 방향성이나 중요한 사실들을 관찰하는 경우가 꽤 있었다. 툭툭 던진 말이 중요했던 경우도 꽤 많았고, 애초에 이런 것이 좋아서 시작하게 된 PS이다. 사실 이러한 부분을 제외하면 stonejjun이라는 코더가 그렇게 특별한지도 모르겠고, 엄청 뛰어난지도 모르겠다. 개인대회에 그렇게 강점이 있는지 모르겠다. 스페셜리스트 같은 느낌인것 같기도 하다. 이상한 말들은 그만하고, 이 글의 진짜 목적은..

문제 태그 : https://www.acmicpc.net/problem/4008 문제 소개 특정 값 a,b,c와 N명의 전투원들의 전투력이 주어진다. 전투원들은 인접한 전투원들끼리 묶어 몇개의 그룹으로 나눌 것이다. 각 그룹의 조정된 전투력은 그 그룹에 속한 모든 전투원의 전투력의 합을 x라고 했을 때, $ax^{2}+bx+c$이다. 이때 가질 수 있는 그룹의 조정된 전투력의 합의 최댓값을 구하시오. 문제 풀이 이 문제를 딱 보자마다 떠오르는 생각은 DP이다. '인접한 것 끼리 묶는다'도 DP를 쓰기 굉장히 좋은 조건이며, 정확히 DP[i]=1부터 i 까지 로 문제를 해결했을 때의 값으로 정의하면 깔끔하게 해결될 것 처럼 보인다. 이를 통해 DP값에 대한 식을 세워보면 다음과 같이 나온다. $DP[i]=..

문제 태그 : https://www.acmicpc.net/problem/13263 문제 소개 나무를 모두 자르고 싶다. 나무 N개의 길이$a_{i}$가 주어지고 N개의 $b_{i}$가 주어진다. 나무 길이 1을 자를때마다 다시 충전을 해야한다. 이때 충전하는 비용은 지금까지 완벽히 자른 나무의 번호 중 가장 큰 번호의 $b_{i}$이다. 이때 $a_{1}=1$ 이고, $b_{N}=0$ 이며, $a_{i}$는 증가하고 $b_{i}$는 감소한다. 문제 풀이 제일 중요한 사실은 $b_{N}=0$이라는 것이다. N번 나무를 자르면 그 이후로는 드는 비용이 0이기 때문에 이 문제를 다르게 해석하면 N번 나무를 자르는데 얼마나 비용이 드는가? 이다. 한 번에 N번 나무를 자를지 중간에 비용을 감소 시킨후 자르는 것..

CHT란? Convex Hull Trick의 약자로 말 그대로 볼록껍질을 이용한 트릭이다. Why? DP 문제에서 왜 사용하게 되는 트릭일까? DP 관계식이 다음과 같이 나왔다고 생각하자. $DP[i]=\underset{j $ax+b$ When? "DP식들을 일차함수꼴로 표현하여 볼록껍질을 만들어 줌으로써 해결을 한다."를 다르게 말해보면, DP식들을 일차함수 꼴로 표현했을 때 볼록껍질이 나오지 않으면 사용할 수 없는 테크닉이라는 것이다. 볼록껍질일 조건은 맨 위의 식에서 $A[j]$의 단조성이다. 주로 최솟값을 뽑을 때에는 $A[j]$가 계속 감소하게 된다. How? 1. 값 구하기 왼쪽과 같이 DP식에 맞는 직선들이 있을때 우리는 연속한 두 직선의 교점을 구함으로써 각 직선이 담당하고 있는 부분을 알..