[Algospot] 삽입 정렬 시간 재기

문제 정보

문제ID

MEASURETIME

출제자

JongMan

출처

알고리즘 문제 해결 전략

시간제한

2000ms

메모리제한

65536kb

분류

자료구조, 정렬, 트리

문제 설명

삽입정렬 시간재기 문제는 정렬알고리즘 중 O(n²)의 시간복잡도를 가진 삽입정렬 알고리즘에서 정렬을 하기위해 숫자가 움직이는 횟수를 구하는 문제입니다.

삽입정렬(Insertion sort)은 앞에서 부터 차례대로 정렬시켜 나가며, 이미 정렬되어 있는 부분과 비교하여, 자신의 위치를 찾아 정렬 시키는 알고리즘으로 일반적인 O(n²)의 정렬 알고리즘인 선택정렬이나 거품정렬 보다는 빠른 속도를 가집니다.

풀이 과정

이 문제 풀이의 핵심은 순차적으로 입력을 받으며, 먼저 입력 받은 값 중 현재 값보다 큰 수가 몇개인지를 Count 하는 것입니다.
물론 모든 값을 입력 받은 후에 계산을 하여도 되지만, 모든 값을 입력받은 후 처리를 하였을 때 얻을 수 있는 장점이 없으므로  편의상 입력을 받으며, 바로 처리하는 방법으로 문제를 풀어 나갔습니다. 

우선 간단하게 문제를 해결하는 방법으로 입력값들을 배열에 담아 새로 입력을 받을 때 마다 이전 입력 값들과 현재 값을 비교하여 큰 수들을 Count 하는 방법입니다.

#include <stdio.h>
int main(void) {
  int c,n,i,j,A[1000000], count;
  scanf("%d",&c);
  while(c--){
    count=0;
    scanf("%d",&n);
     for(i=0; i <n; i++){
      scanf("%d",&A[i]);
      // 이전 입력값과 현재 값을 비교하여 큰 수를 Count.
      for (j=0; j <i;j++){
        if (A [j]>A [i]){ 
          count++; 
        }
      }
    }
    printf("%d\n", count);
  }
  return 0;
}

아주 간단한 방법입니다만 예상대로 시간이 너무 오래 걸리는 단점이 있습니다.
위 연산은 n 개의 값을 입력받는다고 했을 경우 0+1+ ~ +(n-1) = n(n-1)/2 의 시간복잡도 O(n²)를 가집니다.

사실 이 문제에는 위 방법이 아닌 더 간단한 아이디어로 문제를 풀 수 있는 방법이 있습니다. 그건 바로 직접 삽입정렬을 수행하며, 숫자가 움직이는 횟수를 Count 하는 방법입니다.

#include <stdio.h>
int main(void) {
  int c,n,i,j,A[1000000],in,count;
    scanf("%d",&c);
    while(c--){
      count=0;
      scanf("%d",&n);
       for(i=0; i <n; i++){
        scanf("%d", &in);
        //삽입정렬을 수행하며 숫자가 움직이는 횟수를 Count.
        for (j=i-1; j>=0;j--){
          if (A[j]>in) {
            A[j+1] = A[j];
            count++; 
          } else {
            break;
          }
        }
        A[j+1] = in;
      }
      printf("%d\n", count);
    }
  return 0;
}

하지만 역시 삽입정렬은 위 첫번째 연산보다는 빠르겠지만 최악의 경우 0+1+ ~ +(n-1) = n(n-1)/2 의 시간복잡도 O(n²)를 가지는 연산으로 시간초과에 걸리게 됩니다. 

이 문제를 해결하기 위해서는 좀 더 빠르게 정렬을 수행하며, 현재 값보다 큰 값들을 찾을 수 있는 연산이 필요합니다.

Show Spoiler : 아래 내용은 제가 이 문제를 해결한 핵심 내용으로 문제를 푸는데 대한 힌트가 될 수 있습니다. 아래 내용을 보시고자 하는 분만 클릭하여 주시기 바랍니다. Close Spoiler

이번 문제에서 제가 찾은 방법은 '이진 탐색 트리'를 이용한 방법입니다.
이진 탐색 트리는 자식 노드를 2개만 가지는 이진 트리를 이용한 탐색 알고리즘으로서,
일반적으로 좌측 자식 노드에는 현재 값보다 작은 값이, 우측 자식 노드에는 현재값보다 큰 값이 위치하게 트리를 구성합니다.

이와 같이 트리를 구성할 경우 O(nlogn)의 시간복잡도로 정렬을 구현할 수가 있습니다.

