ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 회전초밥
    알고리즘/algospot 2016. 8. 1. 23:06

    항상 이런 DP문제들을 보면 어떤 값을 배열의 index로 표현할까가 나의 관심사였다. 가장 배열에 넣을 만한 값들은 예산에 해당하는 값들이었고 이 값들이 배열의 최대 범위를 초과하지 않기를 기도할 뿐이었다.


    하지만 최대 범위를 초과한다면.. 그 문제는 내겐 그때부터는 DP문제가 아니였다. 어떻게 최적화 할 것인가 머리를 짜매다가 풀지 못한 문제로 남아버렸다.


    책에서본 회전초밥문제도 그랬다. 단순 DP문제로 풀 수 있을 줄 알았는데 예산의 범위가 10^9이하여서 배열로 넣기는 무리였다. 문제의 힌트로 가격이 항상 100의 배수라 10^7정도는 배열에 넣으면 되겠다 생각했는데 메모리의 크기 제한이 64MB였다.


    int형으로 배열의 크기가 10^7로 잡자니 메모리가 초과할 것 같고 그렇다고 최대한 메모리를 쪼개고 쪼개 char형으로 배열을 선언하지나 답의 범위를 온전히 표현하지 못할 것 같았다.


    이런 경우에 사용하는 방법이 슬라이딩 윈도우이다. 슬라이딩 윈도우란 사용하는 데이터 전체를 메모리에 유지하는 것이 아니라 필요한 것들만 저장해두는 방식이다. 가장 대표적인예로는 피보나치배열의 n번째 항을 구하는 방법이다.


     
    int fibo(int n) {
    	if (n <= 1) return n;
    	int seq[3];
    	seq[0] = 0;
    	seq[1] = 1;
    	for (int i = 2; i <= n; i++)
    		seq[i % 3] = seq[(i - 1) % 3] + seq[(i - 2) % 3];
    }
    

    하나의 피보나치 항을 업데이트하는데 필요한 값은 총 3개이고 이때 사용하는 메모리들은 모두 재활용 될 수 있기에 크기 3인 배열로 해결 할 수 있다.

    위 기법을 초밥문제 풀 때도 사용해볼 수 있었다.

    c[현재 체크중인 예산 - 초밥의 최대 가격]이전의 값들은 필요가 없다. 배열의 값이 업데이트하면서 예전에 사용했던 값들은 쓸모가 없어진다. 이런 경우에 모든 최적화 경우의 값들을 초밥의 최대 가격 안에서 표현이 가능해진다. 즉 초밥의 최대 가격 만큼 배열의 크기를 선언해줄 수 있다.

     
    int solve(int c, int n) {
    	int budget, i;
    	int ret = 0;
    
    	for (budget = 0; budget <= c; budget++) {
    		int cand = 0;
    		for (i = 0; i < n; i++) {
    			if (budget >= price[i])
    				cand = max(cand, cost[(budget - price[i]) % 201] + pref[i]);
    			cost[budget % 201] = cand;
    			ret = max(ret, cand);
    		}
    	}
    
    	return ret;
    }
    

    cost[(budget-price[i])%201] 은 budget - price 예산에서 최대 높은 선호도를 갖는 값이다. 모듈러 연산을 통해 이전의 필요없는 값들을 제거한 것에 주목할 필요가 있다.

    역시 고수들은 다르다. 책에서 많은걸 배우는것 같다

    '알고리즘 > algospot' 카테고리의 다른 글

    카쿠로  (0) 2016.12.11
    블록게임  (0) 2016.08.01
    조합게임  (0) 2016.07.25
    ASYMTLING  (0) 2015.02.21
    NUMB3RS  (0) 2015.02.21

    댓글

Designed by Tistory.