트리의 모든 노드를 한번씩 방문하여 모든 정보에 대한 선형 순서를 만들어 내는 방법을 알아보자


트리, 이진트리에 대해서는 이전글을 참고자도록 하자.

2016/10/18 - [Yame Programmer/자료구조&알고리즘] - 야매 개발자 자료구조 가이드[트리(tree)]


이진트리나 이진트리의 순회방법을 난 이제 알았는데 컴공 학생들은 2학년때 배운단다... 부럽...



순회방법에는 3가지가 있다.


1. 전위 순회(Preorder Traversal)

2. 중위 순회(Inorder Traversal)

3. 후위 순회(Postorder Traversal)



1. 전위 순회(Preorder Traversal)

<전위 순회의 탐색 순서 : A B D E C F G>


전위 순회의 특징은 루트 노드를 가장 먼저 탐색 한다.

루트 노드 부터 시작해 왼쪽 하위트리를 탐색하고 왼쪽 트리의 탐색이 끝나면 오른쪽 하위 트리를 탐색하는 방식 입니다.



2. 중위 순회(Inorder Traversal)

<중위 순회 탐색 순서 : D B E A F C G>


중위 순회의 특징은 루트노드가 탐색 순서의 중앙에 위치 합니다.

왼쪽 하위트리 부터 시작해 루트를 거쳐 오른쪽 하위 트리를 탐색 합니다. 



3. 후위 순회(Postorder Traversal)

<후위 순회 탐색 순서 : D E B F G C A>


후위순위의 특징은 루트가 가장 마지막에 탐색 됩니다.

왼쪽 하위 트리에서 시작해 오른쪽 하위트리를 탐색하고 루트 노드를 탐색합니다.



구현된 코드를 참조하실분은


http://songeunjung92.tistory.com/29

http://marobiana.tistory.com/83


이분들의 포스팅을 참고하지면 좋을 것 같습니다.



저작자표시 비영리

'Yame Programmer > 자료구조&알고리즘' 카테고리의 다른 글

야매 개발자 자료구조 가이드[트리(tree)]  (0) 2016.10.18
야매 개발자 알고리즘 가이드[이진 탐색(Binary Search)]  (0) 2016.10.18
야매 개발자 알고리즘 가이드[순차탐색(Sequential Search)]  (0) 2016.10.18
야매 개발자 알고리즘 퀵 정렬[Quick Sort]  (6) 2016.10.11
트리(Tree)라는 자료 구조에 대해서 알아보자.

트리는 말그대로 나무와 유사한 자료 구조이다. 


뿌리에서 시작해 가지가 뻗어나가고 뻗어나간 가지에서


다시 잎사귀가 생긴것과 유사한 모양을 가지고 있는데 그 나무를 뒤집어 놓은것과 같다.


아래 그림을 보도록 하자


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



부모자식관계 : 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


저작자표시 비영리

'Yame Programmer > 자료구조&알고리즘' 카테고리의 다른 글

야매 개발자 자료구조 가이드[이진트리(binary)의 순회(traversal)]  (0) 2016.10.19
야매 개발자 알고리즘 가이드[이진 탐색(Binary Search)]  (0) 2016.10.18
야매 개발자 알고리즘 가이드[순차탐색(Sequential Search)]  (0) 2016.10.18
야매 개발자 알고리즘 퀵 정렬[Quick Sort]  (6) 2016.10.11

순차탐색은 쉬웠으니 빠르게 다음 공부할 이진탐색(Binary Search)에 대해서 알아보자.


이진탐색은 한번 비교를 할때마다 비교를 하는 범위가 반으로 줄어든다


이게 순차탐색과 비교해서 알마나 큰 차이가 있냐면


만약 70억개의 데이터를 검색했을때 순차탐색은 최대 70억 번 평균 35억 번을 비교 하는데 


이진탐색은 최대 33번의 비교로 탐색을 완료 할 수가 있다.


대신 조건이 하나 있는데 이진탐색에 사용하는 배열을 정렬되어진 배열이어야 한다는 것이다.



그림으로 알아보도록 하자




먼저 배열의 중앙을 선택하고 찾고자 하는 값보다 큰지 작은지 비교를 합니다.



