본문 바로가기

알고리즘 관련/BOJ

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번 정점을 .. 더보기
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 .. 더보기
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] 더보기

티스토리툴바