본문 바로가기

분류 전체보기

BOJ)1626 두 번째로 작은 스패닝 트리 문제: icpc.me/1626 두 번째로 작은 스패닝 트리를 구하는 문제이다. 우선 정점이 V개 간선이 E개인 그래프에서 MST를 구해준다. 그리고 MST를 구성할 때 사용하지 않은 E-V+1개의 간선에 대해서 해당 간선을 포함하는 MST를 구하여 답을 구해낸다.. 하지만 E-V+1번 크루스칼을 돌린다면 TLE를 보게 될것이다. 그렇다면 E-V+1개의 간선을 각각 포함하는 MST를 어떻게 구해낼 수 있을까? 우선 현재 보고 있는 간선이 1번 정점과 5번 정점을 연결한다고 가정해보자. 그렇다면 우리는 기존의 MST에서 1번 정점과 5번 정점을 연결해주어 N개의 간선을 가진 그래프를 생각해보자. 해당 그래프를 트리로 만드려면 하나의 간선을 제거해야한다. 이 때 제거되야 되는 간선은 1번 정점과 5번 정점을 .. 더보기
1500? 꿀문제로만 채워넣어서 영양가는 좀 떨어지지만 기쁘다 더보기
BOJ)10881 프로도의 선물 포장 문제: icpc.me/10881 세개의 상자를 하나의 큰 포장상자안에 넣어야 할 때 준비해야하는 포장상자의 최소 넓이를 구하는 문제이다. 우선 상자가 세개밖에 주어지지 않기 때문에 완전탐색을 생각해볼 수 있다. 세개의 상자를 배치하는 모양은 회전에 따라서 달라지지 않는 경우는 1열로 3상자를 배치하는 케이스와 2상자 위에 1 상자를 쌓아놓는 모양 두가지 밖에 없다. 때문에 주어진 조건으로 위의 경우에 해당 하는 모든 경우를 탐색하면 하나의 쿼리를 2*6^3의 시간만에 처리할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637#include #include using namespace std;pair a[6];int three(i.. 더보기
BOJ)11689 GCD(n,k) = 1 문제:icpc.me/11689 1~n까지의 수중에서 n과 서로소인 수를 구하는 문제이다. 소인수분해를 sqrt(n) 시간에 해결해준 뒤 포함-배제의 원리를 이용하여 서로소의 개수를 세주면된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include #include #include using namespace std;typedef long long ll;ll n;struct ele{ ll num, pos, state; ele(ll num, ll pos, ll state) :num(num), pos(pos), state(state) {}};vector .. 더보기
BOJ)2503 숫자 야구 문제:icpc.me/2503 각 자리의 숫자를 임의로 설정해 준 뒤 매 쿼리를 비교해주는 계산을 하더라도 O(1000*N)의 시간밖에 걸리지 않기 때문에 완전 탐색을 해주어 통과되는 숫자의 수를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include using namespace std;int n, r;struct query { int num, strike, ball; query(int num, int strike, int ball) :num(num), strike(strike), ball(ball) {} query() {} int getfirst().. 더보기
BOJ)1799 비숍 문제: icpc.me/1799 한 지점에 비숍이 세워진다면 그 지점을 통과하는 두개의 대각선에 있는 모든 지점에는 비숍이 세워질 수 없다. 이를 이용하여 왼쪽 아래로 향하는 대각선과 오른쪽 아래로 향하는 대각선을 가르는 정점들에게 각각 대각선의 번호를 매겨준 뒤 두 대각선으로 이루어진 이분 그래프에서의 최대 매칭을 구하는 문제로 변형시켜서 해결할 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include #include #include #includ.. 더보기
BOJ)7154 Job Postings 문제: icpc.me/7154 학생들이 원하는 일들과 일들의 개수 등이 주어질 때 학생들의 전체 만족도의 합의 최댓값을 구하는 문제이다. 학생들이 일을 선택하는 것을 학생과 일을 1:1로 매칭한다고 생각한다면 MCMF 문제로 만족도를 구할 수 있다. 모델링은 소스-> 일 -> 학생 -> 싱크로 구성해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798#include #include #include #include .. 더보기
뒤늦은 제 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 .. 더보기

티스토리툴바