본문 바로가기

알고리즘 관련

BOJ)14503 로봇 청소기 문제: icpc.me/14503 주어진 조건대로 로봇을 작동시킬 때 청소를 몇칸까지 할 수 있는지 판단하는 문제이다. 청소한 빈칸을 2 청소안한 빈칸을 0 벽을 1으로 설정한 뒤 시키는대로 시뮬레이션을 돌려주면 된다.12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include using namespace std;int n, m, a[51][51], x, y, h, r;int dx[] = { 0,-1,0,1 };int dy[] = { -1,0,1,0 };int main() { scanf("%d%d", &n, &m); scanf("%d%d%d", &x, &y, &h); for (int i = 0; i 더보기
BOJ)14500 테트로미노 문제:icpc.me/14500 주어진 문제의 답은 모든 경우에 테트로미노를 다 대봄으로서 구할 수 있다. 주어지는 테트로미노의 5가지 모양중 ㅜ 모양을 제외한 4가지 모양은 DFS를 통하여 탐색이 가능하고 ㅜ모양만 따로 처리를 해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include using namespace std;int n, m, a[501][501], v[501][501], r;int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };bool chk(int x, int y) { r.. 더보기
BOJ)14501 퇴사 문제: icpc.me/14501 i일 부터 일을 할 때 얻을 수 있는 급여의 최댓값으로 DP테이블을 잡으면 쉽게 계산할 수 있는 문제이다. dp[i]의 점화식은 max(dp[i+1],dp[i+t[i])+p[i]) 가 된다. 1234567891011121314151617181920#include #include #include using namespace std;int n, dp[16], t[16], p[16];int func(int pos) { if (pos == n + 1)return 0; if (pos > n + 1)return -987654321; int &ret = dp[pos]; if (ret != -1)return ret; return ret = max(func(pos + 1), func(po.. 더보기
BOJ)14502 연구소 문제: icpc.me/14502 N,M의 범위가 매우 적기 때문에 나올 수 있는 경우를 전부 확인해줄 수 있다. 6중 포문을 통하여 모든 경우에 벽을 세워본 후 dfs를 통하여 바이러스가 얼마나 퍼질 수 있는지 조사하여 그 최솟값을 전체 크기에서 벽을 제외한 값에서 빼주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include #include #include using namespace std;int n, m, a[9][9], r, visited[9][9], b;int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,.. 더보기
BOJ)3079 입국심사 문제: icpc.me/3079 X시간 동안 심사할 수 있는 인원 수는 Sum(i: 0~N) X/T[i] 로 정의할 수 있다. 이를 이용하여 파라메트릭 서치로 답을 구해주면 된다. 123456789101112131415161718192021222324#include #include typedef long long ll;using namespace std;ll n, m, a[100001];int main() { scanf("%lld%lld", &n, &m); for (int i = 0; i 1; ll cnt = 0; for (int i = 0; i = m) hi = mid; else lo = mid + 1; } printf("%lld\n", lo); return 0;}cs 더보기
BOJ)2820 자동차 공장 문제: icpc.me/2820 문제를 잘 읽어보면 1번을 루트로 가지는 트리 구조를 이룬다는걸 알 수 있다. 그럼 상사 X의 부하들은 어떻게 구분할 수 있을까? 트리 구조이기 때문에 X에서 Y로 가는 경로는 오직 하나일 것이다. 이걸 이용하여 X지점에서 시작한 DFS가 끝날 때 까지 탐색되는 모든 노드들은 X의 부하라는걸 알 수 있다. 이를 이용하여 1번 노드에서부터 DFS를 돌려 정점의 번호를 새롭게 매겨준 후 DFS가 끝나는 지점(마지막 부하)의 번호까지 알게 된다면 직원에 대한 증가연산을 구간에 대한 증가 연산으로 치환시킬 수 있다, 구간에 대한 증가 연산으로 치환을 했으니 레이지 프로퍼게이션을 이용한 세그먼트 트리나 ,펜윅 트리 등을 이용하여 쿼리를 처리해주면 된다. 1234567891011121.. 더보기
BOJ)7573 고기잡이 문제: icpc.me/7573 그물의 둘레와 물고기의 수가 100으로 매우 적다 이를 이용하여 완전탐색을 해주면 된다. 한 물고기에 대해 그 물고기를 둘레에 포함하는 가능한 모든 그물을 만들어본 뒤 확인해주면 된다. 1234567891011121314151617181920212223242526272829303132333435#include #include using namespace std;int n, l, m, r;pair f[101];bool chk(int x, int y, int lx, int ly, int rx, int ry) { return lx 더보기
BOJ)1202 보석 도둑 문제: icpc.me/1202 가장 가격이 많이 나가는 보석을 최대한 많이 담아야 원하는 답을 구할 수 있는건 그리디하게 알 수 있다. 그렇기 때문에 우리는 가장 가격이 많이 나가는 보석을 먼저 보며 lower_bound를 이용하여 현재 그 보석을 담을 수 있는 가방이 있느지 확인해주면 된다. 1234567891011121314151617181920212223242526272829303132#include #include #include #include using namespace std;int n, k, x, y;long long r;int main() { scanf("%d%d", &n, &k); priority_queue pq; for (int i = 0; i 더보기
BOJ)14499 주사위 굴리기 문제: icpc.me/14499 문제에서 주어진 조건에 맞게 주사위를 시뮬레이션해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include #include using namespace std;int n, m, x, y, k, a[21][21], dice[6], q;bool chk(int cx, int cy) { return 0 더보기
BOJ)2213 트리의 독립집합 문제: icpc.me/2213 트리에서 각 정점에 대한 가중치가 주어지고 정점들의 가중치를 최대로 가지는 최대독립집합 set을 구하는 문제이다. 트리에서의 최대 독립집합을 구하는 문제이기 때문에 사이클이 존재하지 않으므로 다이나믹 프로그래밍으로 해결할 수 있다. dp[pos][state]로 pos번째 정점에 대한 선택여부를 state로 강제한다면 점화식을 쉽게 세워줄 수 있다. 해당 정점을 선택할 경우 해당 정점에 대한 가중치를 얻고 자식들은 state를 선택안함으로 강제된다. 해당 정점을 선택하지 않을 경우 자식들의 state 결과는 선택하거나 선택안하는 경우 중 최댓값을 가지게 된다. 두 케이스에 따라 점화식을 다르게 세워준 후 다이나믹 프로그래밍을 이용하여 답을 구해준 뒤 역추적을 해주면 된다. 1.. 더보기

티스토리툴바