고등학생 시절.. 대학교 진학이 결정되기 직전까지 나의 꿈은 전기전자공학자였다. 운이 좋게 "창원과학고등학교"라는 특목고에 진학하게 되었고, 고등학교를 재학하며 가장 심도 있게 배운 과목은 수학과 물리였기 때문이다. 특히 물리에서 전자기학 파트를 좋아했고 관련 R&E(Research & Education)를 경험하며 자연스럽게 전기전자공학자를 꿈꾸게 되었던 것 같다. 그런 내가 지금은 소프트웨어학과에 진학하게 되어 개발자를 꿈꾸고 있다. 그 이유는 고등학교 때 잠시 취미로 배운 C언어가 생각보다 재미있었고, 그래서 대학 원서를 하나 정도 소프트웨어학과에 넣어보았고, 이 원서가 운이 좋게 합격을 했는데 마침 2년동안 전액장학금을 지원해준다고 하였다. C언어가 즐거웠던 기억을 회상하며 한 번 새로운 도전을 해보자 다짐하며 소프트웨어학과에 진학하였다.

나는 현재 대학교 2학년까지 다니고, 휴학한 뒤 군대를 복무하고 있다. 현재 계급은 상병으로 딱 군생활의 중간을 달려가고 있는데, 곰곰히 내 대학생활을 되돌아보니 정말 놀기만 했다는 사실이 그저 놀라웠다. 분명 새로운 도전을 다짐하며 입학한 소프트웨어학과에서, 나의 2년은 롤과 피파로 가득차 있었다. 그리고 지금은.. 진로와 관계 없는 온갖 뺑이를 치며 의미 없는 군생활을 이어나가고 있었다. 그러다 문득 어차피 IT분야로 내 진로를 이어나갈 것이라면, 군복무라는 시간을 활용해 앞으로 내가 어떤 공부를 해야하는지, 어떤 직업을 가질 수 있을지를 탐구해야겠다는 생각이 들었다.

그 탐구의 과정으로 먼저 [한 권으로 읽은 컴퓨터 구조와 프로그래밍]을 완독할 것이다! 이 책은 다양한 IT분야의 밑바닥 지식을 훑어주는 주제를 다룸으로써, 나에게 앞으로 배울 컴퓨터 지식의 기초를 다져줄 수 있을 것 같다는 생각이 든다. 더 나아가 내가 개발자가 되는 길의 이정표가 되어 줄 수 있을 것이라는 믿음으로 이 책을 읽어보려고 한다. 이 믿음이 착각일 수 있지만, 그래도 아무것도 안하는 것보단 나으니까 ㅎ.ㅎ 이 책은 총 15장으로 이뤄져 있는데, 한 장을 읽을 때마다 느낀점, 배운점 등을 쓸 예정이다. 내가 이 책을 완독할 수 있길 바라며 1장을 펴야겠다!!

📖 1장. 컴퓨터 내부의 언어 체계

1장은 개념적으로 비트를 사용하여 정수, 실수, 문자, 색 등 다양한 요소를 표현하는 방법에 대해 배울 수 있었다.

현재 정수를 비트로 표현하는 방법이 1의 보수(one's complement) 표현법과 2의 보수(two's complement) 표현법 중 왜 2의 보수 표현법이 대부분 선택되었는지 알 수 있었다. 1의 보수 표현법은 0을 두가지 방식으로 표현하는 문제와 덧셈을 하였을 때 MSB(most significant bit)에서 LSB(least significant bit)로 1을 순환 올림을 할 때 하드웨어를 추가해주어야 하는 문제가 있다. 하지만 2의 보수 표현법에서는 앞서 설명한 1의 보수 표현법의 문제점을 해결하였다.

실수를 표현하는 방법에는 고정소수점 표현법과 부동소수점 표현법에 대해 알 수 있었다. 고정소수점 표현법은 디지털 신호 처리 장치(DSP)등 특별한 목적에 쓰이고, 일반적으로는 부동소수점 표현법을 사용한다. 그 중 현재에는 IEEE 754를 표준으로 사용한다.

문자, 즉 텍스트에 표현하는 방법도 배울 수 있었다. 영어 키보드에 있는 모든 기호를 표현할 수 있는 아스키 코드, 다른 언어들을 표현하는 다양한 표준들이 생겨나서 이를 모두 포함하기 위해 생겨난 유니 코드에 대해 배웠다. 그리고 인코딩 방법으로 UTF-8(유니코드 변환 형식 8비트), QP(출력 가능하게 변경한 인코딩), QP보다 조금 더 효율적인 베이스64 인코딩, URL 인코딩에 대해 알 수 있었는데, 솔직히 잘 이해가 안돼서 다음에 인코딩에 대해 조금 더 찾아보고 공부해야겠다.

마지막으로 색을 표현하는 방법을 배웠다. 컴퓨터에서 색은 기본적으로 RGB를 조절하여 색을 만들어 낸다. 빨간색, 녹색, 파란색 각각을 8비트의 크기(0xff ~ 0x00)로 조절하여, 24비트에 저장을 해 색을 만들어 낸다. 그리고 이 24비트를 32비트에 색을 넣어서 처리하는데, 이때 8비트가 빈 공간으로 남게 되어서 남은 8비트는 투명도를 나타내는 비트로 활용한다. 색 인코딩은 16진 트리플렛(hex triplet)으로 표현한다. #rrggbb로 표현하는데(rr은 빨간색의 값, gg는 녹색의 값, bb는 파란색의 값), 예를 들어 #ffff00은 노란색, #000000은 검은색, #ffffff은 흰색이다.

