꿈 꾸는 누렁이

자 오늘도 학습했던 원형 양방향 연결 리스트를 정리할 때가 됐다. 이게 정리를 바로바로 안 하다보니 후, 코드를 다시 이해해야한다. 뭐 복습도 되고 참 좋다;;;

먼저 오늘 할 것은

원형 - 무한 순회가 가능한 -> 그래서 순회에 조건이 꼭 붙는,
양방향 - 노드의 양쪽 링크가 존재하는 -> 그래서 원형 순회 실현이 가능한
연결 리스트

를 포스팅 한다.

원형이라고 해서 개인적으로 위와 같은 형태로  생각하면 혼란만 가중할 것이라고 생각한다. 아래와 같이 말이다.

그래서 우리는 머릿속의 형태를 정해놓고 시작해보고자 한다.

이러한 형태 임을 꼭 기억하고 있어야 한다.

노드 삽입 연산

삽입 연산은 노드가 없을 때와 있을 때로 나눈다.

크 따로 부가 설명이 필요 없을 것 같다ㅋ 

노드 삭제 연산

삭제는 간단하다. 그림 하나로 표현 가능하다.

그 이외에 순회 연산

순회 연산은 그냥 노드의 링크를 순방향/역방향으로 타는 인덱스 포인터를 만들어서 순회를 하면 된다. 다만, 원형 연결 리스트인 만큼 무한 반복에 빠질 수 있기 때문에 아래와 같은 조건을 넣어 무한 반복에서 탈출하도록 해야한다.

위 코드는 순방향 순회, 역방향 순회 모두 마찬가지로 해당되는 부분이다.

메모리 관리 부분

해당 코드에서 또한 메모리 관리 부분이 따로 있기 때문에 삭제 연산 시에도 바로 메모리를 제거 하지 않고 프로그램 종료 전에 한꺼번에 모두 free 시키도록 되어 있다.

클래스로 stack 컨테이너 어댑터로 아래와 같이 구현되어 있다.

코드 및 실행 결과

스택을 연결리스트로 구현해 보았다.

일단 기본 구조에 대한 예시를 나타낸 것이다.

먼저, 왼쪽 구조를 보자. 우리 스택이라고 생각하는 구조이다. Head는 삽입 인덱스를 나타낸다. 소위 말하는 top 변수. 그 왼쪽의 구조를 단순화시켜서 보면 오른쪽처럼 나타낼 수 있다. 오른쪽 구조에서 Head 노드는 새롭게 노드가 삽입될 때 마다 가리키는 것을 갱신시키는데, 이 현상을 자세히 보면 왼쪽 구조에서 head가 옮겨다니는 것과 같다. 

다른 현상을 가지고 생각하기 나름으로 같은 본질을 끌어냈다 크.. 윤성우 교수님께 박수를...

암튼 왼쪽이든 오른쪽이든 위와 같은 본질의 구조를 구현할 것이다.

삽입 연산

1) 헤드와 기존 최 상단 노드의 연결을 끊고, 2) 새 노드와 최상단 노드를 연결하여 새 노드를 최상단 노드로 변경하고,  그 3) 최상단 노드를 헤드가 가리키도록 헤드 값을 갱신 

삭제 연산

삭제의 기본 동작은 노란색 글씨와 빨간색 글씨로 표현을 해두었다.

파란색 글씨는 대충 이런 말이다. 할당된 메모리는 따로 이전에 만들어 뒀던 자료구조로 따로 저장하여 관리하고 프로그램 종료 시, 일괄로 삭제하기 때문에 관련 포인터만 변경하고(모든 포인터 연결을 삭제 '처리') 삭제 되었다고 생각하고 진행하라는 의미이다. 

비어짐 확인

이런 구조에서 비어짐을 확인하려면 어떻게 하면 될까? 
> Head가 NULL을 가리키면 텅 빈 상태입니다. (O)
이런 구조에서 꽉 참을 확인하려면 어떻게 하면 될까?
> 연결 리스트 기반이라 꽉 찰 것을 걱정하지 않아도 됩니다.(O) 그 걱정대신 작성자 나이 걱정을.... (ㅜ.ㅜ)

뭐 더 쓸 말이 없다.

