Go Gradually - Repository

알고리즘 & 라이브 코테의 접근 전략

기존 문제 해결 전략은 일반적으로 주어진 요구사항을 구현할 때의 접근 방식을 작성해두었다.이번 글은 알고리즘과 라이브 코테로 제한해서 좀 더 자세하게 적어보려 한다. 문제 풀이 단계 - 어떠한 순서대로 문제를 접근해야 하나?아이디어 획득 : “추론”하기이 시기는 체계젹인 상태 유지가 특히 중요한 시점이다.문제만 바라보고 있어선, 아무것도 변화하지 않는다.지금의 너는 문제를 제대로 이해하지 못하고 있다.놓친 조건은 없는지 검토하라.문제의 조건을 "우아한" 수준으로 정의할 수 있는지 검토해라.문제 알고리즘/특징의 “증명”으로 아이디어어떻게 이 동작이 수학적으로 증명되는가?{BruteForce, Greedy, D&C, DP, Graph, math}전체 알고리즘이 “결국 구하고자 하는 것” 놓치지 않기“책임” ..

문제를 해설할 때 특수한 DP로 카데인을 자주 언급하게 되는데,카데인 알고리즘이 정확히 어떤 이점이 있는지, 다른 DP와는 무엇이 다른지 명확히 설명한 글이 없어 이렇게 글을 작성한다. 핵심 아이디어는 다음과 같다.dp[i]: 반드시 i에서 끝나는 최대 부분 배열 합즉, 한쪽 끝을 고정함으로써 중간의 연산을 최적 부분구조 + 중복 부분 문제의 형태로 만드는 아이디어가 핵심이다. 그러면 이 문제에서 전체 정답은 max_i dp[i] 가 된다.마지막 원소 a[i]를 포함해야 하므로 두 선택지뿐이다.a[i] 혼자로 새로 시작한다.i−1에서 끝나는 최적해 dp[i−1]에 a[i]를 이어붙인다.따라서 점화식은 다음과 같다.초기값이 점화식은 “끝이 i인 최적해”의 정의에서 바로 나온다.아이디어임의의 최적 부분 배..

오늘도 코드포스 문제풀이를 하던 도중, 익숙한 방정식의 형태가 등장했는데, 정확히 어떻게 풀어야 하는지 기억이 잘 나지 않아, 이번 기회에 확실하게 정리하려고 한다.Div.2 # 955 D번을 풀던 중, 다음과 같은 방정식을 마주하게 되었다.$$ D = px + qy + rz + ... (x, y,z,... \in \mathbb{Z}) $$다음과 같은 형태의 방정식을 "디오판토스 일차방정식" 이라고 한다.실제로 디오판토스 방정식은 차수가 하나씩 늘어갈수록 난이도가 지수적으로 증가한다고 한다.지나치게 깊게 들어가지 않으면서, 적절하게 해당 해의 존재성을 증명하는 방법을 알아보자.위 방정식의 해가 존재하는 지를 구성적 증명으로 처리하려면, 완전 탐색 or 그래프 탐색 방식으로 접근해야 하는데, 이는 지나치게..