본문 바로가기

알고리즘 관련/BOJ

BOJ)1890 점프 문제: icpc.me/1890 규칙에 맞게 갈 수 있는 경로가 주어질 때 오른쪽 맨 아래로 가는 경우의 수를 계산해주는 문제이다. 우리는 dp[x][y] = 0,0에서 x,y로 가는 경우의 수로 테이블을 잡아 준 뒤 x,y에서 나보다 x좌표나 y좌표가 작은 지역중 나에게로 올 수 있는 경우의 수를 더해줘서 n^3 다이나믹 프로그래밍으로 구해줄 수 있다. 1234567891011121314151617181920212223242526272829#include #include #include using namespace std;typedef long long ll;ll n, dp[101][101], a[101][101];ll func(int x, int y) { if (x == y&&y == 0)return .. 더보기
BOJ)2916 자와 각도기 문제:icpc.me/2916 만들 수 있는 각도들이 주어질 때 그 각도들을 더하거나 빼서 만들 수 있는 모든 각도를 구하는 문제이다. 다이나믹 프로그래밍을 통하여 dp[pos][val] = pos번째 각도 까지 이용하여 구할 수 있는 val(각도)로 구해주면 된다. 123456789101112131415161718192021222324252627#include #include using namespace std;int n, k;int a[11], dp[361][11], q[11], r[361];void func(int val, int pos) { if (pos == n)return; if (dp[val][pos])return; dp[val][pos] = true; r[val] = true; int nex.. 더보기
BOJ)3049 다각형의 대각선 문제: icpc.me/3049 볼록 다각형에서의 대각선들의 교점을 구하는 문제이다. 볼록 다각형에서는 겹치는 교점은 존재하지 않으므로 교점이 생성 될 수 있는 경우인 다각형의 꼭지점이 4개일 때의 경우를 세주면 된다. 즉 nC4를 출력해주면 된다. 123456789#include #include using namespace std;int n;int main() { scanf("%d", &n); printf("%d\n", (n*(n - 1)*(n - 2)*(n - 3)) / 24); return 0;}Colored by Color Scriptercs 더보기
BOJ)9577 토렌트 문제: icpc.me/9577 시간마다 시드를 하나씩 받을 수 있고 각 시간에 시드를 받을 수 있는 사람과 각 사람이 받을 수 있는 시드의 종류가 주어졌을 때 시드를 전부 다운 받는 최소 시간을 출력하는 문제이다. 우리는 시간에 대한 정점과 시드에 대한 정점으로 나누어 이분 그래프를 형성해 준 다음 이분 매칭을 시도하는데 시간 정점중 t번째 정점까지 매칭 했을 때 최대매칭이 시드의 수와 일치할 경우 t초가 최단시간이 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include #include #include using namespace std;in.. 더보기
BOJ)5430 AC 문제: icpc.me/5430 정수 배열이 주어질 때 두 종류의 쿼리를 받는다 하나는 배열 전체를 뒤집는것이고 하나는 배열의 앞에서 숫자를 버리는것이다. 쿼리의 수 length(p)와 배열의 수 n이 전부 10만이므로 쿼리를 받을 때마다 배열 전체를 직접 뒤집는다면 O(T*(length(p)*n))의 시간복잡도로 시간초과를 받을 것이다. 우리는 자료구조 deque를 통하여 R 쿼리가 들어올 때 뒤집혔다는 표시만 해준 뒤 D의 경우 앞 뒤로 뽑을 지 결정해주면 된다. 출력할때도 마찬가지로 뒤집혔는지 여부를 판단하여 앞혹은 뒤에서부터 출력해주면 된다. 이렇게 구현할 경우 시간 복잡도는 O(T*(N+P))으로 초과되지 않겠지만 시간초과를 받아서 멘붕했었는데 p의 길이를 구할 때 strlen을 써서 TLE를 받.. 더보기
BOJ)1966 프린터 큐 문제: icpc.me/1966 큐에서 priority가 가장 높지 않으면 뽑은 뒤 맨 뒤로 보낼 때 m번째 수는 몇번째로 뽑히는지 출력하는 문제이다. N이 100밖에 되지 않으므로 N^2 시뮬레이션을 돌려주면 된다. 들어오는 모든 수를 priority queue 와 queue에 넣어준 후 pq의 top과 queue의 front값이 같을 때만 값을 뽑아주면 된다. 1234567891011121314151617181920212223242526272829303132#include #include #include using namespace std;int t, n, m, x, r;int main() { scanf("%d", &t); while (t--) { r = 0; queue qu; priority_queu.. 더보기
BOJ)6064 카잉 달력 문제: icpc.me/6064 n년도를 x:y로 표현할 때 n+1년도는 if(x==m) x=1 else x=x+1 if(y==n) y=1 else y=y+1 로 표현할 때 x:y가 몇년도인지 찾는 문제이다. 처음에 단순하게 시뮬레이션을 돌려봤으나 시간초과를 받아서 문제를 다시 보니 M과 N이 40000씩이므로 O(N*M)의 시뮬레이션으로는 해결할 수 없는 문제였다. 그래서 수식을 사용하여 for(int i=0;i 더보기
BOJ)2787 흔한 수열 문제 문제: icpc.me/2787 구간에 대한 최댓값과 최솟값이 주어질 때 valid한 수열을 만들 수 있는지 여부를 조사하고 가능할 경우 수열을 출력하는 문제이다. 우리는 구간에 대한 최댓값과 최솟값의 정보를 가지고 i번 위치에 올 수없는 값들을 전부 check해준 뒤 쿼리 입력이 끝나면 i번 위치에 올 수 있는 모든 값들을 연결하여 이분매칭을 시켜주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include #define MAX_N 200using namespace std;ve.. 더보기
BOJ)2191 들쥐의 탈출 문제: icpc.me/2191 땅굴에는 한 들쥐만 들어갈 수 있고 s초가 되기 전에 들쥐가 땅굴에 도착하게 되면 잡아먹히지 않을 때 잡아먹히게 되는 들쥐의 최솟값을 출력하는 문제이다. 잡아먹히는 들쥐의 최솟값은 즉 땅굴에 도착하는 들쥐의 최댓값의 여집합이므로 들쥐가 도달할 수 있는 땅굴에 대하여 간선을 연결하여 땅굴/들쥐의 이분 그래프를 형성한 뒤 최대매칭을 구하여 총 들쥐의 수에서 빼주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #include #include #define MAX_N 100using namespace std;double get.. 더보기
BOJ)9169 나는 9999번 문제를 풀 수 있다 문제:icpc.me/9169 풀 수있다고 생각한 사람과 풀 수 없다고 생각한 사람의 생각이 주어지고 사람들의 친구 관계가 주어지는데 이 때 생각을 바꾸거나 친구사이에 투표한 결과가 서로 다른 관계의 수의 합의 최솟값을 구하는 문제이다. 우리는 풀 수 있다고 생각한 사람을 소스에 연결하고 풀 수 없다고 생각한 사람을 싱크에 연결 한 뒤 서로 다른 경우에 간선을 한 방향으로 같은 경우에 양방향으로 연결해줌으로서 그래프를 모델링 해준 뒤 cut의 개수를 구하면 어긋나는(생각이 다른) 경우의 개수이므로 min cut을 구해주면 된다. mincut은 Maxflow-Mincut Theorem에 의하여 maximum flow를 구해줌으로서 해결 된다. 123456789101112131415161718192021222.. 더보기

티스토리툴바