1장에서는 흥미로운 이야기는 머리에 잘 들어오고, 그렇지 않은 이야기는 잘 안들어왔는데, 비트에 대한 이해도가 높은 것은 개발자의 기본 소양인 것 같다는 생각이 들었다. 그래서 반드시 잘 이해가 되지 않았던 부분들은 꼭 복습을 하고 비트에 대한 이해도를 높여야겠다. 특히 2의 보수 표현법과 IEEE 754 부동소수점 표현법의 연산에 대해 잘 알아야겠다. 그리고 인코딩... 꼭 공부해야겠다. 마무리하며, 책에 조금 웃겼던 농담이 있었는데, "세상에는 10종류의 사람이 있다. 2진수를 이해나는 사람과 2진수를 이해하지 못하는 사람이다"이다. 친구들한테 써 먹어야겠다.

📖 2장. 전자 회로의 조합 논리

2장은 컴퓨터는 어떤 논리를 통해 비트를 다루는지에 대해 배울 수 있었다.

전이 함수에 대해 알게 되면서 왜 컴퓨터가 10진 숫자 대신 비트를 사용하는지 배웠다. 이후 하드웨어에서 비트를 사용해야 하는 이유 다음으로, 비트를 다루는 하드웨어를 만드는 방법에 대해 배울 수 있었다. 하지만, 전자기학에 대해 공부를 안한지 너무 오래되어서인지.. 이를 이해하기가 생각보다 굉장히 복잡했고 어려워서.. 다음번에 다시 돌아와 공부를 해야겠다. 우선 3장으로 넘어가고 언젠간 다시 2장으로 돌아와 하드웨어의 역사에 대해 공부해야겠다.

📖 3장. 메모리와 디스크의 핵심: 순차 논리

(독서 예정)

📖 4장. 컴퓨터 내부 구조

(독서 예정)

📖 5장. 컴퓨터 아키텍처와 운영체제

(독서 예정)

📖 6장. 입출력과 네트워킹

(독서 예정)

📖 7장. 데이터 구조와 처리

(독서 예정)

📖 8장. 프로그래밍 언어 처리

(독서 예정)

📖 9장. 웹 브라우저

(독서 예정)

📖 10장. 어플리케이션 프로그래밍과 시스템 프로그래밍

(독서 예정)

📖 11장. 성능 향상을 위한 알고리즘 기법

(독서 예정)

📖 12장. 병렬성과 비동기성

(독서 예정)

📖 13장. 컴퓨터 보안

(독서 예정)

📖 14장. 세상을 바꾸는 기계 지능

(독서 예정)

📖 15장. 훌륭한 프로그래머가 되기 위한 팁과 경험담

(독서 예정)

이 글에서는 DFS(깊이우선탐색)에 대해 다뤄보려고 한다. DFS는 그래프 탐색의 방법 중 하나이다. 그래프를 탐색할 때, vertice(정점)에 있는 edge(간선) 중 하나를 선택해 이동하고, 다음 vertice에서 또 한 edge를 선택해 이동하고, 이를 반복하다가 더 이상 이동할 수 없게 되면 이전의 vertice로 돌아와서 다른 edge를 선택해 이동하며 그래프를 탐색하는 방법을 DFS라고 한다. DFS를 구현할 때는 stack(스택) 자료구조를 이용한다. 왜냐하면 가장 마지막에 들어간 데이터가 가장 먼저 나오는 stack의 원리를 이용하여 바로 이전의 vertice를 쉽게 찾을 수 있기 때문이다. 제일 처음 방문하는 vertice에 있는 edge 중 하나를 택해 다음 vertice로 이동하고, 방문한 vertice를 stack에 넣는다. 이를 반복하여 가장 깊은 곳의 vertice까지 방문하고, edge가 없게 되면 이때 stack의 top에 있는 바로 이전의 vertice를 꺼내, 아까 탐색하지 않았던 edge로 이동한다. 이 반복하여 그래프의 모든 vertice를 탐색하는 방법이 DFS이다.

💻 코드

void DFS(int Vertice){
    Visited[Vertice] = true;
    cout << Vertice << " ";
    for (int i = 0; i < Graph[Vertice].size(); i++){
        int Edge = Graph[Vertice][i];
        if (!Visited[Edge])
            DFS(Edge);
    }
}

위 코드는 DFS의 간단한 코드이다. 💡 동작원리에서 설명한 것과는 달리 stack 자료구조를 사용하지 않고 구현되어 있다. 그 이유는 DFS를 재귀함수 형식으로 짜게 되면, 자연스럽게 재귀함수를 호출하게 되면 stack 자료구조를 만들어내기 때문이다. 이제 DFS 코드에 대해 설명하겠다. 먼저 Vertice를 입력받으면 탐색했다고 저장하고 출력한다. 이후 이 Vertice에 붙어 있는 Edge들을 통해 다음 Vertice로 이동한다. 이때 제일 처음 나오는 Edge를 통해 다음 Vertice로 넘어기 위해 DFS 함수를 재귀로 호출해준다. 이렇게 DFS 방식으로 그래프를 탐색한다.

⏱ 시간복잡도

DFS의 시간복잡도는 $O(|V|+|E|)$이다. $|V|$는 Vertice의 개수, $|E|$는 Edge의 개수이다.

$O(|V|+|E|)$

