23.08.10. 풀었던 문제들 복기

Leetcode 53. Maximum Subarray, 25분

 백준 1912 ,최대 연속 부분수열 합을 구하는 문제와 같은 문제. dp로 쉽게 풀 수 있다. 링크에 풀 수 있는 4가지 방법이 있다.

// Runtime 76 ms Beats 96.56%
// Memory 67.7 MB Beats 32.89%

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();

        int answer = -1e9, sum = 0;
        for(int i = 0; i<n; i++){
            sum = max(nums[i], sum + nums[i]);
            answer = max(answer, sum);
        }

        return answer;
    }
};

 

 

 

BOJ 2412. 암벽 등반, 25분

 일단 이동 회수가 최소로 움직인다에서 BFS임을 알 수 있다. n이 5만이므로 충분하다.

 한 가지 문제는 이동할 수 있는 vertex가 정해져 있다는 것이다. x, y에서 |a-x| <= 2 && |b-y| <= 2인 a, b로만 이동할 수 있다. 만약 모든 vertex들의 edge list를 만들면, 그것만으로 O(n$^2$)이 걸리므로 어렵고, 2d array를 만드는 것도 같은 이유로 어렵다. 때문에 BFS에서 다음 vertex로 탐색을 진행할 때 O(logn)으로 타음 vertex를 결정할 수 있어야 한다. 다행히도 한 칸당 25번만 탐색하면 된다.

 logn을 쓰려면 크게 2가지 방법이 있을 것 같다. binary tree 구조인 map/set을 사용해 존재 유무를 결정하는 방법, 또는 입력을 x, y 순서로 정렬해 x에 대해 binary search 1번, y에 대해 binary search 1번을 하는 방법. map/set을 사용하는 방법이 더 간단해 보이므로 이 방법을 선택했다.

 BFS를 구현하기 위해서는 visited또한 필요하다. 바로 위의 존재 유무와 visited 여부를 동시에 사용하기 위해 map을 사용하자. map에 없으면 없는 vertex, map value가 0이면 unsitied, 1이면 visited로 생각하자.

 그러면 별 것 없이 풀린다!

typedef pair<int, int> pii;

int n, T;
map<pii, int> V; // == 0 : unvisited, == 1 : visited, 존재 유무는 find()로
struct info{
    int x, y, dist;
};

int solve(){
	cin>>n>>T;
    int x, y;
    for(int i = 0; i<n; i++){
        cin>>x>>y;
        V[{x, y}] = 0;
    }

    queue<info> q; // 좌표, dist
    q.push({0, 0, 0});
    while(!q.empty()){
        info cur = q.front(); q.pop();

        // 종료조건
        if(cur.y == T) return cur.dist;

        for(int dx = -2; dx<=2; dx++){
            for(int dy = -2; dy<=2; dy++){
                int nx = cur.x + dx, ny = cur.y + dy;
                if(V.find({nx, ny}) == V.end() || V[{nx, ny}] == 1) continue; // 없거나 visited인 경우
                V[{nx, ny}] = 1;
                info next; next.x = nx; next.y = ny; next.dist = cur.dist + 1;
                q.push(next);
            }
        }
    }

    return -1;
}

//////////////////////

int main(void) {
	cin.tie(0);
	cout.tie(0);
	std::ios_base::sync_with_stdio(0);

	cout<<solve();

	return 0;
}

 

시간복잡도

 vertex 개수가 V일 때 BFS에 O(V+E)인데 E가 25V이므로 O(V), 그리고 각 edge를 탐색하는 데 O(logV)가 걸린다. 따라서 O(VlogV)

 

 

다른 방법

 struct 말고 tuple도 쓸 수 있다. auto [a, b, c,] = q.front() 이런 식으로 쓰면 된다. struct 안 써도 되니까 상당히 편해 보이는군.