코드 및 실행 결과

프로그램 코드를 제출하기에 앞서 복습도 할 겸,
이전에 배웠던 원형 큐를 활용하여 메모리가 생성될 때마다 원형 큐에 메모리 주소를 넣고, 프로그램이 종료될 때 일괄적으로 free~~~~~~~ 된다. 그니까 생성만 했다하면 원형 큐에 넣어제끼고, 프로그램이 끝나기 직전에 다 소멸시켜버리는 것이다. 그래서 실행 결과가 지저분하여 실행결과도 약간의 설명을 넣을 예정이다.

혹시 보는 사람이 있다면 스택 부분만 참고하면 될 듯 합니다. 앞으로도 쭉 요래요..ㅋㅋ

스택이란 정말 간단하다.

분명히 내가 이거 그림 그리면서 포스팅을 한거 같은데 아무리 블로그를 뒤져봐도 없다... 그래서 다시 하는 느낌으로 스택 첫 포스팅을 시작한다.

먼저, 

스택이란 무엇인가?

우리는 스택을 이미 알고 있다. 스택은 프링글스이다. 아래의 그림을 보자.

우리는 세 개의 감자칩 중에서 어떤 감자칩이 제일 먼저 들어갔는지 알 수 있다. 바로 A이다. 어떻게 알았지? 출입구가 하나이고, 원통 내부의 크기는 서로가 뭐 어떻게 비집고 해서 바꿀 수 있는 사이즈가 아니다. 

A가 먼저 들어갔고 -> 그 다음 B가 그 위에 쌓이고 -> 그 후 C가 들어가면서 그 위에 쌓이는 것이다.

이렇듯 스택은 쌓이는 특징을 가지고 있다. 그렇다면 안의 감자칩을 꺼내먹을 때에는 어떻게 할까? 

가장 나중에 들어간 C가 제일 먼저 다시 나오고 -> 그 다음 B가 나오고 -> 가장 먼저 들어간 A가 제일 늦게 나온다. 

이렇게 나중에 들어간 값이 제일 먼저 나오는 구조를 후입선출 구조라고 한다.

단순 배열 기반 스택에서의 삽입

어려울 것이 전혀 없다. 그냥 값이 들어오는데로 쌓아올린다고 생각하고 인덱스를 증가시키면서 값을 추가하면 된다.

하나도 어렵지 않다. 이렇게 보면 그냥 배열 끝에 값을 추가하는 것 같다. 우리는 스택에 값을 추가하는 행위를 push 라고 할 것이다. 삭제 연산을 보자. 

단순 배열 기반 스택에서의 삭제

3 값이 튀어나가면서 삭제 처리가 되어 버리고, 삽입 인덱스가 하나 감소한다.

마지막 하나 남은 1이 튀어 나가며 값이 삭제 처리 되고, 삽입 인덱스가 갈 곳을 잃는데 이 때, 삽입 인덱스를 -1로 하자. 그러면 나중에 빈 스택 상태에서 값을 추가할 때, 삽입 인덱스를 증가시키면 [-1] 에서 [0]으로 바뀌어서 자연스럽게 값을 추가하면 될 뿐만 아니라, 스택이 비어있는지 비어있지 않는지 삽입 인덱스가 -1인지 아닌지를 보면 된다.

그리고 우리는 삭제하는 연산을 pop 한다고 할 것이다.

단순 배열 기반 스택에서의 비워짐과 꽉참을 확인

또한 간단하다.
인덱스가 비워져 있는지를 확인하기 위해선 아까 삭제 연산에의 약속대로 삽입 인덱스가 -1인지를 확인하면 된다. 
인덱스가 가득차 있는지를 확인하기 위해선 현재 삽입 인덱스가 배열의 길이랑 같은지를 확인하면 된다.

코드 및 실행 결과

드디어 원형 큐이다. 자기소개 페이지를 좀 작성하느라, 기록을 하지 못했다.. ㅎㅎ ㅠ.ㅠ

일단, 원형 큐이다. 지난 포스팅 기록에서 처럼 구조로 인해 어쩔 수 없는 단점과 문제를 가지고 있는 일반 배열 기반 큐에서 개선된 것이 원형 큐이다. 그 단점이자 문제는 다음과 같다.