이 글에서는 Radix Sort(기수정렬)에 대해 다뤄보려고 한다. Radix Sort의 원리는 데이터의 낮은 자리수를 이용하여 정렬하는 것이다. Radix Sort는 다른 원소들과 비교 연산을 하지 않아 정렬 속도가 굉장히 빠르다. 그러나 정렬과정에 추가 메모리가 필요하다.

먼저, Radix Sort를 실행하는데에는 추가 메모리인 0 ~ 9까지의 Backet이 필요하다. 이 Backet은 Queue(큐)가 배열을 이용해 연속적으로 할당이 된 자료구조를 가지고 있다. 정렬할 데이터의 값이 {121, 1, 432, 423, 564, 44, 778, 57, 168, 92}이라고 하자. 이제 이 값들의 일의 자리 수에 맞게 Backet에 넣어보자. 위 그림처럼 된다. 이제 이것을 다시 배열에 넣으면, {121, 1, 432, 92, 423, 564, 44, 57, 778, 168}이 된다. 이번에는 십의 자리 수에 맞게 Backet에 넣어보자. 위 그림처럼 된다. 이제 이것을 다시 배열에 넣으면, {1, 121, 423, 432, 44, 564, 168, 57, 778, 92}이 된다. 이번에는 백의 자리 수에 맞게 Backet에 넣어보자. 위 그림처럼 된다. 이제 이것을 다시 배열에 넣으면, {1, 44, 57, 92, 121, 168, 423, 432, 564, 778}이 된다. 배열을 살펴보면 정렬이 끝났다. 이것이 Radix Sort이다. 배열의 데이터 중 가장 큰 자릿수만큼 위 방법을 시행해주면 배열의 모든 데이터의 정렬이 끝난다.

💻 코드

void Radix_Sort(){
    int Max_Value = 0;
    for(int i = 0; i < N; i++){ if(Max_Value < Arr[i]) Max_Value = Arr[i]; }

    int Radix;
    for(Radix = 1; Radix < Max_Value; Radix *= 10){}

    for (int i = 1; i <= Radix; i = i * 10){
        for (int j = 0; j < N; j++){
            int Temp = (Arr[j] / i) % 10;
            Backet[Temp].push(Arr[j]);
        }

        int Idx = 0;
        for (int j = 0; j < 10; j++){
            while (!Backet[j].empty()){
                Arr[Idx] = Backet[j].front();
                Backet[j].pop();
                Idx++;
            }
        }
    }
}

위 코드는 Radix Sort의 간단한 코드이다. 우선 정렬할 배열에서 가장 큰 값을 찾는다. 그리고 가장 큰 값의 자릿수를 구하여, Backet을 이용해 배열을 정렬해야하는지를 찾는다. 그리고 💡 동작원리에서 설명한 것 처럼, Backet에 자릿 수를 참고하여 넣는다. X자릿수의 값을 구하는 코드는 (원소 / X) % 10을 하면 된다(이유는 계산해보길..). 그리고 다시 Backet에서 수를 빼면서 배열에 순서대로 저장한다. 이를 최대값의 자릿수만큼 반복하여 배열을 정렬한다.

⏱ 시간복잡도

Radix Sort의 시간복잡도는 $O(dN)$이다. 빅오 표기법에 의해 $O(N)$이다. 하지만, 단점으로 Backet으로 사용할 Queue로 이루어진 배열을 선언해주어야 하기 때문에 그만큼 추가 메모리가 든다.

$O(dN) = O(N)$

이 글에서는 Shell Sort(쉘정렬)에 대해 다뤄보려고 한다. Shell Sort는 Insertion Sort(삽입정렬)을 보완한 정렬로, Shell Sort의 원리는 Insertion Sort(삽입정렬)에 있다. Shell Sort는 정렬할 배열을 부분배열로 쪼개서 부분배열 각각에 대해 Insertion Sort을 실행하고, 배열을 합친 후 다시 또 쪼개서 Insertion Sort를 진행하고, 이 방법을 반복하여 배열을 정렬한다.

먼저 Shell Sort에서 배열을 어떻게 쪼개는지 살펴보자. 바로 간격을 두고 배열을 쪼개는 것이다. 이때 간격을 Gap(간격)이라고 부른다. 배열의 길이가 10이고 Gap이 5라고 가정하면 부분배열들의 인덱스는 {0,5}, {1,6}, ... {4,9}로 쪼개지는 것이다. 그리고 각각의 부분배열들에 대하여 모두 Insertion Sort를 실행한다. 이제 다시 Gap을 얼마로 두고 배열을 쪼갤 것인지 생각해보자. Shell Sort에서는 이전 Gap의 절반값으로 설정한다. 이때 Gap의 절반값이 짝수인 경우에는 (Gap/2 + 1)하여 홀수로 만들어준다. 그리고 쪼개진 부분배열들에 대하여 Insertion Sort를 진행한다. 이를 Gap이 1이 될 때까지 계속 반복하면 배열이 정렬된다. 아래 그림을 참고하자.

💻 코드

void New_Insertion_Sort(int Start, int Gap){
    for(int i = Start + Gap; i < N; i = i + Gap){
        int temp = Arr[i]; 
        int j;
        for(j = i - Gap; j >= Start; j = j - Gap){
            if(Arr[j] > temp) Arr[j + Gap] = Arr[j];
            else break;
        }
        Arr[j + Gap] = temp;
    }
}

