풀이
백준 22871번 : 징검다리(large)
https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 이분 탐색 카테고리 문제를 풀다가 접하게 된 문제다. 연산시간 때문에 하루종일 이 문제만 붙잡고 고민했다. 최적화 하려는 변수가 M이라면 보통 이분탐색 문제는 O(log M) 시간안에 해결이 가능하거나 그 보다 오래 걸리더라도 주어진 시간 안에 해결이 가능했다. 관련하여 문제를 풀면서 고민한 것들을 글에 풀어서 써보겠다. N개의 징검다리..
백준 3079번 : 입국심사
https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 2110번에서 알게된 내용들을 적용해서 생각보다 쉽게 푼 문제다. M명의 사람들은 입국하기위해 입국심사를 받는다. 심사대는 총 N개가 있고 심사대마다 심사에 소요되는 시간이 정해져있다. M명의 사람들을 모두 통과시키는 최소한의 시간을 구하는 문제이다. 앞서 푼 문제에서 배운 이분 탐색의 요령을 그대로 적용했다. 구하려는 값은 시간이기 때문에 가능한 범위 안에서 조건(시간 안에 사람들..
백준 2110번 : 공유기 설치
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 우아한 테크코스 코딩테스트를 준비할겸 기초 알고리즘을 복습하기 위해 접했던 이분 탐색 문제다. 기존에 풀었던 이분 탐색 문제와 달리 바로 해결 아이디어가 떠오르지 않아서 질문 게시판을 참고해서 해결했다. 일직선(1차원) 좌표상의 특정 좌표에 집이 존재하고 주어진 개수만큼의 공유기를 집에 설치하고자 한다. 공유기는 한 집에 1개만 설치가능하며 주어..
백준 2636번 : 치즈
https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 고민하다가 자체적으로 난이도를 높혀버린 문제이다. 문제 풀이 자체는 다른 그래프 알고리즘과 크게 다르지 않다. 문제를 간단히 요약하자면, 1x1 크기의 정사각형으로 이루어진 판 위에 치즈가 일부분 올려져있고 이 치즈는 공기에 노출된 상태에서 1시간이 지나면 녹아 없어진다. 치즈엔 구멍이 뚫려 있는데 다행히도 이 구멍엔 공기가 없어서 치즈 안쪽에서부터 녹아 없어지진 않지만, 바깥 공기가 구멍 안쪽으로 들어갈..
백준 16234번 : 인구 이동
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 유독 풀면서 실수가 많았던 문제. 풀이 자체는 다른 BFS 그래프 탐색 문제와 다르지 않다. 크기가 NxN인 땅 안에 1x1 크기의 나라가 하나씩 존재한다. 각 나라별로 인구수가 정해져있고 인접 나라와의 인구수의 차이에 따라 인접한 국경선을 열 수 있다. 그렇게 해서 열린 국경선을 따라 하루동안 인구가 이동하는데 특정 나라에서 출발하여 방문이 가능한 나라들은 모두 연합이며, 한 연합..
백준 16956번 : 늑대와 양
https://www.acmicpc.net/problem/16956 16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 www.acmicpc.net DFS, BFS를 이용한 그래프탐색 카테고리에 포함된 문제들을 풀다가 특이한 문제를 발견했다. 문제를 요약하면 1x1 크기의 칸으로 나뉘어진 목장의 상태를 보고, 자유롭게 움직일 수 있는 늑대가 양에게 접근할 수 없게 울타리를 친다. 문제를 보고 이해했을땐 단순히 처음 주어진 늑대의 위치 좌표를 초기 큐에 넣고 BFS 탐색을 하면서 인접한 칸들을 확인하며 인접칸에 양이 있다면 그 자리에 울타리..