23.03.08. 풀었던 문제들

Leetcode 875. Koko Eating Bananas

 어제와 동일한 문제. 문제를 딱 보면 parametric serach로 풀어야 할 것 같은 문제였다.

• 구해야 하는 값(k)의 범위는 넓지만
• k가 정해졌을 때 array를 순회하면서 다 먹을 수 있는지 여부는 쉽게 구할 수있고(O(n))
• 정답이 연속적이다. (어떤 t가 답이면 t보다 큰 모든 값은 답이 될 수 있다)

 모든 binary search문제가 그렇듯 상한을 어떻게 두느냐가 중요하다. 여기서는 piles[i]의 max값이 상한인데, k가 piles[i]보다 크더라도 모든 piles를 먹는 데 걸리는 시간은 동일하기 때문이다. 따라서 상한은 max of piles array이다. 순회하며 계산해도 되지만 명시적인 값을 두는 게 더 빠를 것 같아서 $10^{9} + 1$로 두었다.

 

 그리고 어제 배웠던 최적화 기법을 적용했다. hsum이 다 먹는데 걸리는 시간으로 잡았을 때, 이미 hsum을 초과하는 상황이라면 더 계산해 봤자 hsum이 더 커지기만 할 뿐이므로 break를 걸어 필요없는 연산 회수를 줄였다. 

// Runtime 36 ms Beats 97.14%
// Memory 19 MB Beats 45.12%

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int start = 1, end = 1000000001, mid, hsum;
        while(start < end){
            mid = (start + end) / 2;

            hsum = 0; // 다 먹는데 걸리는 시간 
            for(int i : piles){
                hsum += i/mid + (i%mid != 0);
                if(hsum > h) break;
            }

            if(hsum <= h) end = mid;
            else start = mid + 1;
        }
        return end;
    }
};

 

시간복잡도

 binary search에 O(log$10^{9}$), 각 binary search에서 O(n). 이 때 n은 piles.size()  따라서 O(nlog$10^{9}$)인데 O(log$10^{9}$)는 O(1)로 변환 가능하므로 O(logn)으로 볼 수 있다.

 

공간복잡도

 추가 공간을 사용하지 않으므로 O(1)이다.

 

후기

 문제 접근은 잘 했다. 그런데 이런 parameteric search가 면접에서 나온다고 하면 상한을 잘 계산해야 할 것이다. 상한을 두고, 왜 그 값으로 설정했는지 증명에 대해 고민해 보자.

 잘 모르겠다면 로직을 다 짜고 그 이후에 상한을 설정해도 괜찮을 것 같다.

 

 

프로그래머스 카운트 다운

 전형적인 DP 문제. DP를 어떻게 접근할지는 항상 고민이지만 나는 재귀를 이용하는 top-down보다 for문을 쓰는 bottom-up이 훨씬 직관적인 것 같다. 현재 index를 이용해 다음 값을 계산할 수 있기 때문인 것 같다. 그러나 항상 상황에 맞춰 사용해야 한다.

 문제는 간단하다. [던진 회수, single shot 또는 bull shot 개수] 2개 조건이 있는 DP 문제이다.

• 1. 던진 회수 최소화
• 2. 만약 던진 회수가 같다면
  • single shot 또는 bull shot 개수가 더 많아야 한다.

 

 위 로직을 그대로 구현하면 된다.

 현재 점수를 i라고 두었을 때, i는 1부터 20까지 single shot이 더해질 수 있고, 2, 4, ... , 40 / 3, 6, 9, ... , 60까지 double/triple shot이 더해질 수있고 50이 bull shot으로 더해질 수 있다.  

• i에서 던진 점수를 p라고 할 때
• [i + p점을 던진 회수]가 [i점을 던진 회수 + 1]와 같을 때 - single shot 또는 bull shot 개수가 더 많은 쪽으로 선택함
• [i + p점을 던진 회수]가 [i점을 던진 회수 + 1]보다 클 때
  • i점에서 p를 던진 상태가 더 최적화된 상태이며 이것으로 갱신한다
• 이 식은 아래 calNext() 함수에 들어 있다.

typedef pair<int, int> pii; // .first : 던진 회수, .second : 싱글/불 회수 합

// dp[i]와 dp[i + p]를 비교 후 dp값을 채워넣음
void calNext(vector<pii> &dp, int i, int p, bool isSingleOrBull){
    if(i + p < dp.size()){
        if(dp[i + p].first == dp[i].first + 1){
            dp[i + p].second = max(dp[i + p].second, dp[i].second + isSingleOrBull);
        }
        else if(dp[i + p].first > dp[i].first + 1){
            dp[i + p].first = dp[i].first + 1;
            dp[i + p].second = dp[i].second + isSingleOrBull; // 실수 : 여기도 isSingleOrBull 더해주어야 함
        }
    }
}

vector<int> solution(int target) {
    vector<pii> dp(target+1, {INT_MAX, INT_MIN});
    dp[0] = {0, 0};
    for(int i = 0; i<=target; i++){
        // 1 ~ 20점
        for(int p = 1; p<=20; p++){
            calNext(dp, i, p, true); // 1배
            calNext(dp, i, 2*p, false); // 2배
            calNext(dp, i, 3*p, false); // 3배
        }
        // 50점
        calNext(dp, i, 50, true);
    }
    
    vector<int> answer(2);
    answer[0] = dp[target].first; answer[1] = dp[target].second;
    return answer;
}

 