void Shell_Sort(){
    for(int Gap = N/2; Gap > 0; Gap = Gap/2){
        if((Gap % 2) == 0) Gap++;
        for(int i = 0; i < Gap; i++){ New_Insertion_Sort(i, Gap); }
    }
}

위 코드는 Shell Sort(병합정렬)의 간단한 코드이다.

먼저 New_Insertion_Sort함수를 보자. Insertion Sort와 코드가 거의 똑같다. 다른점은 Gap을 추가하여 부분배열을 정렬한다는 점인데, 이에 대해서는 따로 설명하지 않겠다.

다음은 Shell_Sort함수이다. 반복문을 이용해서 Gap을 배열의 길이/2에서 시작하여 Gap이 1이 될때까지 New_Insertion_Sort함수를 실행시켜준다. 이때 Gap이 짝수이면 +1을 하여 홀수로 만들어준다.

⏱ 시간복잡도

Shell정렬의 시간복잡도는 최선의 경우, 최악의 경우, 평균적인 경우로 나뉜다. 각각 $O(N)$, $O(N^2)$, $O(N^{1.3,1.5})$이다.

Best case : $O(N)$ Worst case : $O(N^2)$ Average case : $O(N^{1.3,1.5})$

이 글에서는 Merge Sort(병합정렬)에 대해 다뤄보려고 한다. Merge Sort의 원리는 배열을 나누었다가, 다시 합치는 것에 있다. 따라서, 분할 정복 알고리즘이라고 할 수 있다. 다시 합치는 과정에서 정렬을 하기 때문에 Merge Sort(병합정렬)이라고 한다.

Merge Sort의 첫 단계는 배열을 크기가 1이 될 때까지 분할하는 것이다. 끝이다. 이제 다음 단계로 넘어가자.

Merge Sort의 다음 단계는 분할한 배열들을 정렬하면서 합치는 것이다. 분할된 배열들을 병합할 때는 2개씩 합친다. 분할된 배열 중 왼쪽에 있는 배열(p ~ q)의 인덱스를 가르킬 변수(Left_Index라고 하자), 오른쪽에 있는 배열(q+1 ~ r)의 인덱스를 가르킬 변수(Right_Index라고 하자), 그리고 병합되는 배열의 인덱스를 저장할 변수(Merge_Index라고 하자), 총 세 변수가 필요하다. 또한, 분할된 배열의 데이터들이 정렬된 채로 합쳐질 때, 임시로 저장할 공간이 필요하다. Left_Index에 저장된 값과 Right_Index에 저장된 값을 비교하여 작은 값을 임시 배열의 인덱스가 p인 공간에 저장한다. 그리고 저장된 변수가 다음 원소를 바라볼 수 있도록 +1해준다. 이 방법을 반복하면 두 배열을 병합하는 과정에서 오름차순으로 원소가 저장되게 된다. 만약 Left_Index 또는 Right_Index 중 하나가 분할된 배열의 끝까지 도달하게 되면, 아직 끝까지 도달하지 못한 Index는 남은 원소를 별도의 비교없이 순서대로 저장해주면 된다. 이후 임시 배열에 정렬된 범위(p ~ r)만큼 본래의 배열에 복사해준다.

💻 코드

void Merge(int Left, int Mid, int Right){
    int Left_Index = Left;
    int Right_Index = Mid + 1;
    int Merge_Index = Left;

    while(Left_Index <= Mid && Right_Index <= Right){
        if(Arr[Left_Index] <= Arr[Right_Index]) Sorted[Merge_Index++] = Arr[Left_Index++];
        else Sorted[Merge_Index++] = Arr[Right_Index++];
    }

    if(Left_Index > Mid){ for(int i = Right_Index; i <= Right; i++) Sorted[Merge_Index++] = Arr[i]; }
    else { for(int i = Left_Index; i <= Mid; i++) Sorted[Merge_Index++] = Arr[i]; }

    for(int i = Left; i <= Right; i++){ Arr[i] = Sorted[i]; }
}

void Merge_Sort(int Left, int Right){
    if(Left < Right){
        int Mid = (Left + Right)/2; 
        Merge_Sort(Left, Mid);
        Merge_Sort(Mid + 1, Right);
        Merge(Left, Mid, Right);
    }
}

위 코드는 Merge Sort(병합정렬)의 간단한 코드이다.

먼저 Merge함수에 대해 설명하겠다. 💡동작원리에서 설명했듯이, Left_Index, Right_Index, Merge_Index 세 변수를 선언해주고, 각각 왼쪽 배열의 첫 인덱스, 오른쪽 배열의 첫 인덱스, 병합될 배열의 첫 인덱스를 저장해준다. 그리고 Left_Index, Right_Index 중 하나가 자신의 범위를 넘어갔을 때 멈추는 조건으로 반복문을 만들어준다. 이때 두 Index의 값을 비교하며 오름차순에 맞게 Sorted(임시배열)에 차근차근 원소를 저장해준다. 이후 두 Index 중 아직 다 저장을 못해준 배열을 마저 저장해준다. 그리고 마지막으로 Arr(본배열)에 Sorted(임시배열)을 복사해주면 두 배열이 오름차순으로 정리된 채 저장이 된다.

다음은 Merge_Sort함수이다. 우선 조건문으로 Left < Right을 해서 배열이 1개 단위까지 쪼개졌을 때 Merge함수, 즉 병합이 되도록 해준다. 배열이 1개 단위로 쪼개는 방법은, Mid 변수를 선언하여 Merg_Sort함수를 Left부터 Mid까지, Mid+1부터 Right까지 재귀호출방식을 사용한다. 조건문에 의해 배열이 1개 단위까지 쪼개지게 될 것이고, 이후에 Merge함수가 호출되어 배열 전체가 병합된다.

