골드에그

1. 문제요약

코딩테스트 연습 - 양과 늑대 | 프로그래머스 스쿨 (programmers.co.kr)

이진 트리에 양과 늑대가 배치되어 있다. 각 노드에 방문할 때마다 양과 늑대를 모두 모아 데리고 다닐 수 있고,

모은 양의 수보다 늑대의 수가 같거나 더 많아지면, 양이 모두 잡아먹힌다. 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아 다시 루트 노드로 돌아오려 할 때, 최대로 모을 수 있는 양의 수를 구하라.

2. 문제예제

아래 접은 글을 확인해서 트리 노드를 어떻게 방문하는지 확인하면 된다.

3. 팩트추출

Fact 1 : 최대한 양을 많이 모아야 하므로 DFS 를 생각할 수 있다. 그런데 한 번 방문했던 자식 노드도 다시 탐색해야 하므로 일반적인 DFS 알고리즘과 다르다. 2번 문제 예제를 예로 들면, 0 => 1 노드로 탐색 실패했지만, 0 => 2 방문 후 1번 노드로 다시 방문할 수 있기 때문에 DFS 경로와는 다르다. 직접 탐색 리스트를 만들어 주어야 한다. 아래 Fact 2 번에서 자세히 다룬다.

Fact 2 : 현재 노드에서 갈 수 있는 경로를 정리해보자면, 아래 자식 노드들 뿐만 아니라 형제 노드의 자식 노드까지 가능하다. (거의 완전 탐색...) 일반적인 DFS 알고리즘은 다음 탐색할 노드가 자식 노드로 고정되어 있기 때문에 형제 노드를 가지고 오려면 부모 노드로부터 받아와야 한다. 탐색 실패해서 다시 부모노드로 돌아가더라도 갈 수 있는 모든 경로를 기억해야 한다. 부모 노드로부터 자식 노드의 경로들을 받아 그 리스트를 계속해서 전달해준다면 모든 탐색이 가능하다.

"경로" 를 인자로 주고 그 경로에서 뽑아 다음 방문할 지역을 선택하면 원래 DFS 경로 중간에 다른 경로를 추가로 검색할 수 있게 되는 트릭이 생긴다.

이 예제로 설명을 해보자면, 오른쪽 트리에서 DFS 를 수행하다가 자식 노드 끝까지 마저 탐색하지 않고 왼쪽 트리로 방문한다. 이렇게 해도 정보가 꼬이지 않는 이유는 부모 노드로부터 정보를 받은 것은 재활용할 수 있기 때문이다. DFS 이기 때문에 또 트리(순환하지 않는 그래프)이기 때문에 같은 정보를 공유하는 다른 형제노드부터 탐색이 가능한 것이다. 

Fact 3 : 부모 노드에서 자식 노드들을 탐색 리스트에 넣고 그 리스트가 삭제가 되지 않고 계속 추가되므로 자신의 노드가 리스트에 계속 살아있을 수 있다. 따라서 자기 자신은 경로 리스트에서 제외해야 한다.

4. 문제전략

팩트추출에서 소개한 DFS 변형 알고리즘을 사용해서 문제를 푼다.

5. 소스코드

import java.util.*;

class Solution {
    private static int answer;
    private static final List<List<Integer>> GRAPH = new LinkedList<>();

    public int solution(int[] info, int[][] edges) {
        answer = 0;
        for (int i = 0; i < info.length; i++) {
            GRAPH.add(new LinkedList<>());
        }

        for (int[] edge : edges) {
            GRAPH.get(edge[0]).add(edge[1]);
        }

        final List<Integer> next = new LinkedList<>();
        next.add(0);

        dfs(info, next, 0, 0, 0);

        return answer;
    }

    private void dfs(int[] info, List<Integer> list, int node, int sheep, int wolf) {
        if (info[node] == 0) {
            sheep += 1;
        } else {
            wolf += 1;
        }

        if (sheep <= wolf) {
            return;
        }

        answer = Math.max(answer, sheep);

        List<Integer> next = new ArrayList<>(list);
        if (!GRAPH.get(node).isEmpty()) {
            next.addAll(GRAPH.get(node));
        }
        next.remove(Integer.valueOf(node));

        for (int n : next) {
            dfs(info, next, n, sheep, wolf);
        }
    }
}

1. 문제요약

코딩테스트 연습 - 등산코스 정하기 | 프로그래머스 스쿨 (programmers.co.kr)

출입구에서 산봉우리까지 갔다가 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 한다.

등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity 라고 할 때 이 intensity 가 가장 짧은 코스를 찾아라. (등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 한다.)

2. 문제예제

등산코스를 1-2-4-5-6-4-2-1 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같다.

각 경로의 가중치가 가장 큰 값이 3 이며, 이 보다 intensity가 낮은 등산코스는 없다.

3. 팩트추출

Fact 1 : Dijkstra 다이젝스트라 알고리즘처럼 항상 최단 거리를 선택한다면, 경로의 intensity 배열은 항상 단조 증가 형태이다. 이 점을 활용하면 출발점에서 산봉우리까지 갔다가 다시 출발점으로 돌아오지 않아도 된다. 출발점에서 산봉우리까지 가는 반쪽짜리 최단 경로만 찾으면 된다. 출발 경로와 회귀 경로가 틀릴 수 있을지 언정 intensity 는 같을 것이기 때문이다. 이 문제에서는 경로를 구하라고 하지 않았으므로 가능하다. => 따라서 큐에 꺼낸 위치가 산봉우리라면 탐색을 종료한다.

