Simple in Complex with Simple

-개요-

배낭 문제는, knapsack problem이라 불리는 유명한 조합 최적화 분야의 문제로 불린다고 한다.

NP-난해에 속하는 문제로, 여기서 NP란 복잡도의 일종으로 다항 시간 안에 풀 수 있는 판정 문제의 집합이다.

여기서 다항 시간이란 Polynomial Time을 말한다. 

즉, 빅 오 표기법으로 O(n^c) n제곱, n의 세 제곱, ... , n의 c제곱을 일컫는다.

지수적 시간인 Exponential Time과는 다르다. 지수적 시간은 O(c^n)을 일컫는다. 2^n, 3^n ...

이 문제의 대표적인 문제인 '도둑과 고민' 문제다.

알고리즘은 57챕터인 모든 부분집합을 출력하는 방식을 활용하여 그 토대로 작성되었다.

-문제-

'한 도둑이 주거집을 침입했다. 이 때, 도둑 눈 앞으로는 여러가지 가치있는 물건들이 존재한다. 찾아낸 물건은 총 N개였다.

이 때, 도둑은 자신이 이 모든 물건을 가져갈 수 없다는 것을 알았다. 왜냐하면 자신이 가져온 배낭이 모든 물건을 담을 수

없기 때문이다. 이 상황에서 도둑이 가장 효율적으로 물건을 훔칠 수 있는 방법은 무엇인가.'

'가장 효율적으로 훔친 물건들의 가치 합과 각 물건들을 출력하시오.'

이 문제의 풀이는 단순하다.

도둑이 가져갈 수 있는 모든 물건들의 조합을 찾고, 그 중에서 자신의 가방에 담을 수 조합만 추린다.

그리고 그 조합중에서 물건들의 가치 합이 가장 높은 조합을 찾아낸다.

그렇기에 앞선 57 문제의 모든 부분집합을 찾고, 그 부분집합을 찾을 때마다 처리 알고리즘에 넣으면 된다.

-점화식-

V(capacity, n) = max( value<n-1> + V(capcity-weight<n-1>, n-1), V(capacity, n-1) )

똑같이 현재 물건들을 선택하는 것과, 선택하지 않는 두 분기로 나뉜다.

두 개의 재귀 흐름으로 나뉘기에 수행시간은 O(2^n)이 되야하지만, capacity의 한계가 존재하기 때문에 선형시간에 풀린다.

-코드-

-출력-

-정리-

이 문제를 풀면서, 재귀적으로 움직이면서 최종 결과 셋을 출력할 수 있는 새로운 방법을 알아내었다.

획기적인 방식이다. 결국은 전수조사법이지만 부분집합을 모두 구하고 이 부분집합을 계산 함수에 넣어서 풀어내는 방식이

항상 궁금했는데, 이런식으로 재귀 흐름에 Recover 동작없이 풀어내느 것을 알았다.

한 단계 조금 정진한 느낌이다.

결국은 계속 반복된 알고리즘이긴 하지만, 한 번 본 것은 안 본 것이라는 강성태님의 말처럼 계속 새롭다.

조금씩, 조금씩 말과 조건이 변한 것 뿐인데 알고리즘의 축이 변한다.

또한 이 문제를 풀면서 배우게 된 부분이 있다.

바로 재귀 운행의 구조는 결국은 트리 구조다.

2개 분기로 나뉘면 이진 트리, 3개 분기로 나뉘면 노드가 3개 가진 삼항 트리 ... 

머리속으로 드디어 재귀의 구조가 들어온다.

이것을 이제 알다니 바보다. 확실히 독학으로 하면 정말 아주 간단하고 쉬운것인데도 그 본질을 모르고 겉돈다.

다행히 이제라도 알아서 다행이다. 하지만 비록 본질은 느리게 알았지만 이것을 알아가는 과정속에서 그 깊이가

훨씬 깊어지는 것을 느낀다.

그리고 또한 이런 재귀 흐름의 구조에서 결국 재귀의 흐름은 중위 순행이란 것을 알았다.

진짜 이것을 어떻게 이제 깨닫지. 이러니 머릿속에 재귀가 쉽게 쉽게 안들어오지.