아니 그러면, 삽입 인덱스와 꺼냄 인덱스를 모두 초기화 시켜서 다시 앞으로 옮겨오면 되는 것 아닌가? 라는 생각이 들었었는데 이를 반박할 수 있는 사례가 또 나타난다....

바로 이 경우이다. 순서대로 읽으면 된다. 35와 43 값을 추가 후, 배열의 끝이기 때문에 가정했던대로 삽입 인덱스를 초기화 시켜서 다시 삽입하여 공간을 활용하려는 노력이 보이는 그림이다. 그럼 만약에 위 상황에서 데이터를 순회하려면 어떻게 해야하는가?

7 -> 11 -> 15 -> 35 -> 43 으로 순회를 해야할까? 아니다. 이렇게 되면 큐의 기본 원리에 제대로 위배된다. 35와 43이 먼저 나와야한다. 

위 상황에서 큐의 기본 원리를 지키며 데이터를 순회하기 위해서는
1) 꺼냄 인덱스부터 먼저 확인 후 값을 꺼낸 뒤,
2) 다시 꺼냄 인덱스를 초기화하여 인덱스 0부터 들어간 값을 꺼내며 인덱스를 증가시키고,
3) 삽입 인덱스와 접하는지를 확인한다.
-> 2, 3 을 반복한다.

나 같으면 위와 같은 짓, 안 하겠다. 원형 큐에 대해 당장 알아본다.

먼저, 왼쪽과 같은 일반 배열을 오른쪽처럼 가상으로 구부렸다고 생각하고 모든 기록을 전개할 것이다. 기본 세팅에 대해서 좀 더 설명하자면, 다음 그림과 같다.

일반 큐처럼 삽입 인덱스와 꺼냄 인덱스가 존재하며, 이름이 각각 그림과 같이 달라질 뿐이다. 그리고 각 인덱스는 대입 연산이나 삭제 연산이 진행된 후에 증가하는 형태를 기본으로 한다.

그럼 삽입과 삭제는 그림 한 장으로 설명이 가능할 것 같다.

그렇다면 삽입을 하려면 큐가 꽉 찾는지 확인해야하며, 삭제하려면 큐가 비어있는지 확인해야한다. 원형 큐의 문제가 바로 이것이기 때문에 중요하다!!!!

먼저, 다음 그림을 보면 문제가 뭔지 알 수 있다

큐가 모두 비었을 때와 가득 찼을 때의 인덱스들의 상태가 완전히 똑같다. 인덱스의 위치에 상관없이 front가 rear을 따라 잡았다는 소리는 삭제를 모두 완료했다고 볼 수 있다. 그러나, rear이 front를 따라 잡았다는 소리는 삽입을 모두 완료했다고 볼 수도 있기 때문이다. 아주 기가 막힙니다.

그래서 원형 큐를 삽입할 때, 큐의 길이 - 1 만큼만 삽입하도록 할 예정이다. 꽉 찬 상태와 텅 빈 상태는 그림과 같다.

이 약속들만 지킨다면 원형 큐를 구현하면서 기가 막힐 일은 없을 것이다.

코드 및 실행 결과

----

----

내가 퀵 정렬까지 공부할 줄은 몰랐(었)다. 역시 차근차근 해 놓는게 중요하다. 더불어 포스팅도 그 때 그 때 하지 않으면 이렇게 개 고생한다.

어찌됐건 오늘은 퀵 정렬이다.

나는 이게 퀵 정렬이 겁나 빨라서 퀵 정렬인가 했는데, 맞다. 겁나 빠른 퀵 정렬 한 번 기록해둔다.

퀵 정렬이란?

퀵 정렬은 이름을 통해서는 대충 어떤 정렬인지 짐작하기가 힘들다. 뭐 병합 정렬과 같은 경우는 뭔가 병합 해나가겠지 싶었는데 퀵 정렬은 아니다. 그래서 퀵 정렬이 무엇인가 라기 보다는 퀵 정렬의 작동 원리를 기록하는게 나의 인생에, 그대의 인생에 더 유익하지 않을까 싶다.