Fact 2 : Fact 1 과 마찬가지로 경로를 구하라고 하지는 않았으므로, 출발점에서 동시에 출발하여 intensity 배열을 수정하여도 상관이 없다. 문제에서 요구하는 정답은 산봉우리와 그 산봉우리의 intensity 이다. 그러니까 어느 출발점에서 출발하여도 도착지점의 intensity 가 최소가 되는 경로만 찾으면 된다. 따라서 우선순위 큐에 출발지점을 모두 넣어놓고 시작한다.

Fact 3 : 일반적인 Dijkstra 다이젝스트라 알고리즘과 다른 점은 각 지점의 비용을 합한 거리가 최소가 되는 경로를 찾는 것이 아니라 각 구간의 최대 비용이 최소가 되는 경로를 찾는 것이다. 따라서 아래와 같이 로직을 수정한다.

if(dist[adjNode.to] > curNode.weight + adjNode.weight){
	dist[adjNode.to] = curNode.weight + adjNode.weight;
}

↓↓↓↓↓↓

if (dist[adjNode.to] > Math.max(curNode.weight, adjNode.weight)) {
	dist[adjNode.to] = effort;
}

Fact 4 : 산봉우리까지 가는 intensity 가 같은 경로가 여러 개라면, 산봉우리의 번호가 가장 작은 것을 반환하라고 지문에서 나와있으므로 산봉우리-intensity 배열에서 최소값을 찾을 때 산봉우리 배열을 먼저 정렬해야 한다.

4. 문제전략

팩트추출에서 소개한 다이젝스트라 변형 알고리즘을 사용하면 된다.

5. 소스코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {
    static class Node implements Comparable<Node> {
        int index;
        int effort;
        public Node(int index, int effort) {
            this.index = index;
            this.effort = effort;
        }
        @Override
        public int compareTo(Node o) {
            return this.effort - o.effort;
        }
    }
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int[] efforts;
    static int[] gatesSave, summitsSave;
    private static void initGraph(int v, int[][] data) {
        for(int i=0; i < v+1; i++){
            graph.add(new ArrayList<>());
        }
        for (int[] datum : data) {
            graph.get(datum[0]).add(new Node(datum[1], datum[2]));
            graph.get(datum[1]).add(new Node(datum[0], datum[2]));
        }
        efforts = new int[v+1];
        for (int i = 1; i < v+1; i++) {
            efforts[i] = Integer.MAX_VALUE;
        }
    }

    private static int[] dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        // 시작지점 삽입
        for (int gate : gatesSave) {
            pq.offer(new Node(gate, 0));
            efforts[gate] = 0;
        }

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            if (isSummit(curNode.index))
                continue;
            if (efforts[curNode.index] < curNode.effort) {
                continue;
            }
            for (Node adjNode : graph.get(curNode.index)) {
                int effort = (adjNode.effort == Integer.MAX_VALUE) ? curNode.effort : Math.max(curNode.effort, adjNode.effort);
                if (efforts[adjNode.index] > effort) {
                    efforts[adjNode.index] = effort;
                    pq.offer(new Node(adjNode.index, efforts[adjNode.index]));
                }
            }
        }

        Arrays.sort(summitsSave);
        int index = -1;
        int minEffort = Integer.MAX_VALUE;
        for (int summit : summitsSave) {
            if (efforts[summit] < minEffort) {
                minEffort = efforts[summit];
                index = summit;
            }
        }
        return new int[]{index, minEffort};
    }

    private static boolean isSummit(int num) {
        for (int summit : summitsSave) {
            if (num == summit) return true;
        }
        return false;
    }

    public static int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        gatesSave = gates;
        summitsSave = summits;
        initGraph(n, paths);
        return dijkstra();
    }
}

1. 문제요약

11658번: 구간 합 구하기 3 (acmicpc.net)

N×N 크기의 표에 숫자들이 채워져 있다. 수의 변경이 빈번히 일어나고 연속 구간에 대한 부분합을 구하려고 한다.

2. 문제예제

3. 팩트추출

Fact 1 : 비슷한 문제인 10999번: 구간 합 구하기 2 (acmicpc.net) 와 다른 부분은 2차원 배열에서 수정 및 조회하며 구간 업데이트가 아니라 한 곳만 업데이트한다는 점이다. 연속된 공간의 연산이므로 세그먼트 트리와 펜윅 트리 모두 가능하다. 펜윅 트리에 대한 자세한 내용은 아래 블로그 글을 참고한다.

펜윅 트리 (바이너리 인덱스 트리) (acmicpc.net)

Fact 2 : 펜윅 트리를 2차원 배열에 적용하면 행과 열 모두 값이 업데이트된다. 맵 전체에 그 해당 인덱스가 필요하는 구간들이 업데이트된다. 예를 들어 map[0][0] 에 해당하는 부분이 펜윅 트리 맵에 저장될 때 다음과 같다.

map[0][0] 이 펜윅트리 tree[x][y] 에 저장될 때의 모습이다. 0 번째 인덱스이기 때문에 0번, 1번, 3번 인덱스 구간합에 모두 저장되는 것을 볼 수 있다.

4. 문제풀이(수동)

문제 예제 입력 1번 map 을 펜윅 트리(tree)에 저장하면 아래와 같다.

여기서 만약 (2, 2) 부터 (3, 4) 까지 구간합을 구하고 싶다면 아래 공식과 같이 전체 사각형에서 변두리 사각형 부분들을 빼주면 된다. 이 때 중복으로 제거한 부분을 다시 한 번 더해주어야 한다.

sum(3, 4) - sum(3, 2-1) - sum(2-1, 4) + sum(2-1, 2-1)

