GOD동하님의 블로그

오랜만에 다시 시작한 알고리즘 그래서 쉬운거, 구현 위주로 일단 시작해보려 한다. https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 모든 알고리즘이 그렇듯이 문제의 제약이나 조건..

DP에서 중복이 발생하므로 memoization을 해야한다는 근거 설명

RGB 거리 알고리즘 문제 Dynamic Programming을 연습하기에는 아주 전형적인 문제라고 생각한다. 풀이1 : 하향식 DP (Top-Down 재귀) 1. 큰 문제를 작은 문제로 분류 2. 최소 단위의 답을 해결하며 병합 풀이2 : 상향식 DP (Bottom-Up 반복문) 1. 작은 문제를 먼저 해결 2. 먼저 푼 문제의 답을 이용해 큰 문제를 해결 설명 : TODO 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475/** * RGB 거리 (문제번호 : 1149) * * @category Dyna..