여기에 각 노드에 자신보다 큰 자식노드(우측 노드)의 수를 가지고 있다면, 탐색을 해 나가면서 이전에 입력받은 값중에 현재 값보다 큰 값이 몇개인지를 알 수 있습니다.

제가 구현한 방식은 배열을 이용한 방법으로 A[n][4]의 배열을 만든 후 A[n][0] 에는 입력받은 값을, A[n][1] 에는 우측 자식 노드의 수를, A[n][2] 좌측 자식노드의 index를, A[n][3]에는 우측 자식노드의 index를 저장합니다.

Value
nRight
left
right

배열은 입력받은 순서대로 index 0 부터 index n-1까지 입력을 저장이 되며, 초기 A[i][0]에 입력받은 값을, A[i][1], A[i][2], A[i][3]은 0으로 세팅합니다.
이 후, Root 인 i=0 부터 탐색을 하며, 우측으로 이동할 때 마다 우측노드수(A[i][1])를 1씩 증가시키며, 좌측으로 이동할때는 해당 우측노드수(A[i][1])+1 을 Count에 추가해주면 결과를 구할 수 있습니다.

설명만으로는 이해가 어려울 수 있으니 예제입력 4, 2, 5, 3, 1를 가지고 설명을 하겠습니다.
index 0 번째가 곧 Root 노드가 되며, 처음 입력받는 값 4가 A[0][0]에 값이 저장됩니다.

Value	4	0	0	0	0
nRight	0	0	0	0	0
left	0	0	0	0	0
right	0	0	0	0	0

다음 index 1에 두번째 입력값 2을 저장 한 후 Root 노드 인 A[0][0] 부터 탐색을 하며 이진탐색트리를 만들어갑니다.
index 1의 입력값 2가 4보다 작으며, A[0]의 좌측노드가 없으므로 A[0][2]에 index 값 1이 저장됩니다.

Value	4	2	0	0	0
nRight	0	0	0	0	0
left	1	0	0	0	0
right	0	0	0	0	0

이 때의 Count는 1+A[0][1] = 1+1 = 1 이 됩니다.

다음으로 index 2에 세번째 입력값 5를 저장한 후 Root 노드부터 탐색합니다.
index 2의 입력값 5가 4보다 크며, A[0]의 우측노드가 없으므로 A[0][3]에 index 값 2가 저장됩니다.
그리고 index 0보다 큰 값이 추가되었으므로 A[0][1]를 1 증가합니다.

Value	4	2	5	0	0
nRight	1	0	0	0	0
left	1	0	0	0	0
right	2	0	0	0	0

이 때의 Count는 좌측으로 이동한 적이 없으므로 0이 됩니다.

다음으로 index 3에 네번째 입력값 3를 저장한 후 Root 노드부터 탐색합니다. A[0][0]과 비교(3<4) -> A[1][0]과 비교(3>2) 이므로 A[1][2]에 index 3를 저장 후 A[1][1]를 1 증가합니다.

Value	4	2	5	3	0
nRight	1	1	0	0	0
left	1	0	0	0	0
right	2	3	0	0	0

이 때의 Count는 좌측으로 A[0]에서 1번 이동하였으므로 1+A[0][1] = 1+1 = 2가 됩니다.

마지막 index 4에 다섯번째 입력값 1를 저장한 후 Root 노드부터 탐색합니다. A[0][0]과 비교(1<4) -> A[1][0]과 비교(1<2)이므로 A[1][2]에 index 4를 저장합니다.

Value	4	2	5	3	1
nRight	1	1	0	0	0
left	1	4	0	0	0
right	2	3	0	0	0

이 때의 Count는 좌측으로 A[0], A[1]에서 2번 이동하였으므로 2+A[0][1]+A[1][1] = 2+1+1 = 4가 됩니다.

이제 Count를 모두 더하면 0+1+0+2+4 = 7이 됩니다.
이는 다음과 같이 결과를 확인할 수 있습니다.

A	비고
4 2 5 3 1	초기 상태(이동 0)
2 4 5 3 1	2를 왼쪽으로 1칸 옮김(이동 1)
2 4 5 3 1	5를 이동하지 않음(이동 0)
2 3 4 5 1	3를 왼쪽으로 2칸 옮김(이동 2)
1 2 3 4 5	1를 왼쪽으로 4칸 옮김(이동 4)

== 소스보기 ==

결과

#

452827

문제

MEASURETIME

언어

cpp

길이

690B

수행시간

226ms

결과

정답

제출일

2016-08-03