기타치는 개발자의 야매 가이드

<트리는 위와 같은 구조를 가지고 있다.>

부모자식관계 : B의 부모는 A , B의 자식은 D,E 

루트 : 트리구조에서 가장 위에 있는 노드, 부모가 없다.

노드 : 트리를 이루는 한 요소 (ex 위 그림의 A, B, C , D ....)

차수 : 어떤 노드가 가지고 있는 자식의 노드 개수를 말한다. 예를 들어 B노드의 차수는 2이다.

        (트리의 차수를 말할땐 가장 높은 차수를 말한다. 예를들어

         D노드에 자식이 하나 더 생긴다면 위 트리의 차수는 3이다)

레벨 : 트리를 이루는 각 층의 번호이다. 깊이 내려갈 수록 레벨이 높아진다. 

높이,깊이 : 루트 노드부터 가장 끝에 있는 노드 까지의 깊이(경로의 길이) 

               위 트리의 깊이는 3이다.

Left chaild-right Sibling 표현법

트리의 표현법이다. 아래의 그림처럼 한개의 노드에 자식과 형제의 포인터를 지니는 구조이다.

Child : 자식노드를 가르킨다

Sibling : 형제노드를 가르킨다

가장 위에 있는 노드부터 시작해 왼쪽에 있는 자식노드를 구하고 그 노드의 자식노드와 형제 노드를 구한다

이렇게 반복을 하면 모든 자식 노드를 찾을 수 있게 된다.

이진 트리 (Binary Tree)

최대 2개의 자식 노드를 가질 수 있는 트리이다.

한 노드당 자식을 1개만 가질 수도 있고 아무것도 없을수도 있고 2개를 가질수도 있다.

이진트리의 종류에는

완전 이진 트리(Complete Binary Tree)와 사향 이진 트리(Skewed Binary Tree), 포화 이진 트리(Full Binary Tree)가 있다.

<완전 이진트리(Complete Binary Tree)>

완전 이진트리는 어떤 노드 두개의 레벨차가 1이하 이며 왼쪽부터 오른쪽으로 채워지는 트리 이다.

만약 왼쪽에서 오른쪽으로 가다가 중간에 노드가 비어있다면 그건 완전 이진트리가 아니다.

예를들어 위의 그림에서 E노드 아래에 자식노드가 생성되면 완전 이진트리가 아니게 된다.

<사향 이진트리(Skewed Binary Tree)>

사향 이진트리는 루트노드를 제외한 모든 노드가 부모 노드의 왼쪽 자식 노드이거나 반대로 오른쪽 자식 노드인 것을 말한다. 즉 노드의 방향이 한쪽 방향으로만 치우쳐진 트리이며 다른말로 경사,편향 이진트리 라고 불리기도 한다.

<포화 이진트리(Full Binary Tree)>

포화 이진트리는 완전이진트리와는 다르게 최대한 노드가 가득차 있는 트리를 말한다. 가장 마지막 노드를 제외한 모든 노드가 자식노드를 2개씩 가지고 있다. 

(모든 포화 이진트리는 완전 이진트리 라고 부를수 있지만 그 반대는 성립하지 않는다.). 

이러한 뭔가 당연한것 같은(따로 공부하지 않아도 될것 같은) 트리구조를 왜 알아야 하는지 얼마 전까진 사실 잘 몰랐다. 

그러나 후에 포스팅할 트리의 순회구조와 그 다음 위상정렬(DFS 깊이 우선 탐색), 너비 우선탐색(BFS)를 거쳐

다익스트라 알고리즘과 같은 조금더 난이도 있는 알고리즘을 이해하기 위해선 이 트리구조에 대해서

기본적인 이해가 필요하기 떄문이라는걸 근 일주일간의 삽질 끝에 체감했다.

역시 기초가 중요하다.

참조: http://blog.eairship.kr/215

