알로그

이번에는 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)문제를 풀어보자. 문제에서 중요한 포인트가 있는데, 연속 두 계단씩 오를 수 있으며 마지막 도착계단은 반드시 밟아..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 쉬울 줄 알았는데 생각보다 구현이 어려웠던 문제이다. dfs를 이용해서 구현하였으며 방향을 설정해주는 dir 변수도 파라미터로 사..