The more I learn, the more I realize how much I do not know
욕심쟁이 판다

욕심쟁이 판다

현재 위치를 (x, y), 이동할 위치를 (nx, ny) 일경우

현재 최대 생존일수 + 1 이 이동할 자리의 기존 최대 생존일수 보다 클 경우에만 업데이트 한다
(다익스트라에서 최단거리 업데이트와 유사)
d[nx][ny] 값이 더 컸을 경우 이동하지 않는 것이 낫다.

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        if (d[i][j] == 0) {
            d[i][j] = 1;
            f(i, j);
        }
    }
}
static void f(int x, int y) {
    int nx, ny;

    for (int i = 0; i < 4; i++) {
        nx = x + dx[i];
        ny = y + dy[i];
        // (d[x][y] + 1 > d[ax][ay] ??
        if (isInRange(nx, ny) && map[x][y] < map[nx][ny] && d[x][y] + 1 > d[nx][ny]) {
            d[nx][ny] = d[x][y] + 1;

            max = Math.max(max, d[nx][ny]);
            f(nx, ny);
        }
    }
}
자동차 경주

Problem

https://www.acmicpc.net/problem/2611

Summary

단방향, 1번 지점에서 출발하여 가장 많은 점수를 얻어 다시 1번 지점으로 돌아오는 경로 및 점수를 구한다

Idea

dist[curr]: curr 에서의 최대 값 저장

dist[curr] = max(dist[curr], dist[next.to] + next.w)

dfs

  • 1 -> 2 -> 5 -> 6 -> 8 -> 7 -> 4 -> 1
    d[4] = max(d[4], d[1] + 6) = 6
  • 1 -> 2 -> 5 -> 6 -> 8 -> 7 -> 4 -> 1
    d[7] = max(d[7], d[4] + 5) = 11
  • 1 -> 2 -> 5 -> 6 -> 8 -> 7 -> 4 -> 1
    d[8] = max(d[8], d[7] + 4) = 15
  • 1 -> 2 -> 5 -> 6 -> 8 -> 7 -> 4 -> 1
    d[6] = max(d[6], d[8] + 3) = 18
static void dfs1(int curr) {
    for (V next : adj.get(curr)) {
        if (dp[next.to] == 0) {
            dfs1(next.to);
        }
        dp[curr] = Math.max(dp[curr], dp[next.to] + next.w);
    }
}

f(curr): curr에서의 최대 값 으로 정의한다면

static int f(int curr) {
    if (dist[curr] != -1) {
        return dist[curr];
    }
    dist[curr] = 0;
    for (V next : adj.get(curr)) {
        int w = f(next.to) + next.w;
        if (w > dist[curr]) {
            dist[curr] = w;
            trace[curr] = next.to;
        }
    }
    
    return dist[curr];
}

bfs

dijkstra로 최고 가중치를 구하는 문제로 생각해 볼 수 있다

경로는 업데이트 할때마다 그 때의 이전 노드를 따로 저장 (즉, 어디서부터 왔는 가를 저장)하여
마지막엔 시작 노드로부터 그 역순으로 따라올라가면 경로를 얻을 수 있다.

s -> e 방향이면 trace[next] = curr;
e -> s 방향이면 trace[curr] = next;

static void bfs() {
    Queue<V> q = new PriorityQueue<V>();
    q.add(new V(1, 0));
    boolean looped = false;
    trace[1] = 1;
    while (!q.isEmpty()) {
        V curr = q.poll();

        if (curr.to == 1) {
            if (looped) {
                continue;
            }
            looped = true;
        }
        for (V next : adj.get(curr.to)) {
            if (dist[curr.to] + next.w > dist[next.to]) {
                dist[next.to] = dist[curr.to] + next.w;
                q.add(new V(next.to, dist[next.to]));
                trace[next.to] = curr.to;
            }
        }}
    }
    System.out.println(dist[1]);

    // LIFO
    Stack<Integer> st = new Stack<Integer>();
    st.push(1);
    st.push(trace[1]);
    int last = trace[1];
    while (last != 1) {
        last = trace[last];
        st.push(last);
    }
    while (!st.isEmpty()) {
        System.out.print(st.pop() + " ");
    }
}
Lowest Common Ancestor

LCA

N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력

LCA는 두 노드 간의 경로 길이 나 촌수 계산 등에 활용

Native 구현

  • depth가 큰 것을 depth가 같을 때 까지(낮은것으로) 맞춰준다
  • 두 정점이 만날 때까지 두 정점을 부모로 이동한다
  • O(N*M) N: 노드 수, M: query 수
dfs(int curr, int depth) {
    depths[curr] = depth;
    visited[curr] = 1;
    
    for (int next : adj.get(curr)) {
        
        if (visited[next] == 0) {
            dfs(next, depth + 1);
            parents[next] = curr;
            
        }
    }
}