얼마전 쿠팡에서 서류 합격 메일이 날아왔다. 구글링을 해보니 쿠팡같은 경우 서류는 거의다 통과시켜 놓고 

problem solving test를 통해서 엄청나게 걸러버리는 듯 하다.

개발자로 취직해서 일한지 2년이 가까워 지면서 웹쪽 HTML CSS JS는 많이 해봤지만

순수 자바 쪽은 거의 건들이지 않았다는 것에서 불안감이 엄청나게 느껴졌다.

학교에서 전공수업 잘 듣고 자료구조나 알고리즘 공부 열심히 했으면 붙을 수 있다고 하는데

난 전공자가 아니다;; 학교에서 기초적인걸 배우긴 했지만 자바 클래스 만들고 'Hello word' 띄우는 수준?

안드로이드로 인텐트 날려서 화면 전환하는 정도 까지만 배웠고 이론적인건 소프트웨어공학 원론쯤?

그 외엔 죄다 마케팅이나 경영, 혹은 발표과제로 점수먹는 수업이라든지 실음과 전공수업이나 들었지 ㅋ

말하자면 전공이라기 보단 반공(?)이라고 말하는게 어울릴 듯 하다.

아무튼 자료구조는 스택과 큐밖에 모르고 정렬 알고리즘은 버블정렬 밖에 모르는 상태에서

어렵다고 소문난 쿠팡 테스트를 통과하려면 짧은 시간동안 공부를 많이 해야 겠다 싶었다.

면접 후기라던지 자료구조 기초라던지 알고리즘을 어떻게 공부해야 하는지 찾아 보면서

퀵정렬이라는 것이 있다는걸 태어나서 어제 처음 알게 되었다.

버블정렬만 있으면 만사 오케이인줄 알았고 심지어 프로젝트중에선 DB에서 불러올때 ORDER BY만 떄려버리면 해결이니

정렬 알고리즘을 사용할 필요성도 못느끼고 있었는데....  좀 충격이었다.

심지어 아래 동영상을 보고 가장 먼저 들었던 생각은

"버블정렬 개쓰레기였네??"

일단 정렬의 종류는 여러가지 있는데 아래 영상을 보도록 하자. 가운데 표시된 퀵정렬이 대체로 가장 빠른 결과를 보여준다. <출처: Viktor Bohush, 유튜브>

그리고 퀵정렬에 대해서 좀더 큰화면으로 보자면 <출처: Timo Bingmann / 유튜브>

이렇게 보여질 수 있다.

해당 내용을 직접 포스팅 하려 해보았으나 알고리즘이나 기초지식이 1도 없는 상태에서 이해 할 수 있는 포스팅 만드는데

시간이 너무 오래 걸린다. 퀵정렬이 무엇인지 이곳 저곳 둘러보던중

아주아주아주 설명을 잘 해놓은 게시글을 발견했다.

허접하게 내가 만드는 것 보다는 정말 잘 만든 다른사람의 글을 보는 것이 더 나을 것이라고 판단 했다.

http://navercast.naver.com/contents.nhn?rid=2871&contents_id=90163

위 주소로 들어가보면 퀵정렬에 대해 아주 잘 설명해 놓은 글이 있다.

한번 쭉 읽어 보고 이해가 좀 되겠다 싶다면 슈도코드 부분은 스킵하고 다음 소스를 보도록 하자

<참조: http://creatordev.tistory.com/70>

처음 올린 링크의 글을 정독했다면 위 소스를 보면서 직접 소스를 디코딩 해보도록 하자.

소스의 처음부터 정렬이 종료될때까지 직접 소스를 따라가면서 정렬을 해보는 것이 이해하는데 가장 큰

도움이 될 것이다.

요즘 웹쪽엔 내가 아는 지식이 후달려서 더 포스팅하기 힘들었는데 노드js나 리엑트js 해보기 전까진

자료구조와 정렬에 대해서 포스팅을 해봐야 겠다. 나에게도 큰 도움이 되는듯 하다.