⏱ 시간복잡도

Merge Sort(병합정렬)의 시간복잡도를 계산해보면 Quick Sort(퀵소트)의 이상적인 경우의 시간복잡도와 같게 된다. Merge Sort은 Quick Sort와 달리 쪼개지는 것이 항상 일정하기 때문에, 모든 경우에 시간복잡도는 같다. 따라서 Merge Sort의 시간복잡도는 $O(NlogN)$이다.

그러나 Merge Sort의 시간복잡도가 항상 $O(NlogN)$인만큼 단점도 있다. 바로 공간복잡도이다. Merge Sort는 병합하는 과정에서 임시로 저장할 배열의 할당이 필요했다. 따라서 정렬해야하는 배열의 크기만큼의 임시배열이 필요하다. Merge Sort에 필요한 공간은 Quick Sort의 두배이다.

$O(NlogN)$

이 글에서는 Heap Sort(힙정렬)에 대해 다뤄보려고 한다. Heap Sort(힙정렬)의 원리는 완전이진트리(complete binary tree)에 있다. complete binary tree(완전이진트리)란, 트리의 모든 Node가 빈 공간 없이 순차적으로 채워져 있는 Tree를 말한다. 오름차순으로 정렬을 할 때는 Max Heap(최대힙), 내림차순으로 정렬을 할 때는 Min Heap(최소힙)을 이용한다. 이때, Max Heap(최대힙)과 Min Heap(최소힙)이란 complete binary tree(완전이진트리)이며, 각각 "부모의 노드값이 자식의 노드값보다 큰 꼴", "부모의 노드값이 자식의 노드값보다 작은 꼴"이다. 본인은 오름차순으로 정렬하는 Heap Sort(힙정렬)을 설명할 것이기 때문에, Max Heap(최대힙)을 사용한다.

Heap Sort(힙정렬)의 첫 번째 단계는 배열을 complete binary tree(완전이진트리)로 바라보고, 이를 Max Heap(최대힙)으로 만드는 것이다. 배열을 complete binary tree(완전이진트리)로 바라보는 방법은 따로 작성하지 않겠다. Max Heap(최대힙)으로 배열이 정리되어 있어야 뒤에 나올 Heapify 함수를 이용하여 배열을 오름차순으로 정렬할 수 있기 때문이다. Heapify 함수는 Tree내에서의 어떠한 원소가 Max Heap(최대힙)의 성질에 맞게 자기 자리를 찾아가는 과정이다. complete binary tree(완전이진트리)를 Max Heap(최대힙)으로 바꾸는 과정에서 Heapify 함수를 사용한다. 바꿔주는 과정은 원소가 배열의 1부터 N까지 있을 때, N/2번째 원소부터 1까지 Heapify 함수를 실행시켜주는 것이다. N/2번째 원소부터 실행시켜주는 이유는 complete binary tree(완전이진트리)의 특성상 N/2+1번째 원소부터는 자식노드가 없기 때문이다. Heap Sort(힙정렬)의 두 번째 단계는 Max Heap(최대힙)의 성질과 Heapify 함수를 이용하여 배열을 오름차순으로 정렬하는 것이다. Max Heap(최대힙)의 성질에 의해서 Root Node가 모든 Node 중 가장 큰 Node일 것이다. 우리는 오름차순으로 배열을 정렬하고 있기 때문에, 이 Root Node와 N번째 원소를 스왑해준다. 그럼 배열 중 가장 큰 값이 제일 뒤로가고, Max Heap(최대힙) 상태가 깨지게 된다. 하지만 이전에 Max Heap(최대힙)상태에서 단 한 원소만 바뀐 것이기 때문에, Heapify함수를 이용해서 바뀐 Root Node를 올바른 위치로 보내주기만 하면 Max Heap(최대힙) 상태가 곧바로 돌아오게 된다. 따라서 Heapify함수를 이용해 Root Node를 올바른 위치로 보내주는데, 이때 유의해야할 점은 배열의 제일 끝에 저장된 가장 큰 값을 제외하고 1부터 N-1까지만 Heapify함수를 실행시켜야한다. 그럼 1부터 N-1까지 Max Heap(최대힙)상태가 되는데, 이때 다시 Root Node와 N-1번째 원소를 스왑해준다. 이후 다시 Heapify함수를 이용해 1부터 N-2까지 Max Heap(최대힙)을 만들어준다. 이를 계속 반복하면 배열이 오름차순으로 정렬된다.

💻 코드

void Heapify(int Cur, int N){
    int Cur_Idx = Cur;
    int Left_Child = Cur*2;
    int Right_Child = Cur*2 + 1;

    if ((Left_Child <= N) && (Arr[Left_Child] > Arr[Cur_Idx])) Cur_Idx = Left_Child;
    if ((Right_Child <= N) && (Arr[Right_Child] > Arr[Cur_Idx])) Cur_Idx = Right_Child;

    if (Cur_Idx != Cur){
        swap(Arr[Cur_Idx], Arr[Cur]);
        Heapify(Cur_Idx, N);
    }
}

void Heap_Sort(){
    for(int i = N/2; i >= 1; i--){ Heapify(i, N); }
    for (int i = N; i >= 2; i--){
        swap(Arr[i], Arr[1]);
        Heapify(1, i - 1);
    }
}