너무 선형 구조로만 알고리즘을 생각하는 것 같다. 조금 더 트리나 그래프 구조에 친숙해지자.

이 문제를 풀어내는데 너무 오랜 시간을 사용하였다.

집중이 많이 풀렸다.

진짜 정말 사소한 부분인데, 계속 오류를 못 찾아내고 빙빙 돌다보면 어느새 집중력이 사라진다.

계속 허리피고 공부하자.

0부터 N-1까지 모든 부분집합 출력하기 알고리즘.

이 알고리즘은 컴퓨터 과학에서 나열하기의 한 종류이다.

나열하기 알고리즘은 대부분 모든 경우를 다 조사하는 전수조사법이 기반이다. 

그렇기에 컴퓨터과학에 무척 어울리는 종류의 주제이며, 재귀적인 방법이 주로 쓰인다.

0부터 N-1까지의 집합 중에서 모든 부분집합 출력하는 방법은 단 두 문장으로 정리된다.

(1) 현재 원소를 포함한 부분집합

(2) 현재 원소를 제외한 부분집합

이 두 문장의 조합으로 모든 부분집합을 찾을 수 있다.

예를 들어 만약 {0,1,2} 집합의 모든 부분집합은 다음과 같다.

{0, 1, 2}

{0, 1}

{0}

{1, 2}

{1}

{2}

공집합

이렇게 8개이다. 즉, 모두가 다 알듯이 2^n개가 바로 n까지의 부분집합 개수이다.

다음은 코드이다.

주석을 통해서 실행원리를 아주 자세히 작성했다.

주석을 많이 쓴 코드는 원리를 파악하기는 좋지만, 한 눈에 보기 어려우니 다음은 주석을 뺀 코드다.

굉장히 코드가 간결하다. 이 코드에 대한 출력은 다음과 같다.

(1) {0, 1, 2}의 모든 부분집합 출력

(2) {0, 1, 2, 3, 4}의 모든 부분집합 출력

올바른 결과를 확인할 수 있다. 아래 빈 공백이 바로 공집합을 의미한다.

그럼 지금부터가 아주 짧지만 이 포스팅의 주 본론이다.

만약 재귀적으로 돌아가는 두 분기의 순서를 코드에서 바꾼다면 어떻게 될까?

결과는 다음과 같다.

왜 올바른 출력이 나타나지 않을까?

순서를 바꾸든 안바꾸든 결국 두 조건

(1) 현재 원소를 포함한 부분집합과 

(2) 현재 원소를 제외한 부분집합의

합인데.

그 이유는 모두가 알다시피 배열을 통한 포인터 접근이기에 이전 분기를 돌면서 기존의 필요한 데이터가 덧씌어져이다.

이를 간단하게 그림으로 한 번 실행 흐름을 따라가며 그려보면 더 명확히 알 수 있다.

그럼 이 바뀐 순서를 유지하면서 올바른 출력을 만들어내려면 어떻게 해야할 까?

다음 코드와 같이 데이터의 처리를 유효한 분기와 밀접하게 연결시켜주면 된다.

이 말을 잊지 않기 위해서 이 포스팅을 작성하였다. 

결과는 다음과 같다.

분기의 순서가 다르기에 전체적인 출력 형태의 순서도 달라진 것을 볼 수 있다.

이처럼 전체 경우를 나열하는 문제는 꽤 많다.

또한 분기가 2개가 아니라 여러개일 수 도 있는데, 그 땐 지금까지 데이터를 백업했다가 각 분기별로 recover하는 방식으로

코드를 작성해왔다. 하지만 이 방식은 너무 비효율적이다. 데이터를 유효 분기에 연결시켜주긴 하지만 그러니 조금 더 연구

해서 더 깔끔하고 효율성있는 방법을 찾아보자.

이번 블로그에서는 퀵 정렬의 새롭게 알게된 부분부터, 과거에 잘못알았던 부분까지 총정리한다.

코드는 맨 아래에 자세하게 비교해두었다.

먼저 퀵 정렬(Quick Sort)은 1962년 '호어(C. A. R. Hoare)'가 고안한 알고리즘이다.

