본문 바로가기

알고리즘 관련/BOJ

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.. 더보기
BOJ)3770 대한민국 문제:icpc.me/3770 동해안과 서해안을 잇는 고속도로의 셋이 주어질 때 교차점의 수를 구하는 문제이다. 모든 고속도로를 받아서 동해안의 순서로 오름차순 정렬을 해준 뒤 동해안의 순서로 보면서 현재 보고 있는 고속도로보다 전에 봤던 고속도로 중 현재 고속도로보다 서해안이 큰 고속도로들의 수를 구해주면 된다. 이를 효과적으로 계산하기 위하여 세그먼트 트리를 사용해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #include using namespace std;int t, n, m, k, x, y, seg[10000];long long r;int update(in.. 더보기
BOJ)6091 핑크 플로이드 문제: icpc.me/6091 플로이드 워셜로 구해진 최단거리의 셋이 주어질 때 원래의 트리에 연결 된 간선만 출력하는 문제이다. 우리는 주어진 최단거리의 셋중에서 가장 작은 간선부터 그리디하게 선택할 수 있다. 근데 이 때 선택하면 안되는 간선을 트리의 성질을 이용하여 알 수 있다. 트리에서 a에서 b로 가는 경로는 유일해야 하므로 내가 현재 보고 있는 간선에 연결 된 양쪽 두 정점이 이미 하나의 컴포넌트를 이루고 있다면 그 간선은 사용하면 안된다. 따라서 우리는 가장 작은 간선부터 연결해 주되 disjoint-set을 이용하여 두 컴포넌트를 연결시켜주어 해당 간선이 컴포넌트를 이루는지 여부를 판단한다. 1234567891011121314151617181920212223242526272829303132.. 더보기
BOJ)1826 연료 채우기 문제:icpc.me/1826 1km를 가는데 1L의 연료가 필요하고 현재 가진 연료량과 목적지까지의 거리 그리고 각 주유소의 정보가 주어질 때 충전횟수를 최소화하여 목적지에 도착하는 충전횟수를 출력하는 문제이다. 우선 주유소의 정보를 받아 거리를 기준으로 sort한 뒤 내가 현재 갈 수 있는 거리보다 가까운 거리에 있는 모든 주유소의 정보를 받아와 채울 수 있는 연료량을 heap에 저장한다. 이후 그리디하게 갈 수 있는 주유소중 가장 큰 연료량을 가지는 주유소를 선택해나가면 문제를 해결 할 수 있다. 123456789101112131415161718192021222324252627#include #include #include using namespace std;priority_queue pq;int n.. 더보기

티스토리툴바