5는 7보다 작기 때문에 5에서 오른쪽에 있는 요소들로 이동하여 


다시 그중 중앙에 위치한 값을 선택해 비교 합니다.



8은 7보다 크기 때문에 왼쪽으로 이동을 합니다


이런식으로 범위를 좁혀나가다 보면 원하는 값을 찾게 되겠죠



한번 검색을 수행할떄마다 범위가 반으로 줄어든다는 말이 이해가 되지 않는다면 


노트에 펼쳐놓고 위의 그림을 따라서 그리고 검색하지 않는 범위부터 반으로 접어 보면 이해가 갈 것이다.



이진탐색의 시간 복잡도 : O(log n) 



이진탐색의 구현 소스를 보면 생각보다 간단하다. 위에 그림에 있는 if문을 반복할 뿐이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int BinarySearch(int dataArr[], int size, int findData)
{
    int low = 0, high = size - 1, mid;
        // low = 검색 할 범위의 가장 왼쪽
        // high = 검색할 범위의 가장 오른쪽 
 
    // high가 low보다 작아진다면 찾으려는 데이터가 데이터 집합에 없다.
    while (low <= high)
    {
        // 중앙값은 low와 high를 더한 값을 2로 나누면 된다.
        mid = (low + high) / 2;
        // 만약 찾으려는 값이 중앙값보다 작다면 high를 mid - 1로 둔다.
        // 찾는값이 중앙값보다 작기 때문이다.
        // 이때 mid-1 = 다음검색할 범위의 가장 오른쪽이 된다.
        if (dataArr[mid] > findData) high = mid - 1;
        // 만약 찾으려는 값이 중앙값보다 크다면 low를 mid + 1로 둔다.
        // 찾는값이 중앙값보다 크기 때문이다
        // 이때 mid+1 = 다음 검색할 범위의 가장 왼쪽이 된다.
        else if (dataArr[mid] < findData) low = mid + 1;
        // 중앙값과 찾으려는 값이 일치하면 mid를 반환한다.
        else return mid;
    }
    // 데이터를 찾지 못하면 -1를 반환한다.
    return -1;
}
 
int main()
{
    int dataArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 21, 24, 26, 27, 28};
    int length = sizeof dataArr / sizeof dataArr[0];
    int input, ret;
 
        scanf("%d", &input);
        ret = BinarySearch(dataArr, length, input); // 이진탐색 실행
        if (ret != -1) printf("찾으려는 데이터는 %d번째에 있습니다.\n", ret + 1);
        else printf("데이터를 찾을 수 없습니다.\n");
    
    return 0;
}
cs


(참조 http://blog.eairship.kr/246)


주석이 많아서 좀 복잡해 보이는데 주석도 빼버리면 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int BinarySearch(int dataArr[], int size, int findData)
{
    int low = 0, high = size - 1, mid;
 
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (dataArr[mid] > findData) high = mid - 1;
        else if (dataArr[mid] < findData) low = mid + 1;
        else return mid;
    }
    return -1;
}
 
int main()
{
    int dataArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 21, 24, 26, 27, 28};
    int length = sizeof dataArr / sizeof dataArr[0];
    int input, ret;
 
    scanf("%d", &input);
    ret = BinarySearch(dataArr, length, input); // 이진탐색 실행
 
    if (ret != -1)
        printf("찾으려는 데이터는 %d번째에 있습니다.\n", ret + 1);
    else 
        printf("데이터를 찾을 수 없습니다.\n");
    
    return 0;
}
cs


이런 소스가 된다.


생각보다 간단한 코드다.

저작자표시 비영리

'Yame Programmer > 자료구조&알고리즘' 카테고리의 다른 글

야매 개발자 자료구조 가이드[이진트리(binary)의 순회(traversal)]  (0) 2016.10.19
야매 개발자 자료구조 가이드[트리(tree)]  (0) 2016.10.18
야매 개발자 알고리즘 가이드[순차탐색(Sequential Search)]  (0) 2016.10.18
야매 개발자 알고리즘 퀵 정렬[Quick Sort]  (6) 2016.10.11

순차탐색이 뭐지? 하고 검색해 들어 온 사람들 대부분은 해당 내용을 보면 매우 실망할 것이다.


