Lavine's Dev Site

Problem

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

A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once.

Two integers in а permutation form an inversion, when the bigger one is before the smaller one.

As an example, in the permutation 4 2 7 1 5 6 3, there are 10 inversions in total. They are the following pairs: 4–2, 4–1, 4–3, 2–1, 7–1, 7–5, 7–6, 7–3, 5–3, 6–3.

Write program invcnt that computes the number of the inversions in a given permutation.

Input

The value for the number n is written on the first line of the standard input. The permutation is written on the second line: n numbers, delimited by spaces.

Output

Write the count of inversions on the standard output.

문제 해결 과정

Inversion Counting이라고도 알려진 나름 유명한 문제이다.

What is Inversion? 

  임의의 길이가 N인 정수 배열 A가 주어졌을 때, A의 index의 쌍 (i, j)에 대하여 i < j, A[i] > A[j]이면 (i, j)는 A의 Inversion이라고 한다.

접근 1 - Brute Force Algorithm

   2개의 for loop을 구성하여 outer loop 값보다 큰 inner loop의 값이 존재하는 경우를 counting한다. 

  이때 시간복잡도는 O(n²)가 된다. -> TLE 발생 ( 2≤ n ≤ 1000000)

   따라서 O(n²)보다 효율적인 복잡도를 갖는 알고리즘이 필요하다!!

접근 2 - Divide and Conquer

 어느 한 배열에서 inversion의 경우를 생각해보면 아래의 그림과 같이 정렬을 하는 과정에서 생기는 교차 점의 개수로 표현이 가능하다.

따라서 Merge Sort 과정 중 merge 부분에서 arr[i] > arr[j] 인 경우를 count해주면  O(NlogN)의 시간 복잡도로 구할 수 있다. 

My Solution Code

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

public class BOJ10090 {
    static int[] tmp;
    static int[] arr;
    static long inversion;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N  = Integer.parseInt(br.readLine());   // 순열 길이
        arr = new int[N];
        tmp = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        inversion = 0;

        mergeSort(0, N-1);

        System.out.println(inversion);
    }

    // divide and conquer
    static void mergeSort(int start, int end) {
        if (start >= end)   // 끝까지 분할 한 경우
            return;

        int mid = (start + end) >> 1; // 중앙 값
        mergeSort(start, mid);  // 좌측 (divide)
        mergeSort(mid+1, end);  // 우측 (divide)
        merge(start, end);  // 병합 (conquer)
    }

    static void merge(int left, int right) {
        int mid = (left + right) >> 1;
        int leftIdx = left;     // 좌측 배열 탐색 인덱스
        int rightIdx = mid+1;   // 우측 배열 탐색 인덱스
        int tempIdx = left;     // 임시 저장 배열 인덱스

        while (leftIdx <= mid && rightIdx <= right) {
            if(arr[leftIdx] <= arr[rightIdx]) {
                tmp[tempIdx++] = arr[leftIdx++];
            } else {
                // inversion 발생 경우 (leftIdx < rightIdx && arr[leftIdx] > arr[rightIdx] )
                tmp[tempIdx++] = arr[rightIdx++];
                inversion += (mid - leftIdx + 1);   // 교차점 count
            }
        }

        // 좌측 잔여 원소 배치
        while(leftIdx <= mid) {
            tmp[tempIdx++] = arr[leftIdx++];
        }

        // 우측 잔여 원소 배치
        while(rightIdx <= right) {
            tmp[tempIdx++] = arr[rightIdx++];
        }

        // copy array
        for(int i = left; i<=right; i++) {
            arr[i] = tmp[i];
        }
    }
}

Problem

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

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

Input

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

Output

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

문제 해결 과정

   -> 문제의 중요 포인트

          1. 한 사이트에는 최대 한 개의 다리만 연결 가능하다.

          2. 서로 다른 다리끼리 겹칠 수 없다.

 따라서 문제의 목적은 M개의 동쪽 사이트 중 N개를 위에서부터 1:1로 연결되는 개수를 구하는 것이다. 그러므로 중복없이 선택하는 경우의 수 즉, 조합 (Combination)을 사용하면 된다.

 이때, 사용될 조합 공식은 아래와 같다. 

 여기서 아래의 2가지 조합 공식 성질을 이용한다면 DP(Dynamic Programming)를 통하여 문제를 풀 수 있게 된다. 

My Solution Code 

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

public class BackJoon1010 {
    static int[][] dp;  // dp 저장 배열

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());    // 테스트 케이스 수

        for(int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine() ," ");
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            dp = new int[M+1][N+1];
            sb.append(combination(M, N) + "\n");
        }
        System.out.println(sb);
    }

    static int combination(int n, int r) {
        // 이미 계산된 결과라면 해당 값 반환
        if(dp[n][r] > 0) {
            return dp[n][r];
        }

        // 조합 성질 - 2 사용
        if (r == 0 || n == r) {
            return dp[n][r] = 1;
        }

        // 조합 성질 - 1 사용
        return dp[n][r] = combination(n-1, r-1) + combination(n-1, r);
    }
}