2017/06 썸네일형 리스트형 뒤늦은 제 3회 IUPC(인하대학교 프로그래밍 경진대회) 후기 및 간략한 풀이 IUPC가 5월 27일에 끝나게 되었다. 제 2회 IUPC때는 DP조차 모르는 상태로 참가해서 15등하고 좋아했었는데 1년이 지나 어느새 문제까지 내고 있게 되었다. (자격 미달이지만 ㅜㅜ) 개인적으로 내가 출제한 문제들이 디스크립션이 굉장히 후져서 참가자들에게 너무나도 미안했다.. CTP가 대상을 뺐긴것도 속상했고 ㅜㅜ 뭐 이외에도 문제 검수를 완벽하게 하지 못하여 디스크립션을 도중에 바꾸는 등 .. 탈많은 대회였지만 그래도 동아리 부회장을 맡으면서 처음으로 제대로 된 무언가를 진행했다는데 의미를 두기로 했다. 뭐 .. 이건 대회 운영 및 문제 출제를 하면서 느낀 개인적인 감상이고 대회에 대해서 얘기를 해보자면 우선 제 1,2회 IUPC가 33~38정도의 팀이 참가를 하여 진행해서 이번에는 40팀 정도.. 더보기 BOJ)12995 트리나라 문제: icpc.me/12995 트리가 주어질 때 노드가 K개인 서브트리의 개수를 구하는 문제이다. 트리DP임을 인지하고 dp[pos][state] = tr[pos].size()) return state == 1 ? 1 : 0; ll &ret = dp[pos][idx][state]; if (ret != -1)return ret; ret = 0; for (int i = 0; i 더보기 BOJ)1405 미친 로봇 문제: icpc.me/1405 각 방향으로 이동할 확률과 이동 횟수가 주어질 때 경로가 단순할 확률을 구하는 문제이다. dfs를 통한 4방향 탐색으로 각 방향으로 이동할 확률을 곱해서 brute force 해주면 된다. 1234567891011121314151617181920212223242526272829#include #include using namespace std;int n, visited[30][30];double p[4];int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };double dfs(int x, int y, int cnt) { if (cnt == 0)return 1.0; double ret = 0.0; visited[x][y] = true; for .. 더보기 BOJ)10838 트리 문제: icpc.me/10838 트리에서 세가지 쿼리를 처리하는 문제이다. 1번 쿼리나 3번 쿼리에서 물어보는 질의를 답하기 위해서는 a와 b의 lca를 필수적으로 구해야한다. 고정된 트리에서 LCA는 전처리를 거친후에 logN의 시간에 구할 수 있지만 2번 쿼리가 트리의 구조를 바꿔버리기 때문에 힘들어질 뿐더러 1번, 3번 쿼리를 처리하기 위해 LCA를 구했다고 하더라도 색칠을하거나 색의 개수를 세려면 log시간에 처리하긴 힘들어보인다. 하지만 문제를 잘 읽어보면 paint와 count 연산 시 a번 노드와 b번 노드 사이의 최단경로의 길이는 항상 1,000 이하이다. 라는 조건을 찾을 수 있다. 이를 이용하여 LCA나 쿼리를 O(1000)의 시간에 해결해주면 문제를 해결할 수 있다. 123456789.. 더보기 BOJ)14590 KUBC League (Small) 문제: icpc.me/14590 외판원 문제(TSP)와 유사한 문제이다. 외판원 문제는 비트마스크 DP로 해결할 수 있다. dp[state][pos] 더보기 BOJ)13538 XOR 쿼리 문제: icpc.me/13538 5가지 종류의 쿼리를 처리하는 문제이다. 1번 쿼리를 x의 위치에 업데이트 시키는 새로운 세그먼트 트리를 생성한다고 가정하면 persistent segment tree 자료구조를 이용할 수 있다. 고로 1번 쿼리의 경우 트리의 개수 n을 증가시켜주면서 n번째 세그먼트 트리의 x의 위치에 업데이트 시켜준다. 이 방식으로 persistent segment tree를 구축시켜주면 3번 쿼리는 자연스럽게 n=n-k가 된다. 이제 2,4,5의 쿼리를 생각해보자 4번 쿼리의 경우 r번째 세그먼트 트리에서의 0~x의 sum에서 l-1번째 세그먼트 트리에서의 0~x의 sum을 빼줌으로서 처리가능하다. 5번 쿼리의 경우는 r번째 세그먼트 트리가 가지는 값에서 l-1번째 세그먼트 트리가 가.. 더보기 Persistent Segment Tree 먼저 시작하기 전에 .. -오늘 공부한 내용을 제 멍청한 머리가 기억하지 못할까봐 기록하는 개인용 글입니다. -해당 자료구조에 대하여 완벽하게 알고 적는 글이 아니기 때문에 Persistent segment tree를 공부하는 용도로는 좋지 못한 글이 될 확률이 높습니다.-BOJ 11932 문제를 풀기 위해 https://hongjun7.tistory.com/m/64와 http://blog.myungwoo.kr/100 를 많은 부분에서 참고하였습니다. persistent segment tree가 뭔지는 알고있었지만 귀찮아서 공부를 미루다가 오늘 BOJ 11932번을 접하고 도전하게 되었다. persistent segment tree는 가상의 N개의 세그먼트 트리를 O(NlogN)의 공간복잡도로 유지하는 .. 더보기 BOJ)1322 X와K 문제: icpc.me/1322 X가 정해져 있을 때 X+Y = X | Y 를 만족하는 Y는 2진수에서의 연산을 생각한다면 X가 0인 비트에만 1이 채워져있는 수일 것이다. 고로 K번째로 큰 Y를 찾는다면 K를 이진수로 표현하였을 때 1이 채워진 순서를 X에서 0인 부분에 순서대로 채운 수가 된다. 이는 투 포인터로 구해줄 수 있다. 12345678910111213141516#include #include using namespace std;typedef long long ll;ll x, y, k;int main() { scanf("%lld%lld", &x, &k); for (int i = 0, j = 0; j 더보기 BOJ)1837 암호제작 문제: icpc.me/1837 P가 너무 크기 때문에 K를 이용하여 답을 구해내야 한다. 우선 K이하의 소수를 에라토스테네스의 체를 이용하여 구해준 뒤 P가 해당 소수들 중 하나라도 나누어 떨어지는 수가 있다면 BAD를 출력하게 된다. 12345678910111213141516171819202122232425262728293031#include #include using namespace std;char a[110];int k, p[2000000];bool chk(const char *s, int p) { int ret = 0; for (int i = 0; s[i]; i++) ret = (ret * 10 + s[i] - '0') % p; return !ret ? true : false;}int main(.. 더보기 BOJ)14577 일기예보 문제:icpc.me/14577 4가지 종류의 질의가 들어오는 문제이다. 지역 수 가 N 질의의 수가 M일 때 N,M이 10만까지 들어오므로 적어도 질의 하나당 log 시간에 해결해줘야 한다. 결국 3,4번 질의를 로그시간에 답해줘야 하는데 구간에 대한 질의이므로 우선 세그먼트 트리를 생각해낼 수 있다. 하지만 좌표 자체에 업데이트를 할 경우 좌표의 범위부터가 감당이 안된다. 그렇기 때문에 우리는 한 지역에 쌓일 수 있는 눈의 양에 업데이트를 해야한다. 나올 수 있는 눈의 양은 3번 쿼리의 경우 2개 1,2번 쿼리의 경우 1개 일 뿐이니 최대 2*M개 뿐이기 때문이다. 말을 어렵게 표현했는데 우선 쿼리를 오프라인으로 처리할거다. 모든 쿼리를 받은 뒤에 해당 질의 때 마다 나올 수 있는 모든 눈의 양을 저장.. 더보기 이전 1 2 3 4 5 다음