= 27

5. 문제전략

문제 전략은 팩트 추출과 문제풀이(수동) 을 통해 알아보았다. 펜윅 트리방식으로 문제를 풀었다.

6. 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[][] inputArray;
    static int[][] fenwickTree;

    private static void update(int x, int y, int val) {
        while(x <= N){
            int yIndex = y;
            while(yIndex <= N) {
                fenwickTree[x][yIndex] += val;
                yIndex += yIndex & -yIndex;
            }
            x += x & -x;
        }
    }

    private static int sum(int x, int y) {
        int result = 0;
        while(x > 0){
            int yIndex = y;
            while(yIndex > 0) {
                result += fenwickTree[x][yIndex];
                yIndex -= yIndex & -yIndex;
            }
            x -= x & -x;
        }
        return result;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        inputArray = new int[N+1][N+1];
        fenwickTree = new int[N+1][N+1];

        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) {
                inputArray[i][j] = Integer.parseInt(st.nextToken());
                update(i, j, inputArray[i][j]);
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int operation = Integer.parseInt(st.nextToken());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            if(operation == 1) {
                int x2 = Integer.parseInt(st.nextToken());
                int y2 = Integer.parseInt(st.nextToken());
                sb.append((sum(x2, y2) - sum(x2, y1-1) - sum(x1-1, y2) + sum(x1-1,y1-1))+"\n");
            }else {
                int change = Integer.parseInt(st.nextToken());
                update(x1, y1, change - inputArray[x1][y1]);
                inputArray[x1][y1] = change;
            }
        }
        System.out.println(sb.toString());
    }
}

1. 문제요약

1520번: 내리막 길 (acmicpc.net)

지도의 각 칸에는 그 지점의 높이가 주어지며 (0, 0) 지점에서 (n-1, m-1) 지점으로 내려가려고 한다. 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 할 때 이동할 수 있는 경로의 수를 구하시오.

2. 문제예제

3. 팩트추출

Fact 1 : 전형적인 BFS 와 DFS 문제인 것처럼 보이지만, 입력의 범위를 보면 완전 탐색 시 시간 초과가 발생할 수 있다. 최대 칸 수가 500 * 500 으로 250000 이며 상하좌우 4방향으로 움직일 수 있으니 4 의 250000 제곱 경우의 수가 존재한다. 경우의 수를 줄일 수 있는 방법을 찾아야 한다.
 

Fact 2 : 문제 예제를 살펴보면 전체 문제의 답이 작은 부분 문제의 답의 합으로 구성되어 있다. 50 번 지점에서 목적지까지 가는 경로의 수는 45번 지점에서 가는 경로의 수 + 35번 지점에서 가는 경로의 수로 이루어져 있다. 35번 지점이나 30번 지점, 27번 지점은 경로의 수가 하나로 나중에 이 지점을 방문하더라도 계산할 필요가 없다. 즉 DP 문제이다.

Fact 3 : 기존 DFS 나 BFS 에서 사용하던 visited 배열을 응용하여 "해당 지점에서 목적지까지 가는 경로의 수" 로 생각하여 해당 값을 재활용하면 탐색 범위를 줄일 수 있다. 여기서 중요한 점은 DFS 와 BFS 의 visited 배열 활용도가 조금 다르다는 것이다. BFS 는 주변부터 탐색하기 때문에 단순 방문했는지 여부만 파악할 수 있지만 DFS 는 한 가지 경우의 수부터 모두 탐색하고 다시 원래 위치로 돌아오기 때문에 수행 도중 visited 배열을 오염시킨다면 그 경로는 다시 탐색하지 않아도 된다. 4 번 문제 풀이 (수동) 부분에서 자세히 확인한다.

Fact 4 : DP[x][y] 배열을 0 으로 초기화하면 이 경로의 수가 0 인지 노드를 방문하지 않은 것인지 확인이 불가능하다. DP 배열이 visited 배열의 역할도 하기 때문에 -1 로 초기화한다.

4. 문제풀이(수동)

문제 예제 입력 1을 DFS 알고리즘 + DP 방식으로 문제를 풀었을 때 애니메이션이다.

손수 애니메이션으로 만들어준 우투리와툴툴 티스토리 블로그님께 감사의 말씀을 전한다. 덕분에 이해하기가 쉽다.

5. 문제전략

문제 전략은 팩트 추출을 통해 알아보았다. DFS + DP 방식으로 문제를 풀었다.

6. 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int M, N;
    static int[][] map;
    static int[][] dp;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        map = new int[M][N];
        dp = new int[M][N];

        for(int j = 0; j < M; j++) {
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                map[j][i] = Integer.parseInt(st.nextToken());
            }
        }
        initDP();
        System.out.println(dfs(0, 0));
    }
    private static void initDP() {
        for(int j = 0; j < M; j++) {
            for (int i = 0; i < N; i++) {
                dp[j][i] = -1;
            }
        }
    }
    private static int dfs(int x, int y) {
        if(x == M-1 && y == N-1){ return 1; }
        if(dp[x][y] != -1) return dp[x][y];

        dp[x][y] = 0;
        for (int i=0; i<4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (newX < 0 || newX >= M || newY < 0 || newY >= N) continue;
            if (map[x][y] <= map[newX][newY]) continue;

            dp[x][y] += dfs(newX, newY);
        }
        return dp[x][y];
    }
}

1. 문제요약

10999번: 구간 합 구하기 2 (acmicpc.net)

어떤 연속된 N개의 수가 있다. 수의 변경이 빈번히 일어나고 연속 구간에 대한 부분합을 구하려고 한다.

