반응형 PS4 [백준 7576] 토마토 - C++ (BFS풀이) 토마토문제철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.토마토를 창고에 보관하는 격자모양의 상자들.. 2024. 5. 15. [백준 16236] 아기 상어 - 파이썬(Python) BFS풀이 시간 복잡도를 잘 줄인 코드 입니다!아기 상어문제N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.더 이상 먹을 수 있는 물고.. 2023. 9. 24. 파이썬(Python) 분할정복 개념과 예제 - 백준 1629 분할정복 알고리즘이란? 분할정복은 여러 알고리즘 한번에 해결할 수 없는 문제를 잘게 쪼개서 해결할 만한 부분문제들로 만든다음에, 그 문제들을 해결하면서 정복해가며 문제를 해결하는 방법으로 보통 재귀함수로 구현합니다. 문제를 잘게 쪼개서 해결한다고 하니까 동적 계획법(DP, 다이나믹 프로그래밍)이랑 똑같은것이 아닌가? 라고 생각이 들것입니다. 확실히 DP의 하향식 접근법이랑 유사한 부분이 많지만 부분문제가 중복되지 않는 부분에서 차이가 있습니다. DP문제, 예를 들어 피보나치 수열 구하기 등은 부분문제가 중복돼서 다른 상위 문제를 푸는데 해결되기 때문에 메모리제이션 기법을 사용합니다. (예를 들어 a10을 구하기 위해서 부분문제를 a9 a8로 나눴을때, a8의 부분문제 a7은 a9를 해결하는데도 쓰이므로 .. 2023. 9. 24. [백준 17144] 미세먼지 안녕! - 파이썬(Python) 미세먼지 안녕! 문제 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 A(r,c)이다. 1초 동안 아래 적힌 일이 순서대로 일어난다. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다. (r, c)에 있는 미세먼지는 인접한 네 방향.. 2023. 9. 23. 이전 1 다음