일반적인 시간 복잡도는 평균적으로 O(nlogn), 최악의 경우 O(n^2)의 시간이 소요된다.

여기서 말하는 최악의 경우란, 정렬하는 배열이 이미 정렬되어 있거나, 거의 정렬된 상태를 지칭한다.

그래서 어떻게보면 앞서 소개한 Insertion Sort와 반대의 성질을 가지고 있다.

퀵 정렬의 복잡도는 다른 알고리즘 Heap Sort 또는 Merge Sort보다 뛰어난 것은 아니다. 

하지만, 실제로 수행했을 때 다른 정렬 알고리즘보다도 빨라서 가장 많이 쓰이는 알고리즘이 되었다.

퀵 정렬의 알고리즘을 딱 두가지 순서로 요약하면 이렇다.

(1) 기준 원소(pivot)를 선택한다.

(2) 기준 원소에 따라 검사 배열을 두 배열로 나눈다.

(3) 정렬될 때까지 위의 (1)~(2)를 반복한다.

*기준 원소는 어떤 원소이든지 관계없다.

아주 간단하다. 하지만 처음 접하는 사람이 막상 구현하려고 하면 어떤 방식인지 헷갈린다.

결국은 기준에 따라 두 분류로 나누고, 한 번 기준은 다시 검사하지 않는다. <<가장 핵심이지만 원리를 모르면 어렵다.

왜냐하면 한 번 기준 원소로 뽑히면, 그 기준 원소는 정렬되었다고 판단한다.

먼저 간단한 예시이다.

4 8 6 2 3 7 5 1 (4는 pivot이고 8부터 1까지 아래와 같은 순차 검사를 진행한다.)

*

(*은 현재 스왑 위치를 가리키고 최초 스왑 위치는 기준 원소인 pivot을 가리킨다.)

(Step 1) 8은 pivot보다 크므로 두 가지로 나뉘는 배열 중 후반부에 속한다.

(Step 2) 6은 8과 마찬가지이다.

(Step 3) 2는 pivot보다 작으므로 전반부 배열이다. 스왑 위치를 하나 먼저 증가시켜 다음 스왑 위치와 교환한다.

           (2 <-> 8)

4 2 6 8 3 7 5 1

   *

(Step 4) 3은 pivot보다 작으므로 전반부 배열이다. 스왑 위치를 하나 증가시켜 다음 스왑 위치와 교환한다.

           (3 <-> 6)

4 2 3 8 6 7 5 1

     *

(Step 5) 7은 pivot보다 크므로 후반부 배열에 속한다.

(Step 6) 5는 pivot보다 크므로 후반부 배열에 속한다.

(Step 7) 1은 pivot보다 작으므로 전반부 배열이다. 스왑 위치와 교환하고 스왑 위치를 하나 증가시킨다.

     (1 <-> 8)

4 2 3 1 6 7 5 8

        *

(Step 8) 모든 원소를 한번 순회했으면, 마지막으로 기준 원소와 현재 스왑 위치를 교환한다.

1 2 3 4 6 7 5 8

그 이유는 기준 원소대로 두 배열로 나뉜 것이기 때문에 제자리를 찾아준 것이다. <<중요중요

즉, 

1 2 3    4    6 7 5 8

이렇게 나뉜 것이다. 그리고 4는 이제 검사 대상에 포함되지 않는다.

나머지 1 2 3 배열과 6 7 5 8 배열을 각각 (Step 1) ~ (Step 8)까지 반복한다.

그러면 최종적으로 1 2 3 4 5 6 7 8 순으로 정렬된다.

여기까지가 기본 원리이다.

전반적이고 기본적인 퀵 정렬의 원리를 알았다면, 이제부터가 진짜 퀵 정렬의 시작이다.

먼저 기본적인 위의 과정은 기초적이지만 실제로 사용하기에는 제약이 따른다.

크게 4개의 문제가 있다.

(1) 랜덤 배열

(2) 이미 정렬되어 있는 배열

(3) 모두 0인 배열(또는 모든 원소가 같은 배열)

(4) 스택 오버플로우 문제 

아주 중요한 문제다!!! 이번에 알게 된 사실도 이 부분들이다.

