순회란, 여기 저기로 돌아다닌다는 뜻을 가지고 있습니다. 우리가 노드를 지나가는 것 역시 순회라고 합니다. 그리고 그 노드를 지나가는 순서에 따라  전위 순회, 중위 순회, 후위 순회로 나뉘는 것입니다.  다음과 같이 단순한 트리가 하나 있다고 가정해봅시다.   모든 노드를 지나가는 횟수는 아래와 같이 총 6회이지만,  (왼->루트->오 / 왼->오->루트 / 루트->왼->오/ 루트->오->왼 / 오->루트->왼 / 오->왼->루트) 왼쪽과 오른쪽이 고정되어있다고 치면,    이렇게 3가지 경우로 나뉠 수 있고, 이게 각각 전위, 중위, 후위 순회입니다. 루트노드 -> 왼쪽 자식 -> 오른쪽 자식 순으로 노드를 읽는 것이 전위 순회, 왼쪽 자식 -> 루트노드 -> 오른쪽 자식 순으로 노드를 읽는 것이 중..

이전 글에서는 선택 정렬에 대해 간단히 설명하였다. https://studywithsheep.tistory.com/6 [알고리즘] 선택 정렬(selection sort) 쉽게 이해하기! 선택 정렬이란 ? 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 나는 이게 인간의 사고와 가장 유사한 알고리즘이라는 생각이 든다. 주어진 숫자 다섯가지 studywithsheep.tistory.com 이번에는, 선택 정렬을 C언어를 이용해 직접 구현해보겠다. 먼저 컴퓨터는 어떤 과정을 거쳐 선택 정렬을 수행할지 생각해보자. 지난 글에 적힌 것과 같이, 먼저 이렇게 수를 비교하여 배열의 맨 앞 쪽에 가장 작은 (or 가장 큰) 수가 오도록 한다. 다음에는 당연히 그 다음으로 작은 (or ..

병합 정렬 (merge sort) 병합 정렬, 합병 정렬 둘 다 같은 말이다.. 병합 정렬은 일단 배열이 더 이상 쪼개지지 않을 때까지 절반으로 계속 쪼갠다. 그리고 조각을 2개씩 묶어 각각을 크기순으로 배열하고 또 그 조각을 2개씩 묶어 크기순으로 배열하는 식이다. 예를 들어, [4, 1, 8, 6, 7, 2, 3, 5] 가 있으면 이런 식으로 원소가 하나 하나 뜯어질 때까지 나눈다. 그리고 더 이상 뜯어지지 않을 정도로 나뉘어졌다면, 이제 반대로 하나 하나 붙이는데, 이 때 정렬을 같이 해준다. 이게 끝이다..! 알고리즘을 이해하는 것 자체는 그리 어렵지 않을 것이다. 분할 정복 알고리즘 하지만 지금까지 설명했던 알고리즘과는 달리 굳이 이렇게 해야하나? 싶을 수도 있을 것 같아 설명을 덧붙이자면, 배..

퀵정렬 (quick sort) 퀵정렬을 설명하는 글을 보면, 피벗을 기준으로 피벗보다 작은 원소들은 모두 피벗의 왼쪽으로, 피벗보다 큰 원소들은 모두 피벗의 오른쪽으로 옮기는 것이라고 적혀있는데, 이 때 피벗(pivot)은 단순히 '먼저 선택된 성분' 정도로만 생각해도 될 것 같다. 다시말해, 먼저 특정 원소가 피벗으로 선정되고 그 원소에 따라 배열이 진행되는 것이 퀵정렬이다. '팀 나누기' 라고 생각하면 쉬울 것 같다. 배열 [5, 7, 3, 6, 2, 1] 이 있을 경우를 예로 들어보겠다. 맨 왼쪽의 원소 5를 피벗으로 정한 뒤, 피벗보다 작거나 같은 원소를 A팀, 피벗보다 큰 원소를 B팀으로 나누어보겠다. 이 때, 원소들은 차례로 줄을 서 있고, 앞에 서있는 원소부터 자리를 찾아가야 한다. 그렇다면..

버블 정렬 (bubble sort) 버블 정렬, 거품을 뜻하는 그 버블이 맞다. 서로 인접한 두 원소끼리 비교하고 크기 순으로 위치를 바꾸는 알고리즘인데, 예를 들면 이런 느낌이다. 임의의 배열 [7, 21, 18, 36, 2 ] 이 있다고 가정하면 버블 정렬은 이렇게 비교를 해주는 식이다. (저 동글 동글한 게 꼭 버블같다고 해서 버블 정렬인 듯 하다. ㄱㅇㅇ..) 오름차순으로 정렬한다고 치면, 과정은 다음과 같다. 1. 7과 21을 비교하고 작은 수를 왼쪽에 둔다. -> 7이 더 작으므로 순서는 7 , 21 그대로 [7, 21 , 18 , 36, 2] 2. 21과 18을 비교하고 작은 수를 왼쪽에 둔다. -> 18이 더 작으므로 순서 18, 21로 바뀜 [7, 18, 21, 36, 2] 3. 21과 ..

삽입 정렬은 바닥에 쌓인 책을 책꽂이에 정리하는 것과 같은 알고리즘이라 생각하면 편하다. 다음 그림을 살펴보자. 책꽂이에 책이 한 권 꽂혀있고, 우리는 바닥에 쌓인 책도 올바른 자리에 꽂아두어야 한다. 이 때, 우리는 책을 시리즈 순서대로 꽂아놔야한다. 물론, 1권부터 뽑아서 다시 꽂을 수도 있겠지만, 책이 쌓여있으니 맨 위에 쌓인 책부터 알맞은 자리에 꽂아두기로 하자. 맨 위의 7권은 5권 뒤에 와야한다. (이미 꽂혀있는 5와 비교, 비교횟수 : 1) 3권은 제일 왼쪽에 꽂아야한다. 어렵게 생각할 필요 없다. 이건 책꽂이니까.. 아래 사진처럼 5권과 7권을 조금 밀고 3권을 맨 왼쪽에 꽂으면 된다. (이미 꽂혀있는 5, 7과 비교, 비교횟수 : 2) 이런 식으로! 이제 다음은 9권인데, 9권은 7권 뒤..