8일차 리뷰

2019/01/14 - [프로그래밍/알고리즘] - 7일차 리뷰

낮잠, 면접, 약속 등 이것저것해서 2일 동안 문제를 못풀었는데

마침 짬이 나서 한 문제 풀었다.

이제 본격적인 알고리즘의 서막이자 꽃!

step9 정렬해보기

---

2750

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

내 풀이 : https://github.com/gnidoc327/one-day-one-problem/commit/7133b2d8c2f76c11bcb46291fe7e59c189e98846

문제에서는 어떤 정렬 알고리즘을 쓰라는지 안나와있어서 Arrays.sort를 사용해서 처음에 풀었다.

다음껄 풀어야지했는데 설명란에 이런게 있더라...

(아하 문제 푸는게 중요한게 아니구나!)

신입생때 c언어 과제가 버블소팅(거품 정렬)이었던게 문뜩 생각이 들었고

알고리즘 수업에서 brute force에 대한 내용이 생각났다.

삽입/거품 정렬이 뭔지는 다들 설명을 했을테니

난 brute force에 대해 설명하고자 한다.

brute force은 직역하면 무차별 대입이다. 

예를 들자면 디비에 비밀번호를 저장할때 암호화해서 저장하는데 많은 사람들이 이게 완벽한 줄 안다.

사실 알고보면 0부터 +1씩하면서 넣다보면 언젠가 비밀번호가 풀린다. 

그래서 보통 사이트에서 3~6개월마다 비밀번호를 바꾸라고 하는게 이런 이유가 있다.

물론 이런 방식은 천문학적인 시간이 소요되지만 이렇게 해서 풀린 암호화 방식 중 DES가 있다.

그것도 무려 하루만에 찾아낼 수 있는 하드웨어가 99년도에 공개되었다고 한다.

그 기계는 2^56 경우의 수를 분산처리로 직접 대입해서 답을 찾아냈다는 것이다.

(최근에는 sha2, 3 등 다양하고 더 큰 수의 암호방식이 만들어지면서 강화되긴 했다.)

(물론 안뚫릴리 없겠지)

(이렇게 생겼다고 한다)

이렇게 입력할 수 있는 경우의 수를 모두 대입해서 푸는 방식의 알고리즘을 brute force라고 한다.

삽입 정렬과 거품 정렬 또한 이런 알고리즘을 사용한 정렬 기법 중 하나이다.

오름차순으로 정렬한다고 했을때,

• 삽입 정렬은 낮은 숫자를 앞에 '삽입' 하는 것이고
• 거품 정렬은 높은 숫자를 '거품이 물에 떠오르듯' 위로 올리는 것이다.

정렬 문제부터 본격적으로 시간 복잡도라는 개념이 나온다.

그리고 빅오(Big-O)라는 개념이 나오는데 

빅오란 간단히 말하자면 작은 수는 무시하자는 것이다.

(n이 양의 방향으로 무한하게 증가한다고 가정한다)

• O(n+1) = O(n) : n에 비하면 1은 매우 작기 때문에 1은 무시된다.
• O(n^2 + n) = O(n^2) : n^2에 비하면 n은 작기 때문에 n은 무시된다.
• O(3n+2) = O(n) : 3n이나 n이나 무한대로 가면 결국 비슷한 값이기 때문에 *3과 +2는 무시된다.
• O(nlogn) = O(nlog(n+2)) : 지수나 로그(log)나 비슷하게 처리한다.

알고리즘에서 빅오 개념을 사용하는 이유는 이러하다

• if문 여러개보다 for문의 중첩이 더 중요하다 : +1, +2(if문 조건)보다 n^2, n^3(for문 중첩)이 더 중요
• for문이 2~3번 연속으로 나오는 건 크게 상관없다 : O(2n) = O(3n) = O(n)
• for문의 시작이 0이든 100이든 n이 크다면 무시할만하다 : O(n(n+100)) = O(n^2)
• 단순 상수보다 log는 시간 복잡도에 영향을 많이준다. : O(n + 100) < O(nlogn)

즉, 컴퓨터 과학에서의 알고리즘은 for문의 중첩과 같은 큰 규모의 시간 복잡도만을 고려한다는 것이다.

for문을 m번 중첩해서 사용했다 => O(n^m)

logn는 보통 tree 구조를 사용할때 나오는데 이건 아마 내일 리뷰할 듯 싶다.

시간복잡도 설명은 대략 이정도까지만 정리.

그럼 실제 푼 문제에 대한 시간복잡도를 간단하게 구해보자.

일단 거품 정렬의 모범답안(위키)을 들고 왔다.

void bubbleSort(int[] arr) {
    int temp = 0;
    for(int i = 0; i < arr.length; i++) {
        for(int j= 1 ; j < arr.length-i; j++) {
            if(arr[j]<arr[j-1]) {
                temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

for문이 2개이다? -> 시간 복잡도는 O(n^2)이다.

(if문과 swap에 대한 연산은 상대적으로 매우 작은 값이므로 무시된다)

삽입 정렬은 while문으로 많이 풀이되는데 while == for이다.

(어차피 while이나 for나 어셈블리 코드로 보면 동일한 condition -> jump 구조이다.)

void insertionSort(int[] arr)
{
 
   for(int index = 1 ; index < arr.length ; index++){
 
      int temp = arr[index];
      int aux = index - 1;
 
      while( (aux >= 0) && ( arr[aux] > temp ) ) {
 
         arr[aux+1] = arr[aux];
         aux--;
      }
      arr[aux + 1] = temp;
   }
}

for문이 2개(while은 for문) -> 시간 복잡도는 O(n^2)이다.

(index가 1부터 시작해봤자 빅오에서는 무시할만한 상수다)

사실 삽입 정렬이 버블소팅이랑 무슨 차이가 있지하고 헷깔렸는데 코드보고 이해했다.

그냥 정렬 우선 순위 방향이 반대일 뿐....

요즘 블로그 하시는 분들이 정렬하는 움짤도 만들어놓고 해서 설명을 잘해놓은걸 보고

난 알고리즘 설계하는 방법에 대해서 리뷰를 해나갈려고 한다.

문제를 푸는 것보다 푸는 법을 익히기 위해서 랄까?

~~~알고리즘은 설명이 많은데 동적 프로그래밍, 분할 정복 알고리즘에 대한 설명을 하는 곳이 없어서

아마 정렬 step쪽은 알고리즘 설계 위주로 갈 듯 하다.

내일은 지옥의 힙소팅과 머지소팅이 기다리고 있다!

내일 저녁은 지옥에서 하는걸로