2. 문제예제

3. 팩트추출

Fact 1 : 연속된 1차원 공간에서 내부에 있는 값들이 수시로 변경되고 연속 부분 구간에 대한 연산을 수행하기 때문에 세그먼트 트리를 생각해볼 수 있다. (내부 값들이 수시로 변경되기 때문에 부분합 자료구조 불가능)
 

Fact 2 : 비슷한 문제인 2042번: 구간 합 구하기 (acmicpc.net) 와 다른 부분은 업데이트 부분이 "구간" 이라는 점이다. 2042 문제같은 경우 단일 지점만 업데이트 되기 때문에 한 번 쿼리 수행 시 시간복잡도가 O(Q * lgN) 이 되지만, 이 문제의 경우 구간 전체를 업데이트 해야 되기 때문에 한 번 쿼리 수행 시 시간복잡도가 O(Q * MlgN) 이 된다. (여기서 M은 구간의 길이) 일반적인 세그먼트 트리를 사용할 경우 시간 초과가 발생할 수 있다.

Fact 3 :  lgN 트리 길이만큼 매번 연산하지 말고, 업데이트나 조회 시 해당 구간이 필요하면 변수를 하나 두어 해당 변수에 업데이트하고 다음 번에 도착했을 때 한 단계씩 자식에게 값을 늦게 전파하면 연산을 획기적으로 줄일 수 있다. 이러한 방법을 Lazy Propagation 이라고 한다. 자세한 내용은 다음 글을 참고하자.

[알고리즘] Segment Tree :: 골드에그 (tistory.com)

4. 문제풀이(수동)

(...생략...)

5. 문제전략

문제 전략은 팩트 추출을 통해 알아보았다. Segment Tree 와 Lazy Propagation 을 활용하여 문제를 풀었다.

6. 소스코드

import java.io.*;
import java.util.StringTokenizer;

class Main {
    static int n;
    static long[] elements;
    static class SegmentTree {
        static class Node {
            long value;
            long lazy;
            Node leftChild, rightChild;
        }

        static Node getNode() {
            Node temp = new Node();
            temp.value = 0;
            temp.lazy = 0;
            temp.leftChild = null;
            temp.rightChild = null;
            return temp;
        }

        static void updateLazy(Node node, int left, int right) {
            // 만약 현재 노드에 lazy 값이 있다면
            if (node.lazy != 0) {
                // 만약 자식이 있다면 자식들에게 lazy 값을 전파한다.
                if (node.leftChild != null) {
                    node.leftChild.lazy += node.lazy;
                }
                if (node.rightChild != null) {
                    node.rightChild.lazy += node.lazy;
                }
                // 현재노드 업데이트 ( 부모노드이므로 구간 길이만큼 업데이트 )
                node.value += node.lazy * (right - left + 1);
                // lazy 값을 업데이트했으므로 0으로 만들어준다.
                node.lazy = 0;
            }
        }

        // 초기화
        private static void initTree(Node node, int index, long updateValue, int left, int right) {
            // 기저사례 (구간에 index 가 없는 경우)
            if (index < left || index > right)
                return;

            // 기저사례 (마지막 구간에 index 가 있는 경우 (수정할 필요 없는 경우))
            // 초기화 과정이 없기 때문에 필요
            if (left == right) {
                node.value = updateValue;
                return;
            }

            int mid = left + (right - left) / 2;
            long leftSum = 0, rightSum = 0;

            if (index <= mid) {
                if (node.leftChild == null) {
                    node.leftChild = getNode();
                }
                initTree(node.leftChild, index, updateValue, left, mid);
            } else {
                if (node.rightChild == null) {
                    node.rightChild = getNode();
                }
                initTree(node.rightChild, index, updateValue, mid + 1, right);
            }

            if (node.leftChild != null)
                leftSum = node.leftChild.value;
            if (node.rightChild != null)
                rightSum = node.rightChild.value;
            node.value = leftSum + rightSum;
        }

        private static void updateRange(Node node, long updateValue, int updateStart, int updateEnd, int left, int right) {
            updateLazy(node, left, right);
            // 기저사례 (구간에 쿼리구간이 없는 경우)
            if (updateEnd < left || updateStart > right)
                return;

            // 기저사례 (업데이트 구간이 완전히 포함되는 경우)
            if (updateEnd >= right && updateStart <= left) {
                node.value += (updateValue * (right - left + 1));
                if (node.leftChild != null) {
                    node.leftChild.lazy += updateValue;
                }
                if (node.rightChild != null) {
                    node.rightChild.lazy += updateValue;
                }
                return;
            }

            int mid = left + (right - left) / 2;
            updateRange(node.leftChild, updateValue, updateStart, updateEnd, left, mid);
            updateRange(node.rightChild, updateValue, updateStart, updateEnd, mid + 1, right);
            node.value = node.leftChild.value + node.rightChild.value;
        }