이 포스팅의 핵심은 바로 이 부분부터이다.

왜 대부분의 프로그래머들이 정렬 라이브러리가 있고, 그 라이브러리의 정렬이 당신의 요구조건을 만족하면

절대로 직접 만들어 쓰지말라고 한 이유들이 바로 저런 문제들이다.

아래 코드를 보면, 퀵 정렬 알고리즘은 다양한 입력에 대해 빠르고 잘 작동하는 정렬 함수를 만들기가 상당히 어렵다.

여기서 다양한 입력이란 조건의 대표적인 예시들이 바로 위의 4가지 문제이다.

4가지의 코드가 있다.

첫 번째 코드는 위에 소개한 (Step 1) ~ (Step 8) 방식으로 움직이며, 랜덤 배열에서는 잘 동작하지만 이미 정렬되어 있는 배열

또는 모든 원소가 같은 배열 그리고 스택 오버플로우의 문제에 취약하다.

두 번째 코드는 첫 번째 코드에서 기준 원소를 랜덤하게 뽑아나가는 방식이다. 단, 하나의 코드만 추가되었다. 이 경우 랜덤 배열과 이미 정렬되어 있는 배열에서는 잘 동작하지만 나머지 (3) (4) 문제에는 취약하다.

세 번째 코드는 과거에 블로그에 포스팅한 코드로 완성형 코드인 네 번째 코드와 원리는 같다. 하지만 그 때 적었던 것처럼 어떤 문제가 있는 듯, 모든 (1) (2) (3) (4) 문제에 대해 취약하다. 이를 완벽히 보완한 코드가 바로 네 번째 코드이다. 

네 번째 코드는 완성형 코드로 위의 예시 과정과는 조금 다른 방식이다. 아마 일반적인 퀵 정렬 알고리즘이라고 한다면 이 세 번째 코드를 지칭한다. (1) (2) (3) (4) 모든 문제에 대해 가장 강력한 방식이다. 세 번째 코드의 방식과 원리는 똑같지만 훨씬 더 명료하게 작성되어 있다. (세 번째 코드는 뭔가 잘 안보이는 실수를 한 듯하다. 이유를 잘 모르겠다.)

-코드 Part-

(1) Quicksort_Seoul(), Partition_Seoul()

(2) Quicksort_Seoul2(), Partition_Seoul2()

(3) Old_Quicksort(), Old_Partition()

(4) Quicksort_Seoul_Final(), Partition_Seoul_Final()

-출력 Part-

(1) 데이터 크기 2000 - 크게 다르지 않다.

(2) 데이터 크기 3000 - 1번 코드와 2번 코드 4번 코드의 문제가 보인다.

(3) 데이터 크기 4000 - 전반적으로 각 코드마다 어떤 결과가 보이는지 가장 일목요연하다.

(4) 데이터 크기 5000, 10000, 100000, 1000000, 10000000 (3번 코드 제외하고 모든 코드 Stack Overflow 터짐)

여기까지가 퀵 정렬에 대해서 좀 더 자세히 알아보았다.

몇 개월 전에 올렸던 퀵 정렬의 문제가 무엇인지 조금 더 알 수 있는 시간이었고, 퀵 정렬의 구동방식이 이제 머릿속에

완전히 잡혔다.

퀵 정렬 내 인생 첫 면접에서, 

버블 정렬에 대해서 면접관님이 손 코딩 할 수 있냐고 질문하셨는데, 

그건 너무 쉬워서 잘 모르겠고 전 퀵 정렬밖에 안 사용합니다. 라고 말했다가 그대로 화이트보드에 퀵 정렬 손 코딩했다.

그 때, 짰던 코드가 바로 Old_Quicksort() 코드였다. 첫 손 코딩이라 진짜 개판이었는데 그래도 패기를 잘 보아주셔서 

합격했었다. 아마 그 때의 합격이 지금 내가 이렇게 꿈을 찾고 여기에 도달할 수 있게 만들었다.

그래서 더욱 퀵 정렬에 대해서 감사하고, 제대로 포스팅하고 싶었는데 이렇게 일단 마무리지어서 좋다.

더 공부하자.

