54. 정렬의 기초 (토너먼트와 최대값, 최소값 찾기)

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

어떤 값의 빈도를 세거나, 어떤 값이 최대 최소인지, 어떤 값이 유일한지, 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이다. (즉, 반대편)

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

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

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

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