돌이 코딩하는 방

도입 다음과 같은 문제를 푼다고 생각해보자. 자동차 경주대회가 있었다. 먼저들어온 순서대로 N대의 자동차들에 대한 평균 속력이 주어진다. 하지만 이 차들중에 평균속력이 K이상인 차들은 우승자격이 박탈된다. 어떤 차가 우승하게 될까? 파라메트릭 서치란? 파라메트릭 서치(Parametric Search)는 기본적으로 이분탐색을 베이스로 깔고 들어간다. 나는 Parametric Search를 "조건내 최대(최소)를 찾는 문제를 log의 시간복잡도를 사용해 결정문제로 바꾸는 테크닉"이라고 말하고 싶다. 이 말만 들어서는 의미를 제대로 파악하기 힘들고 도입의 문제를 이용해 이 말을 풀어나가보려고 한다. 파라메트릭 서치의 역할 도입의 문제를 보면 K미만의 숫자 중 가장 큰 숫자를 찾는 문제가 된다. 하지만 Para..

문제 태그 : 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번 나무를 자를지 중간에 비용을 감소 시킨후 자르는 것..