Let's Begin Programming

www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이 문제는 처음에 생각했을 때 모든 경우의 수를 고려하는 백트래킹 방법이 떠올랐다. 단순하게 문제에 나온 조건을 그대로 따라가는 것이다. 첫 집을 칠할 때는 가장 비용이 적은 색을 선택하고 그 색의 인덱스를 저장한다. 이후에는 그 인덱스에 해당하는 색을 제외하고 다른 색 중에서 더 적은 비용을 가지고 있는 색을 선택한다. 하지만 이 방법은 다이나믹 프로그래밍과 맞지 않다고 생각했다. 이 문..

개발 공부 (알고리즘) 2021. 3. 12. 00:58

www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제를 읽고 그림 예시를 보니 규칙성이 눈에 띄었다. 처음에는 어떻게 풀어야 할 지 해결 방법이 떠오르지 않았지만, 무언가 규칙이 존재할 것 이라는 생각을 지울 수 없었다. 이 문제가 다이나믹 프로그래밍 분류에 있는 문제라고 생각해서 떠올랐을 가능성이 크다고 생각한다. 1, 1, 1, 2, 2, 3, 4, 5, 7 ,9 위 수열은 문제에 나와있는 파도반 수열 P(10)의 숫자들이다. 규칙을 찾기 위해서 계속 삼각형 ..

개발 공부 (알고리즘) 2021. 3. 12. 00:49

www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 이 문제 또한 전형적인 다이나믹 프로그래밍(DP) 문제이다. 다이나믹 프로그래밍 문제는 n =1 일 때, n = 2 일 때 .. 이렇게 직접 세보면서 풀리는 경우도 꽤 있는 것 같다. 이 문제를 보고나서 종이에 직접 경우의 수를 구해보았다. 문제에 나와있는 예시는 n = 1, 2, 4 인 경우가 나와 있기 때문에 3, 5, 6 까지 해보니까 확실한 규칙이 보였다. n = 3 인 경우, 먼저 모두 0 인 경우는 존재하..

개발 공부 (알고리즘) 2021. 3. 11. 02:43

www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 다이나믹 프로그래밍 문제로 주어진 조건을 그대로 구현하면 실행 시간이 굉장히 오래 걸린다. 이럴 때 사용하는 것이 메모이제이션(Memoization) 기법이다. 캐싱(Caching)이라고도 부르는 이 기법은 중복된 연산을 피하고자 하는 다이나믹 프로그래밍을 위해서 기존에 계산한 결과를 저장해놓고 만약 다시 그 값이 필요하다면 곧바로 이미 저장되어있는 값을 반환하는 기법이다. 이 문제에서 입력으로 들어가는 변수는 a..

개발 공부 (알고리즘) 2021. 3. 8. 00:35