퀵 정렬은 병합 정렬과 매우 비슷하게, 쪼개는 것이 그 기본으로 깔려 있는 정렬이다. 또 쪼개기 시작한다는거다. 쪼갠다는 것의 의미는 병합 정렬에 잘? 설명되어 있는진 모르겠고 애타게 설명을 적어 놓았다.

https://typingdog.tistory.com/122?category=924874

퀵 정렬의 주된? 사상?은 이렇다. 

1. 배열을 쪼개는 것과 동시에 정렬하는 것이 아니다
2. 그렇다고 해서 앞/뒤 비교를 하며 정렬을 한다고 생각하면 안된다.
3. 어떤 기준에 맞는 '하나'의 요소의 정렬된 위치를 찾고, 고정한 뒤, 그 위치를 중심으로 양 옆 두개로 쪼개는 것이다. 이 때, 고정된 요소는 이미 올바른 정렬 위치를 찾았으니 정렬 대상에서 제외한다.

그러니까 결국에는 주어진 범위에 한해서 어떤 기준에 의거하여 단 하나의 요소의 올바른 정렬 위치를 찾아나가고 그 위치를 기준으로 양 옆으로 쪼개는 것을 반복해나간다고 생각하면 된다.

사과해야겠다. 이게 무슨 말이냐? 그림으로 기록해야겠다.

이런 배열이 있다.

이 배열을 아주 오도방정을 떨면서 왔다갔다 할 이상한 인덱스들을 소개하겠다.

자, 그림 내에 설명을 기록했지만, 추가 설명이 필요한 부분을 기록하겠다. 

일단, pivot은 비교의 기준이라고 했는데 꼭 이 기준을 맨 왼쪽에 둘 필요도 없다. 다만 이런 기준이 어디에 있긴 있어야한다는 소리인데, 오름차순 정렬의 경우 맨 왼쪽에 많이 쓴다고 생각한다고 생각한다....ㅋㅋ

left와 right는 무조건 배열 전체 중 인덱스 0과 인덱스 끝을 나타내는게 아니라 주어진 범위 내에서 가장 왼쪽과 오른쪽을 나타내는 것이기 때문에, 물결 표시로 강조를 했다.

기본적인 동작은 다음과 같다.

low와 high가 서로를 넘어선 경우이다. 이 경우에는 더 진행해도 (row의 입장에서)pivot보다 작은 값이, (high의 입장에서)pivot보다 큰 값이 나올리가 없기 때문이다. -> 우리는 지금 pivot을 기준으로 작은 값들을 왼쪽으로 몰아왔고, 큰 값들을 오른쪽으로 몰아왔다. 눈으로 잘봐라.

그러면 이제 몰려있는 곳의 경계가 있을 것이다. 3과 6 사이이다. 그 사이에 pivot 값을 넣고 뒤에 값들을 하나씩 땡기고 할 것 없이 high의 값과 pivot의 값을 바꾸면 정확하게 맞아떨어진다. 

pivot 기준으로 왼쪽은 pivot보다 작은 값. 오른쪽은 pivot보다 큰 값.

개쩐다.. 5가 고정 되었다. 이걸 재귀로 왼쪽편, 오른쪽 편 쫘르륵 실행해주면 알아서 각각의 pivot들이 제 자리를 찾아 정렬된 결과를 딱 보일 수 있을 것이다. 

이런 방법을 어떻게 생각했단 말인가 진짜..

코드 및 실행 결과

----

----

QuickSort 함수에서 ' if (left <= right) ' 이 조건! 이 조건은 위 퀵 정렬 과정에서 row와 high 가 서로 넘어서는 경우와는 완전 다른 조건이다. 해당 조건은 쪼개짐의 범위에 대한 조건으로 left와 right가 서로를 넘어서는 것은 이미 요소 하나 단위까지 쪼개고 난 이후라는 의미이다.

잘 정렬되었다. 

병합 정렬에서 재귀에 대해 한 번 설명을 써본 탓에 이번엔 정신이 온전하다.

퀵 정렬의 성능

퀵 정렬의 빅오는 pivot을 어떤 것을 선택하느냐에 따라서 다르다. 잘 선택한 경우

최선의 경우 : O(n log 2 n) - 2는 아래 첨자 2이다.
최악의 경우 : O(n^2) 