시간복잡도

 target을 n이라고 하면 O(n)이다. 앞에서부터 순회하고 각 for문에 61번 순회하기 때문

 

공간복잡도

 추가 공간은 dp vector size인 O(n)만큼 사용한다.

 

후기

 코드를 상당히 깔끔하게 짠 것 같다. 뭔가 만족스럽다.

 i + p 점수를 갱신할 때 던진 회수만 갱신하고 isSingleOrBull를 갱신하지 않았다. 실수... ㅠㅠ

 

 

 

프로그래머스 2차원 동전 뒤집기

 첫 접근은 조합이었다. 똑같은 것을 2번 뒤집으면 의미 없기 때문이다.

 예를 들어 row 1을 뒤집은 후, col x를 뒤집었다가 다시 row 1을 뒤집으면 그냥 col x만 뒤집은 것과 같다. 따라서 row와 col 개수 중에 몇 가지를 골라 뒤집어야 한다는 것이다.

 따라서 전체 (row + col) = s라고 하자. sC0 / sC1 / sC2 / ... / sCs를 모두 계산하면서 답이 나오면 그것 중 최소값을 찾으면 된다. 참고로 s의 상한은 20이고, 파스칼 삼각형의 특성상 i번째 행의 합은 $2^{i}$이므로 $2^{20} = 1000^{2}$, 약 1백만 정도. vector의 비교에 O(n^2)이기 때문에 시간 내에 풀 수 있을 것이라 생각했다.

 

 인데... 이렇게 접근한 이유는 row와 col이 같은 정사각형 모양일 것이라고 생각해서이다.

 

 다르다는 것을 알고는 bitmask를 이용해서 brute-force 했다.

 

 정답 코드는 아래와 같다.

typedef vector<vector<int>> board;
int rsize, csize = 0, answer = INT_MAX;

void flipRowK(board& b, int k){
    for(int i = 0; i<csize; i++){
        b[k][i] = 1 - b[k][i];
    }
}

void flipColK(board& b, int k){
    for(int i = 0; i<rsize; i++){
        b[i][k] = 1 - b[i][k];
    }
}

int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
    if(beginning == target) return 0;
    
    rsize = beginning.size(); csize = beginning[0].size();
    
    // i를 bit로 표현했을 때 1이 오는 위치가 row flip하는 자리이다.
    for(int i = 0; i < (1 << rsize); i++){
        board rowtemp = beginning;
        int rcount = 0;
        // 1이 오는 위치 찾기
        for(int k = 0; k<rsize; k++){
            if(1 & (i >> k)){
                flipRowK(rowtemp, k);
                rcount++;
            }
        }
        
        // j를 bit로 표현했을 때 1이 오는 위치가 column flip하는 자리이다.
        for(int j = 0; j < (1 << csize); j++){
            board coltemp = rowtemp;
            int ccount = 0;
            // 1이 오는 위치 찾기
            for(int k = 0; k<csize; k++){
                if(1 & (j >> k)){
                    flipColK(coltemp, k);
                    ccount++;
                }
            }
            if(coltemp == target){
                answer = min(answer, rcount + ccount);
            }
        }
    }
    
    
    return answer == INT_MAX ? -1 : answer;
}

 

시간복잡도

 설명했듯 완전 탐색이며 2중 for문에 O($2^{20}$), vector 비교에 O($n^{2}$). n의 상한이 10이므로 1초에 아슬아슬 풀린다.

 

후기

 하........ 진짜 화난다 문제 조건에서 row size와 col size가 같다는 조건을 명시하지 않았는데 흘려 짚고 넘어가서 같다는 조건으로 구현했다. 하...진짜... 이것 때문에 삽질을 2시간을 했다...

 row size와 col size가 다르다면 당연히 조합으로 풀 생각을 안 했을 것이다

 vector의 == 연산자는 내부 element까지 모두 비교한다.

 

bitmask의 유용한 몇 가지

// true/false 총 k를 선택한다고 생각하자.
// 모든 경우의 수 n은 2^k이므로 아래와 같이 표현할 수 있다.
int n = 1 << k;

// 어떤 경우의 수 case에 대해 1일 때만 무언가를 하고 싶을 때
int case = // ... 어떤 경우의 수
for(int i = 0; i<k; i++){
    if(1 & (case >> i)){
        // ...
        // case를 오른쪽으로 i번 당긴 것이 1일 때
    }
}

// 또는 아래와 같이 표현할 수 있다.
for(int i = 0; i<k; i++){
    if(case & (1 << i)){
        // ...
        // case의 i번째 자리가 1일 때
    }
}

// 모든 경우의 수에 대해 1일 때에 무언가를 할 때
for(int case = 0; case < n; case++){
    for(int i = 0; i<k; i++){
        if(1 & (case >> i){
            // ...
            // case를 i번 당긴 게 1일 때
        }
    }
}