Algorithm/BOJ
BOJ] 14502. 연구소
BOJ] 14502. 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 2017년 SW역량테스트 기출문제 풀었던 문제지만, 떠올릴 겸 다시 풀어보았다. 생각보다 막힌 부분이 있었지만..
BOJ] 2805. 나무 자르기
BOJ]2805.나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따 www.acmicpc.net 이분탐색(Binary Search) 문제. . 0부터 나무의 가장 높은 높이를 찾아서 그 사이의 값들을 ..
BOJ] 4179. 불!
BOJ] 4179. 불! https://www.acmicpc.net/problem/4179 4179번: 불! 문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간 www.acmicpc.net 기본적으로 BFS알고리즘을 적용하지만, 한번 더 생각이 필요! 보통 2가지 방법으로 접근하는 것 같다. 불 한번 퍼지고, ..
BOJ] 16283. Farm
BOJ] 16283. Farm https://www.acmicpc.net/problem/16283 16283번: Farm 문제 목장 주인인 상배는 양과 염소들을 같이 기르고 있다. 기르는 양과 염소는 각각 한 마리 이상이다. 양과 염소는 같은 사료를 먹고, 양 한 마리는 하루에 사료를 정확히 a 그램 먹고, 염소 한 마리는 하루에 정확히 b 그램을 먹는다고 한다. 상배는 매일 아침 양과 염소가 각각 몇 마리인지를 확인하는 작업을 한다. 양과 염소가 각각 몇 마리인지 확인할 때, 양과 염소들이 돌아 다녀서 정확하게 그 수를 구하는 것이 쉽지 않았다. 대신에 양과 염소가 전체 www.acmicpc.net 연립방정식을 세워랏 연립방정식 세우기 문제의 조건 빼먹지 않기 해가 두개이상이어도 -1출력. 2의 조건때..
BOJ] 2579. 계단오르기
BOJ]2579.계단오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net DP는 고민하고 또 고민해야한다. 점화식(규칙)을 찾아야한다! 문제에서의 아래 규칙을 고려하여 점화식을 구해야한다. 계단은 한 ..
BOJ] 1003. 피보나치 함수
BOJ]1003. 피보나치 함수 https://www.acmicpc.net/problem/1003 DP의 맛보기 문제정도이다. 단순히 피보나치의 결과를 구하는 문제가 아니다. 피보나치 함수가 호출되었을 때, 0과 1이 얼마나 반환(출력)되는지 구하는 문제이다. 규칙을 살펴보자. 예를 들어, fibo(n) : (0의 반환횟수, 1의 반환횟수) 라고 하자. fibo(0) : (1,0) fibo(1) : (0,1) fibo(2) : (1,1) -> fibo(0) + fibo(1) -> (1,0) + (0,1) fibo(3) : (1,2) -> fibo(1) + fibo(2) -> (0,1) + (1,1) fibo(4) : (2,3) -> fibo(2) + fibo(3) -> (1,1) + (1,2) 피보나치의..