algorithm. Introduction to Algorithms 3rd 15.1 Rod cutting

Rod cutting(Dynamic programming)



문제: 위의 가격이 정해져 있을 때 n length인 막대기를 짤라 파는 경우 중 가장 수익이 높은 값은?

생각은 간단하다.

MaxPrice[n] = Max(p[i] + MaxPrice[n - i])

이 것을 코드화 하면

import sys 
P = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30] 

def rodCut(p, n): 
        if n == 0: return 0
        ret = 0 
        for i in range(1, n + 1): 
                ret = max(ret, P[i] + rodCut(p, n - i)) 
        return ret 

rl = lambda: sys.stdin.readline()
print(rodCut(P, int(rl())))

이고
dynamic programming을 적용해서 r에 저장하면

def memorizedCutRodAux(p, n, r): 
        if n == 0:
                r[n] = 0 
                return r[n]
        if r[n] >= 0:
                return r[n]
        ret = 0 
        for i in range(1, n + 1): 
                r[n] = ret = max(ret, P[i] + memorizedCutRodAux(p, n - i, r)) 
        return r[n]

def memorizedCutRod(p, n): 
        r = [-1] * (n + 1)
        return memorizedCutRodAux(p, n, r)
print(memorizedCutRod(P, int(rl())))

그리고 이 것을 bottom up 방식으로 구현하면

def bottomUpMemorizedCutRod(p, n): 
        r = [-1] * (n + 1)
        r[0] = 0 
        for i in range(1, n + 1): 
                ret = 0 
                for j in range(i + 1): 
                        r[n] = ret = max(ret, p[i] + r[n - i]) 
        return r[n]
print(bottomUpMemorizedCutRod(P, int(rl())))

이다.
시간 제약에 걸릴 때 가장 먼저 생각해보는 방법이다..

덧. TopCoder 알고리즘 책에는 변수가 여러가지 인 경우 배열로 저장하기 위한 방법을 표현한 문제가 있다.

Algorithm. Scanning(스캐닝) algorithm

algospot의 MAXSUM 문제:
scanning algorithm을 사용해야 함. scanning algorithm은 기본 concept는
--> '최대값 계산 시, 음수가 포함된다면 잘라내기'
라고 요약할 수 있겠다.

먼저 내가 작성한 source를 보자

package com.yongk.algospot.MAXSUM;

import java.util.Scanner;

public class MAXSUM {
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int T = Integer.parseInt(sc.nextLine());
  while(T-- > 0) {
   int N = sc.nextInt();
   sc.nextLine();
   int[] input = new int[N];
   String[] temp = sc.nextLine().split(" ");
   for (int i = 0; i < N; i++) {
    input[i] = Integer.parseInt(temp[i]);
   }
   System.out.println(getMaximumSetFast(input));
  }
  sc.close();
 }
 private static int getMaximumSetFast(int[] input) { //scanning algorithm
  int max = 0;
  int from = 0;
  for (int i = 0; i < input.length; i++) {
   from = Math.max(from + input[i], 0);
   max = Math.max(max, from);
  }
  return max;
 }
 private static int getMaximumSetSlow(int[] input) { //처음 생각한 O(n^2)의 저속한 algorithm
  int[] sum = new int[input.length];
  sum[0] = input[0];
  int max = 0;
  for (int i = 1; i < input.length; i++) {
   sum[i] = sum[i - 1] + input[i];
   max = Math.max(max, sum[i]);
  }
  
  for (int i = 0; i < sum.length; i++) {
   for (int j = i; j < sum.length; j++) {
    max = Math.max(max, sum[j] - sum[i]);
   }
  }
  return max;
 }
}

- 처음 생각한 것이 getMaximumSetSlow()인데 나름 짱구를 굴려 미리 계산한 값으로 중복 계산을 줄이자는 생각이었지만 미개한 생각이었다.
- getMaximumSetFast()가 scanning algorithm. input[0]에서부터 더해가다가 그 값이 0보다 작아지면 당연히 거기까진 더할 필요가 없다. 왜냐하면 거기서부터 더하는건 0보다 크기 때문.
- 덕분에 scanning algorithm은 O(n)의 속도이다.
- 사람도 이렇게 생각하지 않을까?

덧1, python으로 같은 것을 구현하면

import sys 
def getMaximumSetFast(input):
        maxVal = 0 
        fromVal = 0 
        for i in input:
                fromVal = max(fromVal + i, 0)
                maxVal = max(fromVal, maxVal)
        return maxVal

rl = lambda: sys.stdin.readline()
T = int(rl())
for i in range(T):
        rl()
        input = [int(j) for j in rl().split()] 
        print(getMaximumSetFast(input))

덧2. 그리고 java.util.Scanner()는 느리다..대따 느리다 ㅠㅠ 가급적이면 nextInt()보다는 nextLine()을 parseInt()할 것! 처음엔 다음과 같이 작성했었는데..참담한 속도였다. 적어도 5배 이상 느림.

  while(T-- > 0) {
   int N = sc.nextInt();
   int[] input = new int[N];
   for (int i = 0; i < N; i++) {
    input[i] = sc.nextInt(); //slow!!!
   }
   System.out.println(getMaximumSetFast(input));
  }

Algorithm. 실수 연산

프로그래밍 중 실수 연산이 문제가 되는 경우가 왕왕 있음.

오늘도 algorithm 문제 풀다 한번 위기에 봉착해서 오답노트겸 적어놓는다.

package com.yongk.algospot.RATIO;
import java.util.Scanner;

public class RATIO {

 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int T = Integer.parseInt(sc.nextLine());
  while(T-- > 0) {
   long N = sc.nextLong();
   long M = sc.nextLong();
   System.out.println(getMinimumTick(N, M));
  }
 }

 private static long getMinimumTick(long N, long M) {
  
  long Z = (long)(1 + M * 100 / N);
  if (Z >= 100) return -1;
  return (long)Math.ceil((Z * N - 100 * M) / (100 - Z));

 }
}

위에서 틀린 것을 찾아보면..
Math.ceil에 들어가는 인자가 long으로 연산되어 double로 cast 되어 Math.ceil에 입력됨.

 private static long getMinimumTick(long N, long M) {
  
  long Z = (long)(1 + M * 100 / N);
  if (Z >= 100) return -1;
  return (long)Math.ceil((double)(Z * N - 100 * M) / (100 - Z));

 }

로 변경이 필요하다. 별 것 아닌데 개고생함.

결론:
1. 가급적이면 실수 연산을 정수 연산에 섞지 않고
2. 섞어야 한다면 캐스팅 반드시 할 것