Simple in Complex with Simple

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

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

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

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

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

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

이해한 부분에 대한 것만 정리.

유사점

1. C++과 Java 모두 클래스의 객체를 인스턴스화 하지않은 static 메서드 또는 함수를 지원한다.

2. C++과 Java 모두 Overloading(다중 정의) 생성자를 제공한다.

차이점

1. Java는 전처리기, typedef, enum, defined를 지원하지 않는다. (enum은 Java 1.5부터 지원함)

2. Java는 클래스(class)를 지원하지만 구조체(struct)와 공용체(union)을 지원하지 않는다.

3. 모든 Java 클래스의 최상위 클래스는 Object 클래스이다. (즉, 모든 Java 클래스는 Object 클래스를 상속한다.)

4. Java에서 선언하는 모든 함수 또는 메서드는 모두 클래스 선언 내에 포함된다.

5. 'Interface' 키워드는 자바에서 제공한다. C++에서는 제공하지 않는다.

(그러나 최근에 interface class 라는 기능이 C++에도 구현되어 순수 가상 함수만으로 정의하던 방식이 바뀌는 듯 하다.)

6. Java는 다중상속을 지원하지 않는다. 

(다중상속에 관한 수많은 이슈들이 있다. 이에 대해 검색해볼 것.)

7. C++은 배열의 index 범위를 초과하면 이를 판단할 수 없지만 Java는 배열의 사이즈 값을 가진 length 멤버 변수를 지닌

객체를 배열로 제공하기에, 배열의 범위를 넘어서면 이를 index bound 예외를 발생시킨다.

8. Java는 포인터를 지원하지 않는다. 포인터를 지원하지 않으므로 -> 연산자 역시 사용하지 않는다.

9. C++에서 char 타입은 1 byte, Java에서 char 타입은 2 byte이다.

10. Java에는 소멸자가 없다. 대신 훨씬 더 강력한 Garbage Collector(가비지 콜렉터)가 존재한다.

11. Java에서는 virtual 키워드가 없다. Java는 static 함수가 아닌 모든 함수는 언제나 동적 바인딩 사용.

12. Java에는 final이란 키워드가 존재한다. final 선언은 다중 정의가 될 수 없으며 정적으로 바인딩 됨을 의미한다.

*정적 바인딩과 동적 바인딩의 의미는 함수 또는 메서드를 컴파일 시에 아니면 실행 시에 그 의미를 부여한다는 것.

정적이나 동적 모두 결국의 의미는 컴파일 시인지, 실행 시인지 나타낸다. 이를 잘 이해하여야 한다.

C++에서 virtual 키워드가 붙는다면 이는 정적 바인딩이 아닌 동적 바인딩을 하겠다는 의미이다.

*최소한 색으로 칠한 단어나 굵게 칠하고 밑줄 그은 부분만큼은 잊지말자.

배열과 링크드리스트에 대한 차이를 기술 면접 준비하면서 정리한 것을 쓴다.

-속도-

(1번 포인트) 데이터에 대한 접근 속도 - 배열 승

배열은 index만 있다면 O(1)에 접근.

연결리스트는 최소 한 번은 리스트를 순회하여야 하므로 O(n)에 접근.

(2번 포인트) 데이터 삽입 속도 - 경우에 따라 다름 (전체적으로 연결리스트 승리)

만약 배열에 공간이 많이 남아있고 맨 끝에 삽입한다면, 삽입 속도 역시 O(1)에 가능.

하지만 이런 경우만 발생하는 경우는 꽤 드물기 때문에 연결리스트의 필요성이 대두됨.

연결리스트는 어느 곳에 삽입하던지 O(n)의 시간에 접근함. (만약, 중간 삽입이 없다면 O(1)에 접근)

배열의 경우 데이터를 중간이나 맨 앞에 삽입할 경우 그 이후의 데이터를 한 칸씩 미뤄야하는 추가과정과 시간이 소요.

하지만 연결리스트는 필요없음.

또한 배열의 경우 데이터 삽입시 모든 공간이 다 차버렸다면, realloc()또는 새로이 할당하여 메모리 공간 확장이 필요.

하지만 연결리스트는 필요없음.

데이터 삽입의 경우 범용적인 측면에서 연결리스트의 승.

(3번 포인트) 데이터 삭제 속도 - 경우에 따라 다름 (전체적으로 연결리스트 승리)

위의 2번 포인터와 똑같음.

단지, 데이터 삭제의 경우 그 위치의 데이터를 삭제 후, 전체적으로 한 칸씩 앞당기면 되지만

연결리스트의 경우 예외조건들의 처리가 꼼꼼히 필요함. 그렇기에 코드의 복잡성 증가. - (하지만 이미 만들어진것 사용해서)

결국은 이 역시 범용적인 측면에서 연결리스트의 승.

(결론)

삽입과 삭제가 번번히 이루어진다면, 연결리스트 사용이 좋음.

이미 만들어진 구조에서 데이터의 접근만 필요하면 배열이 좋음.

결국 배열도 해쉬의 일종이고 가장 기본적인 해쉬 기법이 바로 배열.

그리고 또 하나 알아두어야 할 것!

위의 내용만 보면 전반적으로 리스트의 사용이 훨씬 좋아보인다. 하지만 일반적인 알고리즘 문제를 풀이할 땐

리스트보다 배열이 훨씬 빠르고 좋다. 왜냐하면 대부분의 알고리즘 연습문제들은 그 메모리 공간의 범위를

주어지기 때문에 배열 선언을 그 MAX치로 잡을 수 있다면, 훨씬 더 편리하고 리스트와는 전혀 다른 속도를 보인다.

왜냐하면 리스트의 입력은 추가 과정마다 메모리의 할당이 일어나고 삭제에서는 메모리의 해제가 일어난다.

메모리의 할당과 해제는 O() 시간으로 따지지 않지만, 이런 시스템 콜(System Call)을 사용하는 문구는 시간소요가 꽤 걸린다.

그러니 결국은 배열이든 리스트이든 단순히 이론을 떠나서 자기가 무엇을 하려는지, 그 목적에 따라 선택하는 것이 좋다.

const 키워드는 결국 변수의 값이 변경되지 않음을 명시함. 즉, 상수화시킴.

하지만 const 키워드는 정말 다양한 위치에서 사용되기에 혼동이 옴.

크게 변수 선언에 사용되는 위치와 함수 선언에 사용되는 위치 2개로 나뉨.

변수 선언 시

<const> 자료형 <const> 포인터 <const> 변수명;

   (1번)               (2번)               (3번)

함수 선언 시

<const> 자료형 <const> 포인터 함수명(parameter1, parameter2 ...) <const> { }

   (4번)               (5번)                                                             (6번)

변화를 뜻하는 변수에 const 키워드를 붙이는 이유는 그 값이 더이상 바뀌지 않기에 바뀌면 안된다는 것을 명시하는 것.

(어떻게보면 방어적 프로그래밍, 또는 설계의 한 부분이다.)

출처: http://tapito.tistory.com/31