code-challenge.elice.io Day 6 문제는 밤 11시 30분 정도에 접속해서 본 다음 열심히 고민했는데 풀지 못했고.. 적당한 전략으로 60점 정도의 부분 점수를 긁었습니다. Day 7부터는 긴장을 늦추지 말고 일찍 확인해야겠습니다! 엘리스 코드 챌린지 Day 7에는 '계기판 조작하기'라는 문제가 나왔습니다.Day 7 문제를 보고 저는 우선 digit DP를 떠올려 보았습니다. 하지만 digit DP를 짜는 것이 번거롭기 때문에, 다른 방법이 있는지 좀 더 고민해보았습니다.그런데 그냥 näive한 방법이 통과할 것 같아서 그렇게 풀어 맞췄습니다. 방법은 그냥 '자연수 $i$의 모든 자릿수의 종류가 정확히 $K$일 때까지 $i$를 늘리며 반복'입니다.최악의 경우는 $N=10^7$인 경우인..

code-challenge.elice.io사진을 못 찍었습니다.원소 $N$개의 $2^N$가지 모든 부분수열의 합들이 주어졌을 때, 원래 원소 $N$개를 오름차순으로 구해서 출력하면 되는 문제였습니다. 10시 알람에 깨서 비몽사몽 풀었더니 여러번의 오답을 누적했네요..ㅠㅠ 모든 원소가 음이 아닌 정수이기 때문에 "$a_1,\cdots,a_{i-1}$로 구성할 수 있는 모든 합"을 $\{s\}$에서 반복적으로 덜어내면 됩니다. 모두 덜어내졌다면 $\{s\}$에 남은 가장 작은 값은 $a_i$가 됩니다.이로써 새로운 원소를 추론하였기에, 다시 "$a_1,\cdots,a_{i}$로 구성할 수 있는 모든 합"을 모두 덜어내면 다음 과정으로 진행할 수 있습니다.#include using namespace std;m..

code-challenge.elice.io 엘리스 코드 챌린지 Day 4에는 '트리 위의 게임'이라는 문제가 나왔습니다.Day 3처럼, 알고리즘 문제를 평소에 풀어보지 않은 사람들에게는 다소 어려울 수 있는 난이도로 나왔습니다. 저는 오늘부터 알람을 10시에 맞춰두고 풀기로 했습니다. $\mathrm{dfs}(s,\cdot)$이 $s$에서 게임을 시작했을 때 얻을 수 있는 점수라고 정의합시다. 게임에서 가능한 수들이 공개되어 있고, 사람에 따라 가능한 게임 속 시행에 차별이 없다면 보통, 게임은 사이클이 없는 방향 그래프(DAG; directed acyclic graph)로 모델링 되며, 각 게임의 상태는 정점 하나로 표현되고 정점은 승리 또는 패배의 상태를 갖게 됩니다. 어떤 상태에서 진행할 수 있는 ..

code-challenge.elice.io 엘리스 코드 챌린지 Day 3에는 '문자열 압축 해제'라는 문제가 나왔습니다.Day 1, 2에 비해 갑자기 어려워져서 놀랐습니다. 괄호가 포함된 문자열을 해석할 때는 스택(stack) 자료구조와 재귀적인 접근을 이용하는 것이 좋습니다. 문제를 풀기 전, 괄호 문자열에 대해 여는 괄호는 닫는 괄호 짝의 인덱스를, 닫는 괄호는 여는 괄호 짝의 인덱스를 빠르게 찾을 수 있도록 스택을 이용하여 opened[N], closed[N] 배열에 기록해둡시다. 문제를 해결하기 위해 문자열 $S$에 대해 $\mathrm{solve}(S)$를 정의합시다.이때, 문자열 $S$는:첫 번째 문자가 숫자여야 하고,괄호로 이루어진 부분수열(subsequence)이 올바른 괄호 문자열을 이룬..