Insertion Sort(삽입 정렬)이란 비효율 정렬(O(n^2))이지만, 한 가지 특징으로 인해 알아둘 필요가 있다.

흔히 비효율 정렬에는 대표적으로 3개가 있는데 바로 

'Bubble Sort(버블 정렬)', 'Selection Sort(선택 정렬)', 'Insertion Sort(삽입 정렬)'이다.

이 중에서 선택 정렬은 버블 정렬보다 완벽히 상위 호환이므로, 버블 정렬을 정렬 알고리즘 분류에서 빼야 한다는 말도 있다.

선택 정렬의 알고리즘은 무척 간단하다.

각 단계별로 최소값 또는 최대값을 찾아 정렬하고 있는 위치에 저장한다.

이전에 비교 방식에서 최소값 또는 최대값을 찾는데 쓰이는 비교 회수는 n-1, n-2, n-3, ... 1번이다.

그리고 이의 -1 등차수열의 합이 바로 선택 정렬의 총 비교 회수이다.

선택 정렬은 모든 정렬 알고리즘 중에서 가장 기초이다. 딱히 특별한 성질은 없고, 하나씩 찾아나가면서 정렬하는 방식이다.

그리고 이런 선택 정렬과 더불어 또 다른 비효율 정렬이 바로 삽입 정렬이다.

삽입 정렬은 비효율 정렬이지만 특정 경우에 한해서는 무척이나 빠르다.

그 특정 경우란 한 마디로 이미 정렬되어 있는 경우(0으로 채워진 제로 배열 포함)를 말한다.

선택 정렬이 배열의 요소를 중복해서 계속 비교해나가는 알고리즘이라고 한다면,

삽입 정렬은 길이 1에서부터 길이 N까지 늘려가며 자신의 자리를 찾아가며 정렬해나가는 방식이다.

이 때, 각 길이별로 정렬이 되어있어야 한다.

요약하면 다음 두 가지의 과정의 반복으로 삽입 정렬은 이루어진다.

(1) 원소를 하나 추가.

(2) 추가된 원소를 적절한 위치에 삽입.

즉, 5 2 1이라는 배열이 있을 때,

맨 처음에 길이 1에서 정렬된 배열은 

5 (완료)

다음 길이 2에서 정렬된 배열은

5 2

(자기위치 찾기)

2 5 (완료)

다음 길이 3에서 정렬된 배열은

2 5 1

(자기위치 찾기)

1 2 5 (완료)

즉, 이전 시행의 결과로 인해 현재 검사 대상까지의 배열이 정렬되어 있다는 것이 중요하다.

이 성질로 인해 삽입 정렬은 독특한 특징을 가지는데, 

현재 검사 대상이 이전 요소보다 크다면, 그 때의 비교 수행을 하지 않고 다음 단계로 진행된다.

예를들어)

만약 1 2 5 라는 배열이 있으면, 

첫 단계

1

두 번째 단계

1 2 (비교 수행 안함)

세 번째 단계

1 2 5 (비교 수행 안함)

그렇기에 이미 정렬된 배열이라면, 각 시행은 Constant 시간에 끝이 난다.

이 성질을 이용해 이 배열이 정렬된 배열인지 검사하거나, 어느정도 정렬된 배열을 정렬하는데 유용하게 쓰인다.

다음은 여러가지 방식의 삽입 정렬 코드이다.

결국 모든 방식은 똑같지만 표현만 다르다. - 각자 이해하기 편한대로 이해하면 좋다.

(1) SWAP 방식

(2) 뒤로 미루기 방식

(3) 아마존 SW 수석 Developer 방식

(4) 서울대 저자 방식

(5) 서울대 저자 방식 2

(6) 서울대 저자 방식 (함수 호출 x)

(*) 출력 - 제로 배열 수행했을 때

이미 정렬된 배열을 6가지 방식으로 수행하였을 때, 나온 결과이다.

이때 0.02초에 수렴하는 방식들은 함수 콜이 존재하므로 발생한 시간이다.

함수 콜을 사용하지 않는 방식은 모두 0.005초 안에 끝이 났다.

삽입 정렬의 기초부터 그 원리까지 하나씩 다 파악했다. 이젠 절대 잊어버리지 말자.