최선의 경우를 잘 뽑도록 pivot을 데이터 세트의 특성 상 잘 뽑아야하고, 데이터의 이동이 적기 때문에 매우 효율적이고 빠른 알고리즘이라고 생각하면 되겠다.

이번에는 병합 정렬이다. 이게 생각보다 간단하긴 한데 복잡하다(?) 일단 시작한다.

병합 정렬이란?

병합 정렬의 기본은 다음과 같다.

1. 배열을 원소 단위로 쭉~~ 나눴다가
2. 다시 단계적으로 정렬과 동시에 결합을 반복한다.

그림으로 나타내자면 다음과 같다.

그럼 문제는 무엇이냐? 어떻게 쪼갤 것인가? 이다. arr[0] , arr[1] 이게 쪼갠 것 아닌가? 아니다. 그냥 원소에 접근한거지 쪼갠게 아니다. 

그럼 쪼갠다 라는 의미를 아주 곰곰히 생각해봐야한다. 

쪼갠다는 것은 큰 덩어리부터 시작해서 작은 단위로 나눈다는 것이고, 내가 원소 레벨까지 쪼갰다 라는 의미는 내가 지금 쪼개고 있는 진행 흐름이 원소 단위까지 접근했다! 라는 것이다.

좀 어렵지만 잘 생각해라. arr[0] 에 접근하는 것은 우리 집 강아지와 할머니도 할 수 있는 행위이다.(집에 강아지와 할머니는 없다) 이것은 쪼갠 것이 아니고 접근한 거다. 

쪼갠다는 것은 그림의 설명과 같다.

제어할 수 있는 인덱스 범위를 한정지으면 되겠다 이것이다. 그런데 내가 가만히 보니 이 쪼개는 단계가 범위만 줄어드는 것 외에는 모두 같은 짓을 하고 있는 것이다. 그렇다면 원본 배열을 던지고, 그와 함께 범위 값만 다르게 던져주면 알아서 쪼개주는 함수가 없으려나?

있다. 바로 재귀 함수이다. 바로 코드를 본다

위 함수처럼 원본과 범위를 지정하여 함수에 던져주면 알아서 반으로 쪼갤 것이다. 

위 그림처럼 될 것이다.

그렇다면 쪼갰으니 정렬과 결합을 해야한다. 다시 MergeSort 코드를 보겠다.

MergeSort는 범위를 나누어 두 토막 내고(2개의 MergeSort) 그리고 정렬과 결합을(Merge) 수행한다 라는 사실을 기억해야하며, 신뢰해야한다. 그니까 밑에 잔뜩 실행된 MergeSort 함수는 신경쓰지말고, 현재 주어진 범위들에 대해서 정렬하고 결합한다는 것이다.

위 그림처럼 밑 바닥까지 MergeSort 하면서 내려가면 더 이상 쪼개지 못하므로 각 MergeSort에게 지정된 범위에 대해서 Merge 를 통해 정렬과 결합을 수행해주고 리턴한다 그러면 한 단계 위층에서의 MergeSort들은 내부적으로 정렬된 두 덩어리를 받을 것이고 또한 그들도 Merge 를 통해 정렬과 결합을 수행해주고 리턴해준다. 언제까지? 다 합쳐질 때까지!

물론!!!! 여기서 정렬은 조상님이 와서 대신 해주는게 아니다! Merge라는 함수 내에서 이를 구현해야한다. 이는 어렵지 않으므로 코드로 확인해보면 될 것이다.

이 코드가 핵심인데, 앞 범위 토막과 뒷 범위 토막의 요소들을 모두 둘둘씩 비교하여 작은 값을 새로운 공간에 차곡차곡 넣는 방식이다. 이게 가능한 이유는 각 토막들은 아래 계층에서 이미 정렬되어 올라왔기 때문이다! (쓰면서 명확히 깨달음 ㅋ)

내가 무슨 말을 하고 있는지 모르겠다면 직접해봐라 미래의 나야

코드 및 실행 결과

----

----

머리가 참 아득해진다..

머리가 아득해지는 김에 빅오를 보자

병합 정렬 성능

최악/ 평균 / 최선에 상관없이 비교와 데이터 이동 연산을 모두 세어보면 O(n log 2 n)이다. 2는 아래 첨자 2이다.