        static long query(Node node, int queryStart, int queryEnd, int left, int right) {
            updateLazy(node, left, right);
            // 기저사례 (할당되지 않은 경우)
            if (node == null)
                return 0;

            // 기저사례 (구간에 쿼리구간이 없는 경우)
            if (queryEnd < left || queryStart > right)
                return 0;

            // 기저사례 (쿼리 구간이 완전히 포함되는 경우)
            if (queryEnd >= right && queryStart <= left) {
                return node.value;
            }

            int mid = left + (right - left) / 2;
            return query(node.leftChild, queryStart, queryEnd, left, mid) + query(node.rightChild, queryStart, queryEnd, mid + 1, right);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        elements = new long[n];
        for(int i=0; i<n; i++) {
            elements[i] = Long.parseLong(br.readLine());
        }

        SegmentTree.Node root = new SegmentTree.Node();

        for (int i=0; i<elements.length; i++)
            SegmentTree.initTree(root, i+1, elements[i], 1, n);

        for(int i=0; i<m+k; i++) {
            st = new StringTokenizer(br.readLine());
            int operation = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            if(operation == 1) {
                long updateValue = Long.parseLong(st.nextToken());
                SegmentTree.updateRange(root, updateValue, left, right, 1, n);
            }else {
                bw.write(SegmentTree.query(root, left, right, 1, n)+"\n");
            }
        }
        bw.flush();
        bw.close();
    }
}

1. Segment Tree

값이 변하는 연속 구간에 대한 정보를 저장할 때 사용하는 자료구조이다.

값이 변하지 않는다면 구간합을 한 번 연산하고, 계속 질의하면서 쿼리에 대한 결과값을 가져오면 되는데 중간에 있는 값이 변하게 된다면 다시 구간합을 구해야 하므로 O(N) 시간만큼 시간 복잡도가 발생하게 된다. 그래서 조회, 수정 시에도 O(lgN) 시간만큼 줄일 수 있는 자료구조가 필요했다.

일반적인 세그먼트 트리는 입력되는 값 범위의 트리 높이만큼 계산하기 때문에 (N개의 원소가 있을 때 구현에 따라) 2배에서 4배정도의 추가 공간이 필요하지만 원소의 변경, 특정 범위 내의 연산을 logN 에 수행할 수 있다는 장점이 있다.

데이터 관점에서 보면 트리는 아래처럼 구성된다.

인덱스 관점에서 보면 트리는 아래처럼 구성된다.

트리의 인덱스가 0 이 아닌 1 인 이유는 1 부터 시작할 때 좌측부터 차례로 인덱스를 부여하면 아래 공식이 성립한다.

좌측 노드 인덱스 = 부모 노드 인덱스 * 2 (짝수)

우측 노드 인덱스 = 부모 노드 인덱스 * 2 + 1 (홀수)

반대로, 데이터는 1번 노드부터 전체 구간의 합이 적재되고, 내려오면서 반씩 범위가 쪼개져 그 구간의 합이 표시된다.

이진 탐색 트리 연산이므로 Top-Down 방식으로 이분할하여 데이터를 수정하고 조회하면 된다.

<템플릿>

class SegmentTree {
    static long[] tree;
    int treeSize;

    public SegmentTree(int arrSize){
        int h = (int) Math.ceil(Math.log(arrSize)/ Math.log(2));
        this.treeSize = (int) Math.pow(2,h+1);
        tree = new long[treeSize];
    }

    // 초기화와 수정을 update 에서 동시에
    static void update(int node, int index, int updateValue, int left, int right) {
        // 기저사례 (구간에 index 가 없는 경우)
        if (index < left || index > right)
            return;

        // 기저사례 (마지막 구간에 index 가 있는 경우)
        if (left == right) {
            tree[node] = updateValue;
        }

        tree[node] += updateValue;
        int mid = left + (right - left) / 2;
        update(node * 2, index, updateValue, left, mid);
        update(node * 2 + 1, index, updateValue, mid+1, right);
    }

    static void long query(int node, int startIndex, int endIndex, int left, int right){
        // 기저사례 (구간에 쿼리구간이 없는 경우)
        if (endIndex < left || startIndex > right)
            return 0;

        // 기저사례 (마지막 구간에 index 가 있는 경우)
        if (endIndex >= right && startIndex <= left) {
            return tree[node];
        }

        int mid = left + (right - left) / 2;
        return query(node*2, startIndex, endIndex, left, mid) + query(node*2 + 1, startIndex, endIndex, mid+1, right);
    }
}

2. Dynamic Segment Tree

일반적인 세그먼트 트리는 보통 입력 범위의 4배에 달하는 공간을 미리 할당한 후, 모두 업데이트한다. (위 세그먼트 트리 참고) 입력의 범위만큼 모든 영역(logN)을 업데이트해야 하며, 사용하지 않는 공간까지 낭비한다는 단점이 있다.

반면, Dynamic Segment Tree 는 이름에서도 알 수 있듯이 노드가 필요할 때만 생성해서 만들기 때문에 공간을 낭비하지 않는다. 값을 없데이트할 때 mid 노드의 자식 노드가 없는 경우 노드를 동적으로 생성해준다는 점이 다르다. 구간에 대한 쿼리 로직은 자식이 없는 경우만 예외처리해주면 일반적인 세그먼트 트리와 동일하다.

<템플릿>

static class SegmentTree {
    static class Node {
        long value;
        Node leftChild, rightChild;
    }

    static Node getNode() {
        Node temp = new Node();
        temp.value = 0;
        temp.leftChild = null;
        temp.rightChild = null;
        return temp;
    }

    static void initTree(Node node, int index, long updateValue, int left, int right) {
        // 기저사례 (구간에 index 가 없는 경우)
        if (index < left || index > right)
            return;

        // 기저사례 (마지막 구간에 index 가 있는 경우 (수정할 필요 없는 경우 값 셋팅))
        // 초기화 과정이 없기 때문에 필요
        if (left == right) {
            node.value = updateValue;
            return;
        }

        int mid = left + (right - left) / 2;
        long leftSum = 0, rightSum = 0;

        if (index <= mid) {
            if (node.leftChild == null) {
                node.leftChild = getNode();
            }
            update(node.leftChild, index, updateValue, left, mid);
        } else {
            if (node.rightChild == null) {
                node.rightChild = getNode();
            }
            update(node.rightChild, index, updateValue, mid+1, right);
        }

        if (node.leftChild != null)
            leftSum = node.leftChild.value;
        if (node.rightChild != null)
            rightSum = node.rightChild.value;
        node.value = leftSum + rightSum;
    }

