골드에그

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';
        }
    }
}