depth와 parent 를 맞춰준다

int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());

if (depths[u] < depths[v]) {
    int t = u;
    u = v;
    v = t;
}
while (depths[u] != depths[v]) {
    u = parents[u];
}
while (u != v) {
    u = parents[u];
    v = parents[v];
}
System.out.println(u);

DP 구현

tree가 depth를 맞추는 것과 parent를 맞추는 과정을 빠르게 해보자

parents[u][k] 정점 u의 2^k 번째 부모 정의

parents[u][k] = parent[parent[u][k-1]][k-1]

depth diff가 3 이라면 이진 수로 011(2) 이고 parents[parents[u][0]][1] 으로 u를 맞춰준다.

int dist = depths[u] - depths[v];
int cnt = 0;
while (dist > 0) {
    if (dist % 2 == 1)
        u = parents[u][cnt];
    dist /= 2; // or dist >>= 1
    cnt++;
}

다른 방법으로는, 최대 MAX 로 부터 모두 체크해본다

for (int j = MAX; j >= 0; j--) {
    if (depths[v] <= depths[parents[u][j]]) {
        u = parents[u][j];
    }
}

depth가 같으면 이제 parent를 맞춘다

parents가 같다면

if (u != v) {
    for (int j = MAX; j >= 0; j--) {
        if (parents[u][j] != parents[v][j]) {
            u = parents[u][j];
            v = parents[v][j];
        }
    }
    u = parents[u][0];
}

구간 트리로 구현

  1. tree path를 만든다 dfs visited count 로 경로를 만들고 back할 때도 추가해야한다. 1->2->3->2->4 ….

  2. node가 표현된 tree path에서 몇번째 node 인가 늘어나는 path 크기를 담으면 된다

  3. query로 얻은 최소값은 (트리에서의 몇번째 node) 실제 어떤 노드인가? 1번에서의 visited count 에 해당하는 node를 저장하면됨

  • u를 포함하는 서브 트리에서 v를 포함하는 서브트리로 넘어가려면 LCA(u,v) 를 거쳐야만한다.

  • LCA(u,v) 에서 그 부모노드로 올라가려면 그전에 LCA(u,v) 를 루트로하는 서브트리를 모두 돌아본 후이어야한다. 즉 LCA(u,v) 의 조상노드를 u, v가 방문하는 일은 없다

  • 전위 순회를 통해 노드의 새로운 번호를 부여한다. 상위에 있는 노드 일 수록 더 작은 번호를 갖게하고 (방문하는 순서대로 번호 부여)
  • (중요) 순회 경로는 한번식 내려가고 한번씩 올라온다 n-1개 연결이 있으므로 2n-2번 움직이며, 전체 경로는 2n-1 번 (루트는 1번)
  • u와 v의 최상위 노드(최소값)는 u와 v의 최소 공통 조상이다

전위 순회를 통해 노드에 새로운 번호를 부여하고 구간트리에 이용할 1차원 배열을 만듦

void traverse(int here, int d, vector<int> &trip)
{
    no2serial[here] = nextSerial;
    serial2no[nextSerial] = here;
    nextSerial++;
    visitied[here] = true;
 
    depth[here] = d;
    locInTrip[here] = trip.size();
    trip.push_back(no2serial[here]);
 
    for(int i=0; i<graph[here].size(); i++){
        if(!visitied[graph[here][i]]){
          traverse(graph[here][i], d+1, trip);
          trip.push_back(no2serial[here]);
        }
    }
}
 
int LCA(int u, int v)
{
    int lu = locInTrip[u];
    int lv = locInTrip[v];
 
    if(lu > lv) swap(lu, lv);
    return serial2no[query(lu,lv,1,0,2*N-2)];
}
연속합

연속합

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답

D[n]: n 까지의 가장 큰 합

2가지 경우존재한다. 현재 값을 더하는 경우는 현재까지의 값을 더한 값이 최대일 때와 현재값을 더한 값이 최대일 때.

dp 값 중 최대 값을 출력하면 된다.

d[n] = max(arr[n], d[n-1] + arr[n])

int max = arr[0];

for (int i = 1; i < N; i++) {
    d[i] = Math.max(arr[i], d[i - 1] + arr[i]);
    if (d[i] > max) {
        max = d[i];
    }
}
System.out.println(max);
동전 교환

동전 교환

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. (각각의 동전은 몇개라도 사용할 수 있다.)

이전의 제곱 수의 합 문제와 비슷하다. 모든 동전을 다 볼 수 밖에 없다.

d[n] = min(d[n], d[n - coins[i]] + 1)

d[0] = 0;
for (int i = 0; i < N; i++) {
    for (int j = coins[i]; j <= K; j++) {
        d[j] = Math.min(d[j], d[j - coins[i]] + 1);
    }
}

유사문제 풀어보기

© 2017 yoonkiss. All rights reserved.