프로그래머스[Lv.3] - 최적의 행렬 곱셈 문제 설명 사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다. 예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다. ((1 - 5) - 3) = -7 (1 - (5 - 3)) = -1 위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다. 또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다. (((1 - 3) + 5) - 8) = -5 ((1 - (3 + 5)) - 8) = -15 (1 - ((3 + 5) - 8)) = 1 (1 - (3 + (5 - 8))) = 1 ((1 - 3) + (5 - 8)) = -5 위와 같이 서로..
동적계획법
오랜만에 DP 문제를 풀어보았다. 정수 삼각형을 입력받아 저장한 뒤, 최종적으로 가장 큰 수를 만들어 가는 문제이다. 단, 선택할 수는 다음행의 수 중, 왼쪽, 오른쪽 둘 중 하나만 선택 가능하다. 즉, 7에서 선택할 수 있는 수는 3, 8 둘 중 하나이다. 이런 방식으로 하나씩 더해 나가 가장 큰 수를 만들면 된다. 얼핏 보면, 선택할 수 있는 수 중에 큰 수를 선택해서 진행하면 되는 탐욕 법 문제로 볼 수 있다. 하지만, 그 다음 상황은 모르기 때문에 탐욕 법은 항상 올바른 답을 주지 않는다. 따라서, 동적 계획법을 이용하여 답을 구해내면 된다. 다음은 Java로 작성한 코드이다. import java.util.Scanner; public class Triangle { public static voi..
입력받은 수를 3으로 나누기, 2로 나누기, 1 빼기 이 세 가지 연산을 이용하여 1로 만드는 최소의 연산 횟수를 구하는 문제이다. 얼핏 보면, 3으로 나누는 연산이 가장 수를 많이 줄여주니까 3으로 나누고, 3으로 나누지 못하면 2로 나누고, 그러지 못하면 1을 빼는 식으로 구할 수 있는 간단한 문제인 것 같이 보인다. 하지만 이것은 탐욕 법으로 계산하는 방법이며, 항상 최적해를 구할 수 없다. 예를 들어, 10을 1로 만드는 방법을 탐욕법으로 구한다면 10 -> 5 -> 4 -> 3 -> 1으로 총 4회의 연산이 필요하다. 하지만, 동적 계획법으로 연산을 하면 10 -> 9 -> 3 -> 1 로 총 3회의 연산만으로 1로 만들 수 있다. 따라서, 모든 경우의 수를 살펴 보아야 한다. import ja..
