이진 트리 순회 이진 트리를 순회한다는 것은 이진 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미합니다. 이진 트리에서 순회가 중요한 이유는, 순회 순서에 따라 기대할 수 있는 결과값이 다르기 때문입니다. 이진 트리 순회 방법 전위, 중위, 후위 총 3가지의 방법이 있습니다. 이는 루트와 왼쪽 서브트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐에 따라 구분됩니다. 만약 루트를 방문하는 작업을 $V$라 하고, 왼쪽 서브트리 방문을 $L$, 오른쪽 서브트리 방문을 $R$이라고 한다면 다음과 같이 3가지 방법을 생각할 수 있습니다. 이진 트리의 순회방법 전위 순회(preorder traversal): VLR 중위 순회(inorder travers..

트리란? 트리(Tree)는 나무입니다. 데이터의 자료를 나무의 형태처럼 나타냈다고 해서 트리라는 이름이 붙었습니다. 물론 데이터들을 정말 2차원 형태의 나무 그림으로 표현하는 것이 아니고, 앞에서 살펴본 연결 리스트에서 노드를 만들었듯이 여기서도 노드를 만들어서 서로 연결하며 구조를 만들면 됩니다. 나무를 자세히 살펴보면 나뭇가지가 나있는 것을 알 수 있는데, 이 형태를 뒤집어보면 가장 위에 뿌리가 오고 맨 아래에 나뭇잎이 매달려 있는 것을 상상해볼 수 있습니다. 이런 구조는 컴퓨터에서 자주 사용됩니다. 파일의 구조가 트리의 형태와 유사합니다. 이 곳에서는 UX가 폴더로 이루어져있어 트리라고 생각하지 못할 수도 있지만 노드로 표현한다면 트리처럼 나타낼 수 있어 결국 계층적인 데이터 구조를 표현할 수 있습..

이중 연결 리스트 (Double Linked List) 이중 연결 리스트는 한 노드에 link 멤버가 두 개 있는 연결 리스트를 말합니다. 이전에 설명한 단순 연결 리스트와 원형 연결 리스트는 노드 탐색을 하든, 출력을 하든 항상 다음 노드를 찾아가는 방식이었습니다. 그러나 이 둘은 이전 노드를 탐색하려면 번거로운 과정을 거쳐야 합니다. 실생활에 예를 들자면 일방통행 도로를 생각해볼 수 있겠네요. 가고싶은 장소가 있는데 모르고 지나쳤을 때 다시 돌아가려면 어떻게 해야하나요? 후진해서 지나친 곳을 갈 수 있겠지만, 도로 상황이 번잡하고 무조건 한 방향으로만 움직여야 한다면 빙 돌아서 그 도로를 다시 진입해야겠죠. 지금까지 구현한 리스트는 그런 방식이었습니다. 이중 연결 리스트는 이러한 번거로움을 방지하고자..

원형 연결 리스트 (Circular Linked List) 원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 리스트입니다. 단순 연결 리스트는 마지막 노드의 link 필드가 NULL이라고 언급했습니다. 하지만, 원형 연결 리스트는 NULL이 아니라 첫 번째 노드 주소가 됩니다. 마지막 노드를 방문해도 첫 번째 노드로 가게 되고 모든 노드가 link 멤버에 NULL이 되어 있지 않은 상태로 연결되어 있는 상태가 됩니다. 이렇게 된다면 노드를 삽입할 때 상수 시간으로 고정이 된다는 장점이 있습니다. 기존에 단순 연결 리스트에서는 끝에 노드를 삽입하기 위해 리스트의 길이만큼 걸리게 되지만, 원형 연결 리스트에서는 헤드 포인터 자체를 옮겨버리면 되기 때문에 훨씬 적은 시간 안에 연산이 이루어지게 됩니다..

리스트란? List가 무엇일까요? 사전을 찾아보지 말고 이번에는 일상적으로 사용하는 것들을 살펴보겠습니다. To-do List 코딩, 독서, 밥 먹기, 친구들과 게임, ... 버킷 리스트 해커톤 우승, 게이밍 컴퓨터 조립, 해외여행, ... 오늘 저녁에 장 볼 목록 토마토, 배추, 김치, 양파, ... 이런 식으로 리스트를 만들어 그 안에 있는 항목들을 정리할 수 있습니다. 데이터도 마찬가지로 이런 식으로 정리할 수 있습니다. 지금까지 스택과 큐를 살펴봤었는데, 큰 범주로 보자면 이것들도 모두 리스트에 속합니다. 배열 배열은 리스트를 구현하는 가장 기본적인 방법입니다. 하지만 배열 특성상 한 번 크기를 지정하면 바꿀 수 없습니다. 따라서 데이터를 추가하고 싶어도 크기가 크지 않다면 문제가 발생할 수 있습..

덱(Deque; Double-Ended Queue)이란? 앞서 설명한 큐는 데이터가 삽입되는 곳과 삭제되는 곳이 달랐지만 덱은 그렇지 않습니다. 큐의 앞과 뒤에서 모두 삽입과 삭제가 가능한 큐를 의미합니다. 덱 ADT 덱의 특징에 맞게 양쪽에서 원소를 추가할 수 있게 짜여져 있습니다. create() ::= 덱 생성 init(dq) ::= 덱 초기화 is_empty(dq) ::= 덱이 비었는지 검사 is_full(dq) ::= 덱이 꽉 차있는지 검사 add_front(dq, e) ::= 덱의 앞 원소 추가 add_rear(dq, e) ::= 덱의 뒤 원소 추가 delete_front(dq) ::= 덱의 앞 원소 제거 및 반환 delete_rear(dq) ::= 덱의 뒤 원소 제거 및 반환 pop_fron..

원형 큐 (Circular Queue) 앞서 선형 큐의 단점을 설명하면서 rear가 가리키는 인덱스에 삽입한다고 했습니다. 이는 큐의 크기에 따라 제한될 수 있다고 했습니다. 원형 큐는 이 점을 개선할 수 있습니다. 어떤 방식으로 개선할 수 있을까요? 큐의 삽입 함수인 enqueue()에서는 rear을 1 증가시키면서 다음 인덱스에 큐를 삽입할 수 있습니다. 만약 MAX_QUEUE_SIZE에 인덱스가 접근하려고 하면 자동으로 인덱스를 0으로 만들어주면 될 것입니다. 이렇게 숫자가 꽉 차면 0으로 돌아가는 현상을 어디서 겪을 수 있을까요? 바로 나머지 연산에서 찾을 수 있습니다. 0을 5로 나누었다고 해봅시다. 수학적으로는 말이 안되지만, 일단 해봅시다. 나머지 연산에 따르면 나머지가 0이 나옵니다. 1를..