알로그

백준 17144번 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net 전형적인 맵 형태의 BFS 문제이다. 코드를 구현한 순서는 (bfs -> 위측 공기청정기 순..

이번에는 BFS를 이용한 문제를 풀어보자. 이 문제는Brute-Force 방법으로도 풀 수 있는 문제이다. https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 값이 0에 해당하는 위치가 빈 ..

DFS를 이용하여 백준 문제를 풀어보자. https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 기존에는 맵 형태의 탐색을 하기 위한 DFS방식만 알고 있었는데, DFS를 백트래킹을 이용하여 탐색하는 방식으로 구현할 수 있다는 것을 처음 알게 해 준 문제이다. DFS, 백트래킹을 이용해서 팀을 나눠서 능력치의 합을 구하는 문제이다. 또는 순열을 이용해서 팀을 나눈 뒤, 능력치의 합을 구할 수도 있다. 딱히 설명할 부분은 없으며 DFS와 백트래킹을 이용하는 방법(값을 호출하..

백준 1463번 1로 만들기를 풀어보자. https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 전형적인 DP문제이며, 우선 DP문제를 풀기 위해 점화식을 세워보자. 연산을 사용하는 횟수의 최소값을 구해야 하므로 아래와 같이 점화식을 세울 수 있다. D[N] = N을 1로 만들기 위해 사용한 연산의 최소 횟수 이때 사용할 수 있는 연산은 세가지이다. 만약 N이 3이라면 3으로 나눌 수 있고, 나눗셈 연산을 했으므로 연산횟수 1을 더 해준다 ex) D[3] = D[3/3] + 1 -> D[3] = D[1] + 1 이런식으로 각 연산마다 세울 수 있는 점화식은 아래와 ..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net DP(Dynamic Programming)문제를 풀어보자. 문제에서 중요한 포인트가 있는데, 연속 두 계단씩 오를 수 있으며 마지막 도착계단은 반드시 밟아..