위 코드는 Heap Sort(힙정렬)의 간단한 코드이다.

우선 Heapify 함수에 대해 설명하겠다. Cur은 제자리를 찾아가야하는 원소의 위치이고, Cur_Idx에 다시 저장한다. Left_Child와 Right_Child는 배열을 complete binary tree(완전이진트리)의 성질을 이용하여 각각 저장해준다. 제자리를 찾아가야하는 원소 중 자신보다 더 큰 자식이 있다면 바꿔줘야한다. 이때 두 자식이 모두 자신보다 크면 두 자식 중 더 큰 자식을 저장해주어야한다. 이를 감안하여 코드가 짜여 있는데, Left_Child가 더 커서 Cur_Idx에 저장이 되었더라도, 다시 Right_Child가 더 크면 Cur_Idx에 Right_Child가 저장되게 코드가 짜여있다. 이후 Cur_Idx가 변화를 했다면, 기존의 Cur과 스왑을 하여 원소과 그 자식을 스왑해주고 Heapify함수를 재귀호출해준다.

다음은 Heap_Sort 함수이다. 첫 번째 줄의 반복문은 정렬이 되지 않은 배열을 Max Heap(최대힙)으로 바꿔주기 위한 것이다. 코드에 대한 설명은 위에서 했기 때문에 하지 않겠다. 자, 이제 배열은 Max Heap(최대힙)으로 정렬이 되었다. 이제 Max Heap의 Root Node를 제일 뒤로 보내주고 다시 Heapify함수를 호출하여 Max Heap(최대힙)을 만들고, 이를 Max Heap(최대힙)의 크기가 2가 될 때까지 반복해준다. 그럼 배열은 오름차순으로 정렬된다.

⏱ 시간복잡도

Heap Sort(힙정렬)의 시간복잡도를 계산해보자. 먼저 Heapify 함수의 시간복잡도를 계산해야한다. Heapify 함수의 시간복잡도는 최대 $logN$이다. complete binary tree(완전이진트리)의 성질에 의해 깊이가 $logN$이 되고, 최대깊이까지 재귀호출이 되었을 때 최대 시간복잡도가 나오기 때문이다.

이제 Heap Sort(힙정렬)의 시간복잡도를 계산해보자. Heap_Sort() 함수에서 Max Heap을 생성해줄 때 걸리는 시간복잡도는 Heapify함수를 N/2만큼 실행하기 때문에, $O(NlogN/2) = O(NlogN)$이 된다. 또한, 오름차순으로 정렬하는 반복문에서도 Heapify함수가 $N-1$번 실행이 되기 때문에 시간복잡도가 $O((N-1)logN) = O(NlogN)$이 된다. 따라서, Heap Sort(힙정렬)의 시간복잡도는 $O(NlogN)$이다.

$O(NlogN)$

이 글에서는 Quick Sort(퀵정렬)에 대해 다뤄보려고 한다. Quick Sort(퀵정렬)의 원리는 분할 정복 방법에 있으므로, 분할 파트와, 정복 파트를 나누어서 설명한다.

우선, 분할 파트이다. 정렬해야하는 배열을 Array라고 하자. Array에서의 아무 원소를 골라서 고른 원소를 기준으로 분할을 한다. 이때 고른 원소는 pivot(피벗)이라고 한다. Array에서 pivot보다 작은 값은 pivot의 왼쪽으로, 큰 값은 모두 오른쪽으로 보낸다. 이 과정을 partition(파티션)이라고 한다.

이제 정복 파트를 보자. 정복 파트는 위 분할 파트를 재귀적으로 호출하는 것이다. 앞 과정에서의 pivot의 위치가 q라면, Array의 첫 원소부터 q-1번째 원소까지와 q+1번째 원소부터 마지막 원소까지 다시 분할 파트를 해주는 것이다. 이를 재귀적으로 호출하며 Array를 정렬해 정복한다.

💻 코드

int Partition(int Left, int Right){
    int Pivot_Value = Arr[Left];
    int Left_Mark = Left + 1, Right_Mark = Right;
    while(Left_Mark <= Right_Mark){
        while(Arr[Left_Mark] <= Pivot_Value){ Left_Mark++; }
        while(Arr[Right_Mark] > Pivot_Value){ Right_Mark--; }
        if(Left_Mark < Right_Mark) { swap(Arr[Left_Mark],Arr[Right_Mark]); }
    }
    swap(Arr[Left], Arr[Right_Mark]);
    return Right_Mark;
}

void Quick_Sort(int Left, int Right){
    if (Left < Right){
        int Pivot = Partition(Left, Right);
        Quick_Sort(Left, Pivot - 1);
        Quick_Sort(Pivot + 1, Right);
    }
}

위 코드는 Quick Sort(퀵정렬)의 간단한 코드이다.

