이우의 개발일지

백준 14940번 최단거리문제 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.입력지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.출력 각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.예제 입력 1 복사15 152 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1..

백준 7576번 토마토 토마토 문제풀이토마토 문제는 하루 동안 상, 하, 좌, 우에 있는 토마토들이 익게 되는데 며칠만에 익게 되는지 최소 값을 찾는 문제이다.상,하,좌,우 + 최소값을 얘기할 때 BFS를 자연스레 떠올리게 되었다. - 토마토 창고 크기는 M * N - M * N 크기의 창고에서 토마토의 각 상태 (1 : 익음, 0 : 안 익음, -1 : 존재 X) 를 저장한다. 만약 토마토가 익은 상태 (1) 이면 queue에 저장- queue에 저장된 값 중 front에 있는 값을 빼와서, 그 값의 상, 하, 좌, 우를 탐색한다. 탐색 조건으로는 0부터 m과 n 사이에 있어야하며, 상태가 0이여야 한다. - 만약 BFS를 다 돌고 나서, 0이 존재한다면 -1로 둘러쌓여있어서 탐색할 수 없다는 표시로 ..

DP, 다이나믹 프로그래밍이란? -> 하나의 문제를 단 한번만 풀도록 하는 알고리즘 설계 기법입니다. Why DP를 사용할까?그냥 사용하면 사실 재귀방식과 똑같이 사용할 수 있다. 하지만, 일반적인 코딩테스트 같은 경우 시간제한이 걸려있기 때문에 동일한 작은 문제를 여러번 풀면 무조건적으로 시간초과가 뜨게 된다.  예를 들어, 피보나치 수열을 그 예로 들 수 있다.#include int dp(int x){ if( x == 1) return 1; if( x == 2) return 1; return dp(x - 1) + dp ( x - 2); } 위 처럼 코딩을 하게 된다면, 50번째만 가도 굉장히 오래 걸리게 된다.  #include int d[100];int dp(int x){ ..