CS/Algorism (99) 썸네일형 리스트형 [백준] 12825. 1로 만들기 2 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net n을 1로 만드는 가장 적은 연산 횟수를 구해서 출력하고, 이때 연산 과정까지 출력해야 한다. dp[i]: i를 1로 만드는 최소한의 연산 갯수 record[i]: i를 1로 만드는 최소한의 연산 갯수의 과정에서, i가 되기 이전의 값 주의할 점은 dp[i]로 오는 경우가 여러개가 있을 수 있는데 (ex, dp[4] : 1 -> 2 -> 4, 1 -> 2 -> 3 -> 4), 기존 dp[i]의 값보다 새로운 dp[i]의 값이 작을 때만 갱신해주어야 한다. import java.io.BufferedRea.. [백준] 1149. RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 잘못 생각하면 그리디 알고리즘을 떠올릴 수 있다. 1번째 집부터 접근하여 3가지 색 중 가장 비용이 적은 색으로 칠하고, 2번째 집에 접근하여 1번째 집이 사용한 색을 제외하고 비용이 적은 색으로 칠하는 방식이다. 그러나 이는 잘못된 방법이다. 반례는 다음과 같다. 각 집이 빨간색, 초록색, 파란색으로 집을 칠하는 비용이 아래와 같다. 1번 집 1 100 103 2번 집 1 .. 알고리즘 간단 정리 다이나믹 프로그래밍(DP) 주어진 문제를 여러 개의 작은 문제로 나누어 푼 다음, 그 결과들로 주어진 문제를 푼다. 즉 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 때 적용된다. 구현 방식 메모이제이션: 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 분할 정복은 문제를 분할했을 때 겹치는 문제가 발생하지 않는다. 반면 DP는 겹치는 문제가 발생하기 때문에 메모제이션이 필요하다. Top-Down 방식: 재귀 함수를 이용하여, 큰 문제 해결을 위해 작은 문제를 호출하는 방식이다. Bottom-Up 방식: 반목문을 이용하여, 작은 문제부터 차근차근 답을 도출하는 방식이다. 재귀 .. 이전 1 ··· 10 11 12 13 다음