우선, Partition 함수부분부터 설명하겠다. pivot(피벗)은 항상 정복하려고 하는 부분 배열의 가장 앞을 바라보게 설정했고, Pivot_Value라고 변수명을 설정하여 pivot(피벗)의 데이터값을 저장하였다. pivot(피벗)을 기준으로 작은 값과 큰 값을 나누기 위해서는 두 개의 포인터가 필요해서 Left_Mark, Right_Mark라는 변수를 선언하여 각각 부분 배열의 두 번째 값과 제일 마지막 값을 저장해주었다. 이제 본격적으로 pivot(피벗)을 기준으로 작은 값과 큰 값을 나누어주는데 나누는 방식은 Left_Mark는 오른쪽으로 탐색하며 pivot(피벗)보다 큰 값을 찾고, Right_Mark는 왼쪽으로 탐색하며 pivot(피벗)보다 작은 값을 찾는다. 그 값을 찾게 되면, 서로 스왑해준다. 이를 Left_Mark와 Right_Mark가 만날 때까지 반복해주면 pivot(피벗)을 기준으로 작은 값과 큰 값이 분할이 된다. 마지막으로 pivot(피벗)과 Right_Mark를 스왑해주면 pivot(피벗)보다 작은 값은 앞으로, 큰 값은 뒤로 정렬되게 된다. 그리고 Partition 함수는 pivot(피벗)의 인덱스 값을 리턴해주는데, pivot(피벗)과 Right_Mark를 스왑했기 때문에 Right_Mark를 리턴해주면 된다.

이제 Quick_Sort 함수를 살펴보자. Quick_Sort함수의 제일 첫 부분은 if(Left < Right)인데 이 부분은 배열의 분할을 최소 2개 단위까지 분할 정복하기 위한 것이다. Quick_Sort 함수는 Partition 함수에 비해 비교적 간단하다. Partition 함수로부터 pivot(피벗)의 인덱스 값을 리턴받는다. pivot(피벗)을 기준으로 앞 부분배열과 뒷 부분배열을 나누어서 재귀함수를 호출하여 정복하면 된다. 아래 그림은 코드를 시각적으로 설명한다.

⏱ 시간복잡도

Quick Sort(퀵정렬)은 pivot(피벗)의 인덱스에 따라서 불균등하게 나뉘기 때문에 최선의 경우와 최악의 경우가 나뉘게 된다.

먼저 최선의 경우를 살펴보자. 최선의 경우는 pivot(피벗)이 모든 경우에 정복하려는 배열의 정중앙에 들어가는 것이다. 그렇게 되면 퀵 정렬이 한 번 호출 될 때마다 1/2로 쪼개진다. 따라서, 퀵 정렬의 재귀 호출 깊이는 $log_2N$이다. 한 호출마다 $N$번의 시행이 되기 때문에, 최선의 경우에 시간복잡도는 $O(Nlog_2N)$이다.

이번엔 최악의 경우를 살펴보자. 최악의 경우는 pivot(피벗)이 모든 경우에 정복하려는 배열의 제일 앞에 들어가는 것이다. 그렇게 되면 퀵 정렬의 재귀 호출 깊이는 $N$이 된다. 따라서 최악의 경우에 시간복잡도는 $O(N^2)$이다.

Best case : $O(Nlog_2N)$ Worst case : $O(N^2)$

이 글에서는 Counting Sort(계수정렬)에 대해 다뤄보려고 한다. Counting Sort(계수정렬)의 원리는 원소값의 개수를 세고 새로운 배열에 그 갯수에 따라서 위치를 설정해주는 것이다. 새로운 배열을 선언하고, 정렬할 배열의 원소들을 계산해서 저장해준다. 새로운 배열의 이름을 Count라고 하자. Count의 인덱스 값은 정렬할 배열의 원소값이 될 것이고, Count의 데이터 값은 인덱스 값의 갯수가 될 것이다. 예를들어 정렬할 배열에 3이라는 원소가 5개가 있었다면, Count[3] = 5가 되는 것이다. 정렬할 배열을 i=0부터 i=N-1까지 한 번만 탐색하면 위 그림처럼 Count배열을 채울 수 있다.

이제 Output 배열을 선언하여 기존의 배열을 정렬한다. Output에 올바르게 정렬을 하기 위해서, Count의 값을 Count의 인덱스가 Output에 들어갈 수 있는 최대 인덱스로 바꾸어준다. 이는 Count의 값을 자신보다 앞에 있는 원소들의 합으로 바꾸어주면 된다. Count[i] = Count[i] + Count[i-1] 점화식을 이용한다.

드디어 Output 배열을 채울 수 있게 되었다. 이제는 정렬할 배열을 다시 탐색하며 Count을 참고해 Output 배열에 차곡차곡 원소를 채워넣으면 된다. Output 배열에 원소를 넣을 때마다, Count의 값은 -1을 하여 Output 배열이 완성됐을 때, Count의 값은 Count의 인덱스가 Output에 들어간 최소 인덱스로 되도록 한다. 이것이 Countring Sort(계수정렬)이다.

💻 코드

void Counting_Sort(){
    for (int i = 0; i < N; i++) Count[Arr[i]]++;
    for (int i = 1; i <= Max; i++) Count[i] = Count[i] + Count[i - 1];
    for (int i = 0; i < N; i++){
        Count[Arr[i]]--;
        Output[Count[Arr[i]]] = Arr[i];
    }
}

⏱ 시간복잡도

Countring Sort(계수정렬)의 시간복잡도는 다른 정렬과 다르게 타 원소와 비교를 하여 스왑하는 방식으로 정렬을 하는 것이 아닌, 단지 원소의 개수를 세는 것으로 자연스럽게 정렬이 되는 알고리즘이기 때문에 시간복잡도는 $O(N)$이다.

하지만, 정렬해야하는 데이터 값 중 최대값의 크기만큼의 배열을 선언해줘야하기 때문에 데이터 값의 범위가 넓을 수록 그만큼 공간복잡도가 커져서 실행속도가 늦어진다. 그렇기 때문에 Countring Sort(계수정렬)을 사용하려면 데이터 값의 범위를 반드시 확인해야한다.