	static void updateRange(Node node, long updateValue, int updateStart, int updateEnd, int left, int right) {
        // 기저사례 (구간에 쿼리구간이 없는 경우)
        if (updateEnd < left || updateStart > right)
            return;

        int mid = left + (right - left) / 2;
        updateRange(node.leftChild, updateValue, updateStart, updateEnd, left, mid);
        updateRange(node.rightChild, updateValue, updateStart, updateEnd, mid + 1, right);
        node.value = node.leftChild.value + node.rightChild.value;
    }
        
    static void int query(Node node, int startIndex, int endIndex, int left, int right){
        // 기저사례 (할당되지 않은 경우)
        if (node == null)
            return 0;
        // 기저사례 (구간에 쿼리구간이 없는 경우)
        if (endIndex < left || startIndex > right)
            return 0;

        // 기저사례 (마지막 구간에 index 가 있는 경우)
        if (endIndex >= right && startIndex <= left) {
            return node.value;
        }

        int mid = left + (right - left) / 2;
        return query(node.leftChild, startIndex, endIndex, left, mid) + query(node.rightChild, startIndex, endIndex, mid+1, right);
    }
}

3. Dynamic Segment Tree (+ Lazy Propagation)

( 아무리 구글에 검색해봐도 메모리를 절약할 수 있는 Dynamic Segment Tree 와 연산을 줄이는 Lazy Propagation 을 같이 사용하는 코드가 없었다... 특히 Java 는 더욱 없었다. 그래서 내가 쓰려고 템플릿을 만들었다. )

Dynamic Segment Tree 에서 값을 업데이트할 때 자식노드들도 모두 변경하는데 굳이 지금 당장 자식노드의 조회나 수정이 필요 없는 경우라면 트리를 순회하면서 업데이트할 필요는 없다. lazy 라는 변수를 하나두고, 그 변수에 업데이트할 변수를 저장한 다음 나중에 조회하거나 수정할 때 한 단계씩 자식에게 전파하면 된다. 그래서 이름이 느린 전파이다.

업데이트 하고자 하는 범위를 updateStart, updateEnd 라고 할 때, 자식노드를 순회하면서 left, right 탐색 범위가 업데이트 하고자 하는 범위에 완전히 포함된다면 자식노드를 방문하지 않고 lazy 값만 자식노드에게 전파한뒤 종료한다. 자식 노드들을 방문하지 않는다.

<템플릿>

static class SegmentTree {
    static class Node {
        long value;
        long lazy;
        Node leftChild, rightChild;
    }

    static Node getNode() {
        Node temp = new Node();
        temp.value = 0;
        temp.lazy = 0;
        temp.leftChild = null;
        temp.rightChild = null;
        return temp;
    }

    static void updateLazy(Node node, int left, int right) {
        // 만약 현재 노드에 lazy 값이 있다면
        if (node.lazy != 0) {
            // 만약 자식이 있다면 자식들에게 lazy 값을 전파한다.
            if (node.leftChild != null) {
                node.leftChild.lazy += node.lazy;
            }
            if (node.rightChild != null) {
                node.rightChild.lazy += node.lazy;
            }
            // 현재노드 업데이트 ( 부모노드이므로 구간 길이만큼 업데이트 )
            node.value += node.lazy * (right - left + 1);
            // lazy 값을 업데이트했으므로 0으로 만들어준다.
            node.lazy = 0;
        }
    }

    // 초기화
    static void initTree(Node node, int index, long updateValue, int left, int right) {
        // 기저사례 (구간에 index 가 없는 경우)
        if (index < left || index > right)
            return;

        // 기저사례 (마지막 구간에 index 가 있는 경우 (수정할 필요 없는 경우))
        // 초기화 과정이 없기 때문에 필요
        if (left == right) {
            node.value = updateValue;
            return;
        }

        int mid = left + (right - left) / 2;
        long leftSum = 0, rightSum = 0;

        if (index <= mid) {
            if (node.leftChild == null) {
                node.leftChild = getNode();
            }
            initTree(node.leftChild, index, updateValue, left, mid);
        } else {
            if (node.rightChild == null) {
                node.rightChild = getNode();
            }
            initTree(node.rightChild, index, updateValue, mid + 1, right);
        }

        if (node.leftChild != null)
            leftSum = node.leftChild.value;
        if (node.rightChild != null)
            rightSum = node.rightChild.value;
        node.value = leftSum + rightSum;
    }

    static void updateRange(Node node, long updateValue, int updateStart, int updateEnd, int left, int right) {
        updateLazy(node, left, right);
        // 기저사례 (구간에 쿼리구간이 없는 경우)
        if (updateEnd < left || updateStart > right)
            return;

        // 기저사례 (업데이트 구간이 완전히 포함되는 경우)
        if (updateEnd >= right && updateStart <= left) {
            node.value += (updateValue * (right - left + 1));
            if (node.leftChild != null) {
                node.leftChild.lazy += updateValue;
            }
            if (node.rightChild != null) {
                node.rightChild.lazy += updateValue;
            }
            return;
        }

        int mid = left + (right - left) / 2;
        updateRange(node.leftChild, updateValue, updateStart, updateEnd, left, mid);
        updateRange(node.rightChild, updateValue, updateStart, updateEnd, mid + 1, right);
        node.value = node.leftChild.value + node.rightChild.value;
    }