오늘은 힙 정렬이다.

힙 정렬이란?

말 그대로 Heap 자료구조를 이용한 정렬 방식이다. Min Heap에서 루트 노드부터 빼오면 오름차순 정렬이 가능한 점을 이용해한 것이다.

힙 정렬은 Heap 자료 구조 조금 개조하면 만들 수 있다.
아래 그림과 같은 Min-Heap을 이용하면 정렬 성능이 죽여준다 ㅋ 

우선 순위 큐에서도 우선 순위가 높은 것을 작은 값이라고 약속하고 작성한다면 같은 결과이다. 뭐 그 기반이 heap 자료구조이니 heap을 통해서 구현했고, 이미 구현해놓은 것에 우선 순위 부분만 조금 수정하였다. 나중에 기억 안날 때에는 아래 링크 먼저 보고, 다음 코드를 확인하면 될 듯 하다. 

수정한 부분을 보자면, 원래 기존 heap 코드는 우선 순위를 결정하는 부분을 삽입마다 지정하기로 했는데 그것을 함수 포인터를 이용하여 없애버리고 자동으로 우선 순위를 나뉘도록 했다.

https://typingdog.tistory.com/110?category=924874

다음은 코드이다.

코드 및 실행 결과

----

----

힙 정렬 성능

힙 데이터 저장 시간 복잡도 : O(log2 n) - 2는 아래 첨자의 2이다.
힙 데이터 삭제 시간 복잡도 : O(log2 n) - 2는 아래 첨자의 2이다.
힙 데이터 정렬의 경우, 저장과 삭제를 각각 n번씩 수행하므로 시간 복잡도 : O(n log 2 n) - 2는 아래 첨자의 2이다.

힙 구조에 데이터 삽입, 삭제 등이 이루어진다는 것을 고려한다고 하더라도, 앞서 봤던 O(n^2) 정렬들 보다도 성능이 좋은 것이다.

하 코딩해놓고 묵혀뒀다가 포스팅하느라 다시 보고 시간 버리는게 너무 아깝다 앞으로는 정말 열심히 바로바로 정리해서 올려야겠다.

그래도 다시 복습할 기회가 되었으니 의미있는 시간이라 생각하고 일반 연결 리스트에 대한 기록이다.

내가 (윤성우 교수님의 자료구조 책의 ADT를 보고) 코딩한 연결 리스트는 살짝 형태가 다르다. 그러므로 특징에 대해서 그림과 글의 적절한 특징 설명 이후 코드와 실행결과를 기록 하겠다.

일단,

단순 연결 리스트란?

구조체와 주소 값을 이용하여 현재 노드 내부에 다음 순서 노드의 주소 값이 저장되어 있는 형태로 이 이어진 연결을 통해 값을 순회할 수 있는 자료 구조이다.

노드 내부에 다음 순서 노드의 주소 값이 저장되어 있다는 것은 이러한 경우를 뜻한다.

구조

원래는 아래 그림과 같은 형식으로 리스트가 구성되어졌어야 했는데 

머리 회전이 덜 된 관계로 아래 처럼 다른 리스트를 만들어버렸다. 그건 뭐 그거대로 기록할 것임.

일단 위 구조로 생겨먹었고, 노드 구조체와 그 노드들을 담고 관리하는 자료구조 구조체가 있다

새 노드가 항상 헤드 다음 즉, 실질 데이터 노드 맨 앞에 항시 존재해야만 한다. 값을 추가할 때, 값과 링크 값만 변경하고 사용한다. 위와 같은 특성 때문에 리스트를 초기화할 때 다음 그림과 같이 꼭 -1 값으로 초기화 한다.

초기화 및 추가

값을 추가할 때에는 빈 노드의 값을 변경하여 사용하지만, 그래도 어찌됐던 빈 노드를 헤드 다음, 데이터 노드들 맨 앞에 두는 것이 원칙이기 때문에 데이터를 추가할 때 빈 노드 또한 추가해 놓아야 한다.

순회
다음은 순회이다.

삭제 
다음은 삭제이다. 내가 따로 만든 함수들이 있기 때문에 간단하게 설명한다.

코드 및 실행 결과

----