$O(N)$

이 글에서는 Selection Sort(선택정렬)에 대해 다뤄보려고 한다. Selection Sort(선택정렬)의 원리는 정렬되지 않은 부분배열에서 가장 큰 값, 혹은 가장 작은 값을 찾고 스왑하여 정렬하는 것이다. 위 그림은 오름차순으로 정렬하는 Selection Sort(선택정렬)의 동작원리 중 첫 단계를 그림으로 표현한 것이다. 시행의 목적은 가장 작은 값을 선택해 제일 앞으로 보내주는 것이다. 그래서 정렬되지 않은 부분배열의 가장 앞 원소를 가장 작은 값이라고 가정하고, 뒤에 값들을 비교하며 가장 앞 원소보다 작은 값이 나오면 그 값의 인덱스를 저장하는 방식으로 계속 반복한다. 배열의 끝까지 탐색했을 때, 제일 처음 시작한 원소와 가장 작은 값의 인덱스가 다르면 스왑해준다. 이 시행을 배열이 정렬 될 때까지 해준다. 이렇게 가장 큰 값, 또는 가장 작은 값을 선택하여 정렬시켜주는 방식이 Selection Sort(선택정렬)이다.

💻 코드

void Selection_Sort(){
    for(int i = 0 ; i < N; i++){
        int temp = i;          
        for(int j = i  + 1; j < N; j++)  {
            if(Arr[j] < Arr[temp]) temp = j;   
        }
        if(i != temp) swap(Arr[i], Arr[temp]);   
    }
}

⏱ 시간복잡도

연산 횟수를 계산해보면, $(N-1) + (N-2) + ... + (1) = N(N-1)/2$ 이므로 시간복잡도는 $O(N^2)$이 된다.

$O(N^2)$

이 글에서는 Insertion Sort(삽입정렬)에 대해 다뤄보려고 한다. Insertion Sort(삽입정렬)의 원리는 인덱스가 1부터 N-1까지의 원소를 순서대로 하나씩 제 위치를 찾아서 삽입하며 정렬하는 것이다. 위 그림은 오름차순으로 정렬하는 Insertion Sort(삽입정렬)의 동작원리를 그림으로 표현한 것이다. 1번 원소부터 N-1번 원소의 위치를 찾아서 그 사이에 넣고 배열을 뒤로 미는 것을 확인할 수 있다. i번째 원소의 위치를 찾는 과정은 다음과 같다. i-1, i-2, ... 를 하나씩 탐색해, i번째 원소보다 더 크면 뒤로 한칸씩 밀고, i번째 원소보다 작은 원소가 나타나면 탐색을 멈추고 그 자리에 i번째 원소를 삽입한다. 이것이 Insertion Sort(삽입정렬)이다.

💻 코드

void Insertion_Sort(){
    for (int i = 1; i < N; i++) {
        int temp = Arr[i];
        int j;
        for(j = i - 1; j >= 0; j--){
            if(Arr[j] > temp) Arr[j + 1] = Arr[j];
            else break;
        }
        Arr[j + 1] = temp; 
    }
}

⏱ 시간복잡도

Insertion Sort(삽입정렬)는 i번째 원소의 위치를 찾는 과정에서의 연산 횟수가 일정하지 않아서 최선의 경우와 최악의 경우로 나뉘게 된다.

먼저 최선의 경우를 살펴보자. 최선의 경우는 모두 한 번만에 i번째 원소의 위치를 찾게 되는 것이기 때문에 연산 횟수가 N-1이 된다. 따라서 시간복잡도는 $O(N)$이다.

최악의 경우를 살펴보자. 최악의 경우에는 모든 i번째 원소에 대하여 위치를 찾을 때, i-1번째 원소부터 0번째 원소를 탐색하는 것이다. 따라서 연산 횟수가 $1 + 2 + ... + N-1 = N(N-1)/2$이므로 시간복잡도는 $O(N^2)$이다.

Best case : $O(N)$ Worst case : $O(N^2)$

💡 동작원리

이 글에서는 Bubble Sort(버블정렬)에 대해 다뤄보려고 한다. Bubble Sort(버블정렬)의 원리는 가장 인접한 두 원소를 비교하여, 차순에 맞게 스왑하는 것이다.

위 그림은 오름차순으로 정렬하는 Bubble Sort(버블정렬)의 동작원리를 그림으로 표현한 것이다. i번째 원소와 i+1번째 원소를 비교하여 i번째 원소가 크면 스왑한다. 이를 끝까지 한 번 시행하면, 배열에서 가장 큰 원소가 N번째에 위치하게 된다. 이렇게 정렬되는 원소를 제외하고 계속 시행하면 배열이 오름차순으로 정렬된다. 이것이 Bubble Sort(버블정렬)이다.

💻 코드

void Bubble_Sort(){
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N - i; j++){
            if(Arr[j] > Arr[j + 1]){
                swap(Arr[j], Arr[j + 1]);
            }
        }
    }
}

⏱ 시간복잡도

(N-1) + (N-2) + ... + 1 = N(N-1)/2 이므로 시간복잡도는 $O(N^2)$가 된다.

$O(N^2)$

내 프로필은 solved.ac 에서 확인할 수 있다.

📝목표 (for 💎Diamond V💎)

• AC RATING: 2200
• Class 7: 220
• 그리고 SW마에스트로 연수생이 되는 그날까지..

  ⏱기한

• 이용* 전역 전까지..