Simple in Complex with Simple

어젠 이상한 하루였다.

결과에 대한 기대로 인해, 좀처럼 집중할 수 없던 하루다.

아침에 결전이란 일기를 쓰고, 열심히 공부하긴 했지만,

음 뭐랄까.

결전이 많아졌다?

좋드라.

기쁜 소식들이 연이어서 터지는게.

응.

좋았다.

너무 많이 다가와서 조금 힘에 겨울 수도 있다고 생각했는데.

하나하나의 기회에도 엄청 감사하다.

자만하지도 말고, 크게 겸손하지도 말고.

소중하게 다가온 기회들 최선을 다해서 부딪혀보자.

조금 체력적으로 힘에 겨울 수도 있으니까, 잘 대비하고.

이 시간에 글 쓰면서 졸린 것은 1달하고 일주일동안 처음인 것 같다.

시험기간이 끝나버려 많이 비어버린 도서관의 모습도 낯설다.

허리피자.

안졸리게.

그리고 오늘 아침에 학교오는데 여전히 하늘을 본다.

어제의 비 영향인지 하늘엔 조금 먹구름이 섞여있다.

차가워진 공기는 폐부에 스며들었다 나가면서 추움을 느끼게 한다.

넓은 하늘.

왠 고래가 헤엄치는 것 같았다.

사진 못 찍은게 아쉽다.

고래처럼 생긴 거대한 먹구름이 하늘이란 바다를 유영하는 모습 이뻤는데.

생각해보니, 이 세상에서 가장 추상적인 존재는 하늘이었군.

생각접고 최선 다해, 또 놓치고 우울해빠지지말고.

  으아아아아아아아아아아아아아아아아아.

할 수 있다. 할 수 있다. 할 수 있다.

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초 안에 끝이 났다.

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

11월 8일.

결전의 날.

남은 시간 11일.

지금보다 최소 두 레벨은 올려서 와.

라고 말해주는 듯한 준비기간.

모든 공부에 의지를 가지고 쏟자.

아버지, 어머니가 기뻐하는 모습.

다시 보고싶다.

형의 기대에 찬 목소리.

또 듣고싶다.

반드시, 끝낸다, 무조건.

이런 확정짓는 말은 하지말자.

내 모든걸 쏟고, 잔잔하게 기다려.

여기가 도착점인지, 아니면 또 지나가는 과정인지는 모르지만.

최고가 되고싶다.

내 분야에서.

그리고 명예도, 욕심도, 돈도 그 위에 있는 것은 사랑이란 거 잊지말자. 

컴퓨터 과학에서는 값의 비교를 해야할 때가 많다.

어떤 값의 빈도를 세거나, 어떤 값이 최대 최소인지, 어떤 값이 유일한지, n번째로 큰 원소는 무엇인지.

이런 비교를 쉽게 해주는 것이 바로 '정렬' 기법이다.

정렬이란 데이터를 일정한 순서대로 늘어놓는 상태를 지칭한다.

늘어놓는 상태는 오름차순일 수도 있고, 내림차순일 수도 있다.

정렬에 관련된 알고리즘은 무척이나 많고, 상황에 따라 유용한 정렬 알고리즘도 많이 알려져있다.

또한 대부분 널리 쓰이는 프로그래밍 환경에서는 좋은 정렬 함수(qsort)와 탐색 함수(find)를 제공한다.

정렬 알고리즘을 직접 만들어 사용하면, 메모리 오류가 발생할 수 있다. 

대부분 재귀적 성질에서 나오는 '스택 오버플로우' 현상이다.

그렇기에 직접 만들어 사용하는 것보다 언제나 이미 구현된 라이브러리를 이용하는 것이 좋다.

이에 관련된 '존 벤틀리'의 명언이 있다.

"만약 시스템에서 제공하는 정렬이 당신의 필요를 충족시킨다면, 직접 작성하는 것은 생각도 하지 말아라."

이처럼 정렬 알고리즘을 직접 만들어 사용하는 것은 큰 위험에 속한다.

