개발자는 눈 아프다

정올 Q1871 줄세우기

▶ 문제 http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1144&sca=3050

3 7 5 2 6 1 4

주어진 숫자를 최소한으로 이동하여 정렬하는 방법을 구하는 문제이다.

위 문제의 경우 7, 4, 1, 2를 옴겨 4번만에 정렬된 숫자열을 구할 수 있다.

▶ 문제 접근

 정렬알고리즘을 사용하여 문제를 푸는 것으로 접근하였다. 선택과 삽입중 고민하여 교환 횟수를 카운트하는 방법을 시도하였다. 여기에 다이나믹을 접목하여 f(n)의 n은 숫자으 갯수로 생각하여 문제에 접근하였다. 

하지만 f(n)들간의 관계를 정리하기 힘들었고 정렬의 특성상 최소한의 방법을 구하기 보다 각숫자를 삽입 교환하는 것 이하로 줄어들지 못하였다.

▶ 문제 풀이

 다이나믹을 활용하면 의외로 쉽게 풀리는 문제이다.

 이 문제의 정렬되기전 주어진 순열에서 최대의 길이로 정렬된 순자의 열을 찾는 것이다. 

위 문제에서는 3, 5, 6 으로 정렬된 최대길이의 순자열이다. 이 숫자열 이외의 4개의 수를 이동하면 최소 이동 횟수를 구할 수 있다.

 이를 구하는 방법은 가장 높은탑 쌓기와 유사한 방법으로 구할 수 있다. 

가장 뒤에서 부터(위 문제의 숫자 4) 자기를 포함하여 오른쪽에 자기보다 큰 숫자중 최대길이를 가진 숫자를 찾는 것이다.

f(n)을 구해보자

f(6) = 1

f(6)(6번째 위치한 4를 뜻한다.)는 4보다 오른쪽에 위치한 숫자는 없으므로 자기 자신의 길이인 1이다.

f(5) = 2

오른쪽에 4가 있으며 1,4는 정상 순열이기에 1+f(6)이므로 2이다.

f(4) = 1, f(3) = 2, f(2) = 2, f(1) = 1, f(0) = 3이다. 

올바른 최대 길이의 순열은 3이므로 답은 7-3=4 가된다.

정올 Q1539 가장 높은 탑 쌓기

▶ 문제 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=811&sca=305

가장 일반적인 형태의 다이나믹 프로그래밍 문제이다. 다이나믹 문제에서 유명한 knab과 유사한 형태를 띠고 있다.

조건

1. 넓이, 높이, 무게가 존재하며 동일 높이는 존재하나 동일 넓이, 무게는 없다.

2. 벽돌 위에 쌓으려면 넓이, 무게가 작아야 가능하다.

3. 가능한 모든 경우의 수중 최대 탑 높이를 구하여라

입력값

▶ 문제 접근

 최초 문제 접근 시 다이나믹 형태의 점화 식을 생각하지 못하였다. 그래서 각 벽돌과 그 벽돌 위에 쌓을 수 있는 벽돌을 찾아 2차원 int map을 만드는 형태로 코딩하였다. 답을 구할 수는 있었으나 다이나믹 문제 풀이의 의미가 없으므로 새로 접근해 보았다.

위에 올라갈 수 있는 벽돌의 수를 찾고 그 중 가장 높이가 높은 것과 자기 높이를 해서 자기의 값을 저장한다. 

▶ 문제 풀이

 1. 벽돌을 무게나 넓이에 의해 정렬한다.

위 입력 예시를 넓이에 의해 정렬해 보겠다.

1 5 2

4 4 6

9 2 3

16 2 5

25 3 4

편의상 위에서 순서대로 1번이라 칭하겠다.

1번벽돌 위에 올라갈 수 있는 벽돌은 존재하지 않는다 따라서 자기 높이만 더한 f(1)=5 이다.

2번 벽돌의 경우 1번 벽돌을 위에 올릴 수 있다. 따라서 최대 높이 f(2) = 9이다.

f(3)=7, f(4)=9, f(5)=10이다.

이중 최대 높이는 f(5)로 135번을 쌓은 것이다. 여기서 주의해야 할 점은 이 인덱스는 정렬한 상태이므로 초기 입력 시 받은 인덱스로 변환해 주어야 한다는 것이다.  생각보다 쉽게 풀리는 것이 다이나믹 문제라 할 수 있다.

다이나믹의 경우 N값이 보통 구하려고 하는 혹은 최대 값이 N인 경우가 대부분이다.