    static long query(Node node, int queryStart, int queryEnd, int left, int right) {
        updateLazy(node, left, right);
        // 기저사례 (할당되지 않은 경우)
        if (node == null)
            return 0;

        // 기저사례 (구간에 쿼리구간이 없는 경우)
        if (queryEnd < left || queryStart > right)
            return 0;

        // 기저사례 (쿼리 구간이 완전히 포함되는 경우)
        if (queryEnd >= right && queryStart <= left) {
            return node.value;
        }

        int mid = left + (right - left) / 2;
        return query(node.leftChild, queryStart, queryEnd, left, mid) + query(node.rightChild, queryStart, queryEnd, mid + 1, right);
    }
}

Q . updateRange 와 Query 함수에서 updateLazy 를 가장 먼저 호출해야 되는 이유?

A . 해당 템플릿이 완성되기 전, 구간에 쿼리 구간이 없는 경우 updateLazy 를 할 필요가 없지 않나? 라고 생각했었다. 그래서 "기저사례 (구간에 쿼리구간이 없는 경우)" 로직 뒷 부분에 updateLazy 를 배치하고 최적화를 잘 했다며 만족했었다.

그런데, Lazy Propagation 의 대표문제인 백준 10999 문제를 풀어보니 모두 틀렸다고 나오는 것이었다. 게시판에서 언급하고 있는 반례 케이스들은 모두 맞았는데 안 되니까 답답할 노릇이었다. 잘 생각해보면 잘못된 생각이었다.

만약 부모 노드에 lazy 값이 있는데 자식 노드가 범위를 벗어난다면 lazy 를 전파받지 못하고 계산이 되기 때문이다. 꼭 query 와 update 할 때 updateLazy 를 먼저 호출하자.

1. 문제요약

9426번: 중앙값 측정 (acmicpc.net)

1차원 배열이 주어지고 길이가 K 인 연속 부분 수열에 대해, N-K+1 개의 중앙값의 합을 구하는 프로그램을 작성하시오.

수 K 개의 중앙값은 ((K+1)/2) 번째로 작은 숫자이다. 인덱싱은 1번 부터 시작하며, K가 홀수인 경우를 처리하기 위해 1을 더한다.

2. 문제예제

3. 팩트추출

Fact 1 : 길이가 K 인 모든 연속 부분 수열을 구해야 되므로 슬라이딩 윈도우를 생각할 수 있다.

양 옆에 있는 숫자들만 연산에 추가하고 중간 부분에 있는 값을 재사용할 수 있다면 슬라이딩 윈도우가 적합할 수 있다.

하지만, 이 문제같은 경우 숫자를 양 옆에서 가져와도 어느 것이 중앙 값인지 슬라이딩 윈도우로 K 배열을 가져올 때마다 K 길이만큼 탐색해야 구할 수 있다. 다시 말해 배열 중앙에 있는 값들을 재활용할 수 없다.
 

Fact 2 : 각 구간을 효율적으로 탐색할 수 있는 자료구조를 사용한다면 빠르게 계산할 수 있다. 세그먼트 트리가 대표적인 방식이다. 세그먼트 트리는 자신을 포함한 모든 구역에 대해 값을 업데이트한다는 특징과 부모 노드로 올라갈수록 구간의정보가 합쳐진다는 특징이 있다. 해당 문제에서는 중앙값을 찾고 싶어하므로 자식 노드를 몇 개 가지고 있는지 카운트 정보를 가지고 있다면 쉽게 계산할 수 있다.

지문에서 소개한 중앙값을 M = (K+1)/2 이라고 할 때, 아래와 같은 방법으로 탐색할 수 있다.

tree[node*2] >= M : 왼쪽 자식 트리가 M 보다 크므로 자신보다 작은 값이 나올 때까지 왼쪽 트리를 재귀탐색한다.

tree[node*2] < M : 왼쪽 자식 트리가 M 보다 작으므로 M 에서 왼쪽 형제 노드 갯수만큼 빼주고 (M-tree[node*2]) 오른쪽 트리를 재귀탐색한다.

Fact 3 : 트리에 주어진 배열을 모두 삽입할 필요는 없다. 슬라이딩 윈도우 방식처럼 트리에 하나씩 넣고 빼어 쿼리 결과 값을 가져온다.

4. 문제풀이(수동)

(출처 : [BOJ] 백준 9426번 중앙값 측정 (Java) (tistory.com))

K 배열 내부 값들인 3, 4, 5 값을 세그먼트 트리에 삽입하면 3 4 5 인덱스를 포함한 부모노드들은 각 아래 자식노드들이 몇 개 있는지 카운트 정보를 가지고 있게 된다. 이를 통해 어디로 탐색하는지 알 수 있게 된다.

먼저 중앙값을 계산하면, (k+1/2) 공식에 따라 k=2 가 된다. 왼쪽 자식은 1개 밖에 없으므로 오른쪽 자식 트리에 있다는 것을 알 수 있으며, 오른쪽 트리를 순회하면서 왼쪽 자식의 갯수만큼 빼주어 탐색을 하는 것을 볼 수 있다.

5. 문제전략

문제 전략은 팩트 추출을 통해 알아보았다. 슬라이딩 윈도우 기법으로 K 개 만큼 세그먼트 트리에 삽입하고 쿼리를 각각 수행한다.

6. 소스코드

( [BOJ] 백준 9426번 중앙값 측정 (Java) (tistory.com) 소스코드를 공부하고, 주석을 달았습니다. )

public class Main {
    static final int SIZE = 65536;
    static int[] arr, tree;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        arr = new int[n+1];
        for(int i=1; i<=n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        tree = new int[SIZE*4];
        // 1 번부터 k 직전까지 노드 삽입
        for(int i=1; i<k; i++) {
            update(0,SIZE,1,arr[i],1);
        }
        int prev = 1;
        int mid = (k+1)/2;
        long ans = 0;
        // k 부터 n 까지 노드 삽입하면서 중앙값을 계산하고, 슬라이딩 윈도우 기법으로 K 배열을 움직인다.
        for(int i=k; i<=n; i++) {
            update(0,SIZE,1,arr[i],1);
            ans += find(0,SIZE,1,mid);
            update(0,SIZE,1,arr[prev++],-1);
        }
        System.out.println(ans);
    }

