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 사이에는 최..
코드마스터 2023 이후로 세 문제를 출제하였다. 때는 작년 여름 방학. 정시로 늦은 탑승을 하는 것은 승산이 적다고 판단했던 시기. 특기자에 한 줄이라도 더 적을 거 만들자는 생각으로 (사실 함수컵 검수하다가 뽐뿌가 와서.. 그냥 출제가 하고 싶었다) 문제 구상을 시작했다. Sieve Game, 고양이 리그, 신촌방위본부: 지하 벙커의 비밀, 요 세 문제가 그 때 만들어졌다. 당시에 한 일주일간 한적한 카페에 가서 이것저것 생각나는대로 만들어보다가 집에 오는 걸 반복했다. 신촌방위본부: 지하 벙커의 비밀은 SNUPC Call for Tasks에 던졌다가 반려되었고, 이번 SUAPC 2024w Call for Tasks에서 간택되었다. 선발고사 & 함수컵에 출제된 투스텝을 보고 투스텝에 대한 관심이 많이..
unordered_map의 템플릿 인자에 직접 정의한 해시 함수를 넣어서 [핵 피하기] or [원하는 자료형을 key로 사용하기] 를 할 수 있습니다. key의 자료형을 바꾸자 20940번: Pingvin 문제를 깔끔하게 풀고 싶은 마음에 이상한 짓을 했습니다. 다음 코드는 Pingvin 문제에서 456ms로 AC를 받은 코드입니다. 상수 최적화 없이는 TLE가 나기 쉬우므로 주의하세요. 더보기 #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include #define rep(i,a,b) for (auto i = (a); i n; rep(i,0,2) cin >> S[i]; rep(i..
매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다. 완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요. Suffix array 기본 문제 몇 개랑 상어의 저녁식사 풀었습니다. 딱히 어려운 부분은 없었습니다. Prefix와 Suffix 링크 일단 해싱으로 pfx=sfx들을 효율적으로 구할 수 있고, 이것들이 몇 번 등장하는지를 suffix array를 갖고 구할 수 있지 않을까 하는 생각이 듭니다. LCP 배열에서 RMQ를 돌리면..! 어떤 패턴이 몇 번 등장하는지를 손쉽게 확인할 수 있겠다는 신선한 생각이 들었습니다. 해보겠습니다..! 구현량에 걸맞지 않게 한 번에 예제가 나왔습니다. 제..
