본문 바로가기

Problem Solving/BOJ 백준

 (132)
[ BOJ 백준 6118번 - 숨바꼭질 ] 해설 및 코드 https://www.acmicpc.net/problem/6118 목적 다음 그림과 같은 그래프에서 1번 정점과 다른 정점들과의 최단 거리를 구한 뒤, 그 중에서 가장 긴 길이의 정점에 관한 정보를 구하자. 접근법 1. bfs알고리즘을 이용하여 이전에 갱신한 거리보다 작은 경우 거리를 갱신하며, 이를 더이상 갱신할 것이 없을 때까지 반복한다. ( 백준 8061 - Bitmap문제와 유사한 방식을 이용한다.) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include #include #include #include #define f(i,l,r) for(int..
[ BOJ 백준 8061번 - Bitmap ] 해설 및 코드 https://www.acmicpc.net/problem/8061 목적 임의의 (i, j)에서 1이 있는 좌표(white pixel)와의 최단 거리를 구하자. 접근법 1. white pixel들의 좌표를 모두 queue에 담아 bfs 알고리즘을 이용하여 거리를 갱신해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include #include #define f(i,l,r) for(int i=l;i= ans[ni][nj]) continue; ans[ni][nj] = nk; q.push({ ni,nj,nk }); } } } int main(..
[ BOJ 백준 2606번 - 바이러스 ] 해설 및 코드 https://www.acmicpc.net/problem/2606 목적 1번 컴퓨터와 연결된 컴퓨터의 개수를 구하자. 접근법 1. 아주 많은 접근법이 있지만, Disjoint-set 자료구조를 이용하여 접근했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include #define f(i,l,r) for(int i=l;in; f(i,1,n)p[i]=i,size[i]=1; int m;cin>>m; while(m--){ int a,b;cin>>a>>b; combine(a,b); } cout
[ BOJ 백준 3430번 - 용이 산다 ] 해설 및 코드 https://www.acmicpc.net/problem/3430 목적 비가 내려 호수에 물이 넘치지 않도록 용이 호수 물을 먹는 순서를 구하자. 접근법 1. t[i]가 자연수일때, 즉 비가 내릴 때, 미리 우물을 비워야 한다. 탐욕적으로 비가 내리지 않는 날 중에서 가능한 가장 이른 날을 선택해야 한다. 왜냐하면 매 순간마다 선택할 수 있는 선택지를 최대한 많이 확보해야 하기 때문이다. 2. 선택할 수 있는 범위는, t[j]==t[i](j는 jt; if(t==0){ s.insert(i); ans[i]=0; } else{ set::iterator it=s.upper_bound(a[t]); if(it==s.end()){ while(m-->i)cin>>t; return false; } ans[*it]=t; ..
[ BOJ 백준 1840번 - 스도쿠 ] 해설 및 코드 https://www.acmicpc.net/problem/1840 목적 스도쿠에 채워 넣을 번호가 81개의 줄에 걸쳐서 주어진다. 이때, 실수한 단계가 몇 번째인지 구하자. 접근법 1. 1~81번까지 올바른 입력인지 확인하기에는 시간제한에 걸린다. 이분탐색으로 확인할 단계 수를 줄이든, 틀린 위치부터 단계를 거슬러 올라가면서 구해야한다. 이분탐색은 72ms 정도가 걸린다. 후자의 방법은 0ms. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include #define f(i,l,r) for(int i=l;i>..
[ BOJ 백준 1300번 - K번째 수 ] 해설 및 코드 https://www.acmicpc.net/problem/1300 목적 N*N 크기의 배열 A가 있다. A[i][j]에 i*j를 채워 넣고, 원소를 정렬하여 1차원 배열 B에 넣는다. 이때 B의 K번째 원소를 구하라. 접근법 1. 이분탐색으로 원소를 정하고, 좌우 범위 이동은 원소 크기 이하의 모든 원소 개수를 기준으로 한다. 2. 모든 원소의 개수는 O(n)으로 구해주자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #include #define f(i,l,r) for(int i=l;i> n >> k; int l = 1, r = k; while (l = k) r = num - 1; else l = num + 1; } cout
[ BOJ 백준 3020번 - 개똥벌레 ] 해설 및 코드 https://www.acmicpc.net/problem/3020 목적 1에서 H의 높이로 동굴을 일직선으로 통과하는 동안에, 만나는 장애물의 최소 개수와 그 때의 경로의 개수를 구하자. 접근법 1. 분류는 이분탐색이다. 풀이는 누적합이다. 이유는 더 쉽고 빠르기 때문이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #define f(i,l,r) for(int i=l;i> n >> h; n /= 2; f(i, 0, n) { int a, b; cin >> a >> b; --s[a]; ++s[h - b]; } int mn = n, cnt = 1, curr=n; f(i, 1, h) { curr += s[i]; if (c..
[ BOJ 백준 1939번 - 중량제한 ] 해설 및 코드 https://www.acmicpc.net/problem/1939 목적 섬과 섬 사이에 중량제한 데이터가 주어질 때, 공장이 있는 섬을 연결하는 경로중에 중량제한이 가장 큰 경로를 구하자. 접근법 1. 이분탐색으로 중량을 구한 후, dfs나 bfs로 검증한다. 두 가지 방법으로 테스트해 보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include #include #include #define f(i,l,r) for(int i=l;i>..

티스토리툴바