왜냐하면 이미 반복문을 배우면서 적어도 한번 이상은 써봤을 탐색 방법이기 때문이다.


2년동안 이 방식으로 검색을 하면서 이 알고리즘의 이름이 순차탐색 이라는 것을 난 오늘 알았다.



매우 단순하다



시간 복잡도:  최악O(n) , 평균 (n+1)/2


시간복잡도가 최악인 경우는 원하는 값이 가장 마지막에 있을 경우이다.



데이터가 배열에 있으면 배열의 처음부터 끝까지 차례대로 비교하면서 원하는 


데이터를 찾는 알고리즘이다.


이 알고리즘은 단방향으로 탐색을 하기 때문에 선형탐색(Linear Search)라고 부르기도 한다.



코드는 매우 단순하다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
// for문을 돌면서 데이터를 찾는다. 찾느 데이터가 없는 경우 -1 반환
// 찾는 데이터가 있으면 해당 번째 반환
int search(int dataArr[], int length, int findData)
{
    for(int i = 0; i < length; i++)
        if (dataArr[i] == findData) return i;
    return -1;
}
 
 
 
int main()
{
    int arr[] = {23, 25, 14, 5, 66, 72, 13, 224, 51};
    int length = sizeof arr / sizeof arr[0];
    int findData = 0;
    int findIndex = 0;
 
    printf("찾으시는 데이터를 입력해주세요: ");
    scanf("%d", &findData);
 
    findIndex = search(arr, length, findData); // 
 
    if(findIndex == -1) printf("데이터를 찾지 못했습니다.\n");
    else printf("데이터는 %d번째에 있습니다.\n", findIndex);
    
 
    return 0;
}
cs



(참조 http://blog.eairship.kr/245 )




순차탐색은 코드구현이 매우 쉬워서 짧은 기리의 데이터를 검색할때 사용하는 것이 좋은 것 같다.

저작자표시 비영리

'Yame Programmer > 자료구조&알고리즘' 카테고리의 다른 글

야매 개발자 자료구조 가이드[이진트리(binary)의 순회(traversal)]  (0) 2016.10.19
야매 개발자 자료구조 가이드[트리(tree)]  (0) 2016.10.18
야매 개발자 알고리즘 가이드[이진 탐색(Binary Search)]  (0) 2016.10.18
야매 개발자 알고리즘 퀵 정렬[Quick Sort]  (6) 2016.10.11

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


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


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


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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 값을 비교하고 로우와 하이를 이동시키면서 값의 교환이 이루어지는 함수
public static int partition(int arr[], int left, int right) {
 
    int pivot = arr[(left + right) / 2];
 
    while (left < right) {
        while ((arr[left] < pivot) && (left < right))
            left++;
        while ((arr[right] > pivot) && (left < right))
            right--;
 
        if (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }
 
    return left;
}
 
 
public static void quickSort(int arr[], int left, int right) {
 
    if (left < right) {
        // 값을 비교하고 로우와 하이를 이동시키면서 값의 교환이 이루어지는 함수
        int pivotNewIndex = partition(arr, left, right);
        // quick sort의 설명중
        // 자주 나오는 '재귀', '분할' 이라고 설명되어지는 부분이다.
        quickSort(arr, left, pivotNewIndex - 1);
        quickSort(arr, pivotNewIndex + 1, right);
    }
 
}
 
// 
public static void main(String[] args) {
    int[] arrs = { 69, 10, 30, 2, 16, 8, 31, 22 };
    quickSort(arrs, 0, arrs.length - 1);
    System.out.println("결과");
 
    for (int i : arrs) {
        System.out.print(i + " ");
    }
}
cs


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



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

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

도움이 될 것이다.



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


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

저작자표시 비영리

'Yame Programmer > 자료구조&알고리즘' 카테고리의 다른 글

야매 개발자 자료구조 가이드[이진트리(binary)의 순회(traversal)]  (0) 2016.10.19
야매 개발자 자료구조 가이드[트리(tree)]  (0) 2016.10.18
야매 개발자 알고리즘 가이드[이진 탐색(Binary Search)]  (0) 2016.10.18
야매 개발자 알고리즘 가이드[순차탐색(Sequential Search)]  (0) 2016.10.18

+ Recent posts

티스토리툴바