    static int update(int start, int end, int node, int index, int diff) {
        // 기저사례 1 : 타겟 인덱스가 범위 밖인 경우, skip
        if(index < start || end < index) {
            return tree[node];
        }
        // 기저사례 2 : 타겟 인덱스 안에 있으면서 start == end 값이 같다면 index 지점에 도착했다는 뜻
        if(start == end) {
            return tree[node] += diff;
        }

        int mid = (start + end) / 2;
        // 좌측 의 카운트와 우측의 카운트를 합친 값이 부모 카운트
        return tree[node] = update(start, mid, node*2, index, diff)+update(mid+1, end, node*2+1, index, diff);
    }

    static int find(int start, int end, int node, int k) {
        if(start == end) {
            return start;
        }

        int mid = (start+end) / 2;
        if(tree[node*2] >= k) {
            return find(start, mid, node*2, k);
        } else {
            return find(mid+1, end, node*2+1, k-tree[2*node]);
        }
    }
}

1. 문제요약

2138번: 전구와 스위치 (acmicpc.net)

N개의 스위치와 N개의 전구가 있다. i (1 < i < N) 번 스위치를 누르면 i - 1, i, i + 1 의 세 개의 전구의 상태가 동시에 바뀐다.

(자기 자신을 포함해서 양 옆에 있는 전구가 동시에 바뀐다.) N개의 전구들 현재 상태와 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

2. 문제예제

3. 팩트추출

Fact 1 : 자기 자신의 스위치를 바꿀 수 있는 것은 양 옆에 있는 전구이다.

그런데 만약 0 ~ N - 1 까지 순차적으로 실행하게 된다면, 왼쪽에 있는 전구는 오른쪽 전구에 의해 바뀔 수 있으므로 사고 과정에서 생략할 수 있다. 오른쪽 전구로만 컨트롤하게 바꾼다면 이전 정보가 필요 없어지게 된다. 또 부분문제이기 때문에 그리디 알고리즘으로 풀 수 있다.

Fact 2 : i - 1 번째 전구만 보면서 타겟 전구와 같다면 넘기고, 다르다면 스위치를 누른다. 그런데 가장 첫 번째 전구는 눌러야 할지, 말아야 할지 결정할 수가 없기 때문에 두 가지 경우의 수 모두 구한다.

Fact 3 : i 가 마지막 N 위치까지 왔는데 타겟 전구의 상태와 다르다면, 도달할 수 없다는 뜻이고 같다면 최소의 경우의 수 이므로 count 를 반환한다. 이 전략이 항상 최선의 상태를 반환하는지는(최소 값을 보장하는지는) 아래 문제풀이(수동)을 통해 알아본다.

4. 문제풀이(수동)

그리디 알고리즘은 해당 전략이 항상 최선의 상태를 반환해주는지 검증해야 한다. 문제를 전구 배열 3 크기로 나누어서 생각해본다.

현재 전구 상태 : 010

목표 전구 상태 : 111

목표 전구 상태와 다른 부분을 보고 바로 킨다면 010 -> 100 -> 011 루틴으로 가장 첫 번째 전구를 못 키게 된다.

그 다음 인덱스에서 킨다면 101 -> 110 -> 111 로 안정적으로 킬 수 있게 된다.

현재 전구 상태 : 000

목표 전구 상태 : 111

중간에 있는 전구 하나만 키면 되는 것처럼 보이지만 그 다음 인덱스에서 키기 때문에 이 중간 문제도 해당 공식이 성립한다. 이처럼 3 전구 상태 배열의 모든 경우의 수를 나열하고 테스트 해보았을 때, 오른쪽에 있는 전구를 킬 때가 가장 올바른 선택이라는 것을 알 수 있다.

5. 문제전략

문제 전략은 예제 풀이(수동)과 팩트 추출을 통해 알아보았다.

6. 소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static int N;
    static char lightArray[][], targetArray[];
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        lightArray = new char[2][N];
        lightArray[0] = br.readLine().toCharArray();
        lightArray[1] = br.readLine().toCharArray();
        targetArray = br.readLine().toCharArray();
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }

    private static void run(int index, int count, int type) {
        if(index == N) {
            if(lightArray[type][index-1] == targetArray[index-1]) {
                answer = Math.min(answer, count);
            }
            return;
        }
        if(lightArray[type][index-1]!=targetArray[index-1]) {
            push(index,type);
            run(index+1,count+1,type);
        } else {
            run(index + 1, count, type);
        }
    }
    private static void push(int index, int type) {
        for(int i=index-1; i<=index+1; i++) {
            if(i>=0 && i<N)
                lightArray[type][i] = lightArray[type][i] == '1' ? '0' : '1';
        }
    }
}