하지만 정말 소수의 상황에서, 특히 대규모 데이터를 다뤄야 하는 상황에서 필요에 맞는 정렬 알고리즘을 직접 구현하거나

정렬 알고리즘을 변형 및 응용하여 프로그램을 작성해야 할 지도 모른다고 한다.

여러가지 상황에서, 그 상황에 적합한 정렬 알고리즘을 선택하고 어떤 입력 조건에서도 느려지거나 오류가 발생하면 안된다.

그렇기에 정렬에 대한 심도깊은 이해와 제공되는 정렬을 사용하는 것과 새롭게 작성하는 정렬 알고리즘 사이의 장단점을

명확히 파악하고, 각각의 정렬에 대한 원리를 이해하고 코드로 작성할 수 있어야 한다.

다음은 토너먼트 상황이 있다.

총 N개의 팀이 나와서 경합을 벌인다.

이 때, 토너먼트를 주최한 쪽은 많은 관람료를 벌어들이기 위해서 최대한 많은 경기를 잡으려고 한다.

하지만 어떤 대진표를 작성하여도, 정말 이상하게 꼬은 대진표를 작성하여도, 여전히 N-1개의 경기를 치뤄야한다.

어떻게하면 대진표를 바꿔서 더 많은 경기를 하게 만들 수 있을까?

- 정답은 없다. 토너먼트 우승자를 찾기위해선 무조건 N-1개의 경기를 치뤄야 한다.

첫 1경기에 N개의 팀이 각각 자신의 상대와 겨루어 N/2 팀이 탈락한다. (N/2번 경기)

그리고 다음 2경기에 마찬가지로 그 절반인 N/4 팀이 탈락한다. (N/4번 경기)

...

이런식으로 마지막엔 두 팀만 남아 최종 승자를 겨룬다. (1경기)

만약 위의 N이 8라 했을 때, 4번+2번+1번 총 7번이 발생하고,

만약 위의 N이 12라 했을 때, 6번+3번+1번+1번 총 11번이 발생한다. (1번은 홀수팀이 남았기에 한 팀은 부전승이다.)

위의 표현은 꽤 어려운 표현이고 쉽게 표현하면, 한 경기 후에는 반드시 한 팀이 떨어진다. (토너먼트 방식이기에)

그래서 최종적으로 N-1팀이 떨어지면 남는 팀은 1곳이고, 이 팀이 우승자다.

N-1팀이 떨어지기 위해서는 N-1번 경기를 치르면 된다.

두 표현 방식 중 어느것도 다 맞다.

아주 간단한 원리로 말을 빙빙 꼬았는데 결론은 항상 이렇다. 

N번째를 조사할 때, 어떤 데이터를 결정하기 위해서는 N-1번 비교를 해야한다.

이는, 최대값 또는 최소값을 찾는데도 마찬가지이다.

처음 이 문제를 봤을 땐, 뭔가 거창한 원리가 숨겨져 있는 줄 알았다.

그래서 긴장하고 살펴보기 시작했는데, 결국은 기초 원리이다.

기초는 쉽지 않다. 이것을 명심하자.

마지막으로 추가적인 문제로, 

토너먼트에서 한 팀은 모든 팀을 다 이길 수 있는 팀 A이고, 한 팀은 A팀을 제외한 모든 팀을 이길 수 있는 B팀이 있다.

B팀이 준우승하기 위한 확률은 얼마인가?

생각해보자.

정답은 1/2 확률이다.

왜냐하면 B팀이 최종 경기에 나서면 된다. 그러기 위해서는 처음 시작 위치에서 최종 경기 이전에 A팀과 맞붙을 상황이

안나오는 위치에서 시작하면 된다. 그 위치의 개수는 현재 팀에서 N/2이다. (즉, 반대편)

이처럼 토너먼트란 단어 듣고 쫄지 말고 전력으로 달려들자.

기본인데 고작 단어듣고 무서워서 벌벌 떠는 꼴이라니. 꼴사납다.

계속 생각하자. 설계와 코딩은 외워서 하는 것이 아니라 생각해서 하는 것이니까.

결국엔 생각하는 능력이 뛰어난 자가 코딩을 잘한다.