code-challenge.elice.io 엘리스 코드 챌린지 Day 2에는 '정리 정돈을 좋아하는 k씨'라는 문제가 나왔습니다. 저는 다음과 같이 copy, sort 함수를 이용하여 단순하게 코드를 작성했습니다.#include using namespace std;const int N = 10003, M = 503;int n, m;int a[N], b[N];int main() { cin >> n >> m; for(int i=1; i> a[i]; while(m--) { int i, j, k; cin >> i >> j >> k; copy(a+i,a+j+1,b+i); sort(b+i,b+j+1); cout

code-challenge.elice.io 엘리스 코드 챌린지 Day 1에는 '목표량'이라는 문제가 나왔습니다. 저는 다음과 같이 next_permutation 함수를 이용하여 풀었습니다.이 함수는 배열, vector, string 등의 first, last iterator를 받아서 사전순으로 바로 다음인 순열을 만들어줍니다. 만약 그런 순열이 존재하지 않을 경우 0을 리턴합니다.따라서 이 함수를 알고 있으면 본 문제를 보다 쉽게 구현할 수 있습니다.#include using namespace std;int main() { string N; cin >> N; next_permutation(begin(N), end(N)); cout

7월 5일 15시 ~ 7월 6일 15시 동안 진행되었다. 대학생이 된 후 처음으로 치르는 메이저 대회였다. 현대모비스는 PS 폼이 별로인 시점에 2년연속티켓페널티를 물기 싫음 + 마침 더 재밌는 일정 + 기출 안 풂 (대회를 대비하는 과정에서 해당 대회에 대한 애정이 생기는 편) 의 사유로, 예선만 대충 치렀다. 팀원들은 대회 가서 괴물같은 모습들을 뽐내고 온 듯 하다... ㅊㅊ Screencast를 youtube에 올렸다. https://youtu.be/VuXg1AEQsXo 문제들에 대한 감상은, 내 기준으로 딱 1 라운드 용으로 재밌게 몸풀기 할 수 있는 난이도였다고 생각한다. 무엇보다 지문이 두세줄로 끝나는 것이 너무 좋았다. GOAT 간략하게 풀이를 적자면,A보다 B가 좋아: A와 A 사이에는 최..

일주일에 다이아를 다섯 문제씩 풀겠다는 다짐을 했다.이 다짐을 어느 정도 지켰다. 마지막 주는 두 문제 밖에 풀지 못해서 아쉽지만, 6월 첫째주는 다시 6문제를 풀면서 달리고 있다. 현재 해결한 다이아는 98문제이다. 다이아 문제 짬을 좀 늘려보겠다는 생각으로 시작했는데, 금방 100문제에 다다라서 기분이 좋다.더불어, 플래티넘 5~3은 각각 95문제 이상 해결한 것으로 보인다. 일단, 5월 동안 해결한 다이아 문제들을 나열해 보겠다.13514번: 트리와 쿼리 513546번: 수열과 쿼리 413545번: 수열과 쿼리 014504번: 수열과 쿼리 1817410번: 수열과 쿼리 1.519525번: Rectangle-free Grid31055번: A Graph Problem23798번: 올바른 괄호 문자열13..

안녕하세요. 블로그 운영자 김도훈입니다. "알고리즘 과외 합니다"여는 말"알고리즘 과외? 그런 것도 있어?"보통 알고리즘 과외 얘기를 꺼내면 반응은 이렇습니다.사람들에게 알고리즘 과외가 생소한 것은 사실입니다. 어쩌면, 알고리즘 공부가 현재처럼 대중적으로 자리잡은 것은 오래되지 않았기에 생소한 것이 오히려 당연할 수도 있습니다.알고리즘 문제를 푸는 과정은 꽤 길고 복잡합니다. 또한 숙련된 사람이라도 주기적으로 난관을 부딪힐 수 밖에 없는 분야입니다. 따라서 난관에 부딪혔을 때 가능한 한 빠르게 헤쳐나오고, 다음 단계를 향해 나아가도록 도와주는 멘토가 있다면 성장의 속도는 확연히 높아질 수 밖에 없습니다.만약 본인의 성장이 더뎌지고 있으며, 꾸준히 이끌어주는 멘토가 있었으면 좋겠다는 마음이 있다면 과외가 ..