목록분류 전체보기 (26)
LoCeL
2022 ICPC Seoul Regional에 GreenBelt팀으로 출전하였다. 전체 12문제중 5문제를 해결하고 프리즈 기준 39위, 최종 43위를 달성했다. 피곤해서 좋은 글이 써지지 않는 것 같지만, 기억이 휘발되기 전에 대회 중에 있었던 일을 시간 순으로 복기해보고자 한다. 대회 시작 전에 풍선이 앞에 놓여있길래, 풍선의 개수를 세어서 난이도를 예측하려고 했다. 후에 들은 이야기로는 풍선 개수를 일부러 맞춰놓았다고 한다(...) 그냥 플라시보였음. J. Parentheses Tree (AC at 10 min) 사실 그림이랑 예제입력보고 쫄았는데 문제를 읽자마자 별거 아니라는걸 깨달았다. 구현에는 그렇게 많은 시간이 걸리지 않았는데 10분에 AC를 받은 이유는, 키보드를 교체하고 자리까지 바꿨기 ..
우리는 살아가면서 수많은 문제를 마주하게 되고, 수많은 해법으로 문제들을 해결하게 됩니다. 모든 사람들은 그 종류에 관계없이, 문제를 해결하며 살아가고, 이왕이면 문제를 잘 해결하는 사람이 되고 싶습니다. 오늘 할 이야기는 알고리즘 문제 해결을 중심으로, 어떻게 생각하고 공부해야 문제를 잘 해결할 수 있는지, 최근 문제의 풀이법과 공부법을 바꾸면서 제가 느낀 것을 써 내려가 보고자 합니다. 물론 누군가에게는 아주 당연한 이야기가 될 수도 있고, 값진 이야기가 될 수도 있을 것 같습니다. 요즘 컴퓨터공학을 공부하는 사람이라면, 또는 그 분야의 직업을 갖고 싶은 사람이라면 알고리즘 문제 해결(이하 Problem Solving의 준말인 PS라 칭합니다)을 한 번쯤은 들어보거나, 경험해보았을 것입니다. 처음 공..
더보기 BOJ 10767 Palindromic Paths N by N 크기의 격자판의 각 칸에 알파벳이 쓰여있고, (0, 0)에서 부터 (N-1, N-1)까지 오른쪽 또는 아래 칸으로만 이동하여 가는 모든 경로에 대해, 지나온 알파벳을 순서대로 놓은 문자열들 중 서로 다른 팰린드롬의 개수를 구하는 문제. $2 \leq N 18$ 이라는 조건이 있어서, 브루트포스로 해결되겠구나 하는 느낌을 받았다. 그러나 모든 경로를 보려면 총 $2^35$ 만큼의 경로를 봐야하므로, 시간내에 해결할 수 없다. 팰린드롬의 길이는 항상 $2N-1$로 나오므로, 시작점에서 출발하여 길이 N의 prefix, 끝점에서 출발하여 길이 N의 surfix를 만들고, 두 prefix와 surfix가 같은 경우를 세어주면 된다. MITM이..
보호되어 있는 글입니다.
2021년 11월 27일 토요일 오후 1시부터 5시까지 4시간동안 제 3회 유니스트 알고리즘 프로그래밍 대회인 Uni-CODE 2021이 개최되었다. 출제, 검수진으로는 leejseo, queued_q, wbjeon2k, jh05013, koosaga, cs71107, junie 그리고 내가 참여했다. 문제는 여기에서 확인할 수 있다. 총평 우선 올해는 모든 문제를 영어로 출제하였다. 문제를 번역하는 과정이 제일 힘들었던 것 같다... 난이도는 예상보다 어려웠다. 그럼에도 참가자들이 모두 문제를 잘 풀어서, H를 제외한 모든 문제가 대회 중에 해결되었다. 문제 해결 분포도 꽤나 마음에 들었고, 당일 노쇼를 제외한 모든 참가자들이 적어도 1문제는 해결하였다. 다만, 작년에 비해 신청자 대비 참가율이 너무 ..
문제 가장 긴 증가하고 연속하는 부분 수열을 찾으면, N - (수열의 길이) 가 답이 된다. 가장 긴 증가하고 연속하는 부분 수열은, A[i] 앞에 A[i]-1이 있었는지를 간단히 판별하여 DP 테이블을 채울 수 있다. #include using namespace std; using ll = long long; int N; int A[1000005], B[1000005], cnt[1000005]; int D[1000005]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N; for (int i = 1; i > A[i]; B[A[i]] = i; D[i] = 1; } for (int i = 1; i
처음 참가해본 Div.3 라운드이다. 총 7문제 중에서, A, B, C, D, F1 5문제를 해결했다. 꽤나 괜찮은 성적을 받아서, 그레이까지 곤두박질 쳤던 레이팅을 그린으로 끌어올렸다. 열심히 치면 민트는 물론이고 블루까지 금방 올릴 수 있지 않을까 A. Dislike of Threes 3의 배수거나, 일의 자리숫자가 3이 아닌 숫자를 모았을 때, k번째로 큰 수를 출력하는 문제였다. 넉넉하게 3000 이하의 수 중에서 조건을 만족하는 수들만 미리 계산하여 정렬한 후에, k번째를 매번 출력하면 되는 간단만 문제였다. B. Who's Opposite? 원 위에 n명의 사람들이 일정한 간격으로 둘러서있고, 마주보는 두 사람의 번호 a, b가 주어져있을 때, 사람 c와 마주보는 사람의 번호를 구하고, 구할 ..
문제 2759번: 팬케익 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 숫자 여러개가 공백으로 구분되어있다. 첫 번째 숫자는 팬케익의 개수 N이고, 그 다음 N개의 숫자는 팬케익의 크기이다. 가장 www.acmicpc.net 꽤 재미있는 문제였다. 문제에서 명시해둔 최대로 뒤집을 수 있는 횟수인 $2n-3$이 핵심이다. 팬케익의 숫자는 $1$부터 $n$까지 있다. 당연하게도, 정렬되어있을때, 크기 $i$인 팬케익은 $i$번째 위치에 있을 것이다. 크기 $i$인 팬케익을 $i$번째 위치로 보내는 가장 나이브한 풀이를 생각해보자. 크기 $i$인 팬케익의 위치를 $p$라고 하자. $p$위치에서 팬케익을 뒤집는다. 이때 크기 $i$인 팬케익은 첫번째 위치로 갈 것이다. 그리고 $i$..
올해 11월 28일 오후 1시부터 3시간 동안, Uni-CODE 2020이 개최되었습니다. 총 참가인원 82명으로, 10~20명 남짓이었던 1회 대회와는 비교하여 크게 불어난 규모였습니다. 그로 인해서 생겼던 예상하지 못했던 상황도 많이 있었는데, 운영에서 작년과 달라진 경험들을 정리해보고자 합니다. 대회 준비의 시작 사실 올해는 대회를 열 생각이 없었습니다. 작년에 대회 운영을 하면서 대회 운영이 쉽지 않다는 것을 느끼기도 했고, 연구실 인턴으로 바빠서 시간이 없을 것이라고 생각했으며, 무엇보다 COVID-19의 유행으로 작년보다 참여율이 훨씬 저조할 것이라 판단하였기 때문입니다. 작년 신청자수가 20명이 안되었던 것을 생각하면, 이것보다 적은 인원이 대회에 참여해봐야 대회를 개최하는 의미가 없다고 판..
문제는 여기에서 확인할 수 있다. 간단하고 유명한 knapsack문제이다. D[k][n]을 n번째 물건까지 보고, 배낭의 무게가 k일 때, 배낭의 물건의 가치의 합의 최대라고 놓으면 점화식은 D[k][n] = max(D[k-u[i]][i+1] + e[i])이다. (u는 물건의 무게, e는 가치) 1234567891011121314151617181920212223242526272829303132#include using namespace std; typedef long long int lld; lld s, n, u[105], e[105];lld d[100001][105]; lld solve(int cap, int i) { if(i == n) return 0; lld &ret = d[cap][i]; if(r..