Tech/Algorithm & DS (6) 썸네일형 리스트형 [DS] 이진 탐색 트리 - Binary search tree, 순회 - Traversal (구현) 이진 탐색 트리의 구현 방법에는 여러 가지가 있습니다. 이 글에서는 리스트를 사용하여 재조정 없이 단순히 삽입만 수행하는 트리를 만들고 각 노드를 탐색하여 출력하고자 합니다. 트리 구조에서 각각의 노드를 정확히 한번씩 체계적인 방법으로 방문하는 것을 트리 순회 Tree traversal 라 하는데, 삽입된 원소들을 순회하는 방법은 크게 두 가지 분류로 나뉘며, 대표적인 다음 네 가지 탐색법이 있습니다. Reference : https://en.wikipedia.org/wiki/Tree_traversal Tree traversal - Wikipedia "Tree search" redirects here. It is not to be confused with Search tree. In computer sc.. [DS] 이진 트리 - binary tree (개념 및 이진 트리의 종류) 트리 Tree 는 원소들을 계층적으로 저장하는 비선형 non-linear 자료구조입니다. * 위 그림의 나무를 뒤집어 둔 것과 비슷하게 생겼습니다. 최상의 원소 루트 root를 제외한 각각의 원소는 하나의 부모 parent 노드와 0개 이상의 자식 child 노드들을 가지고 있습니다. 여기서 자식이 없는 노드를 외부 노드 external node 혹은 리프 노드 leaf node, 하나 이상의 자식 노드를 가진 노드를 내부 노드 internal node 라 칭합니다. 이 중에서, 이진 트리 혹은 바이너리 트리 binary tree 는 하나의 노드가 최대 2개의 자식을 가지는 트리 자료구조를 의미합니다. 아래 그림은 바이너리 트리가 어떻게 구성되는지를 나타낸 것입니다. 이진 트리에서는 내부 노드의 자식을 .. [DS] 링크드 리스트 - Linked List (개념 및 구현) 앞서 구현한 스택과 큐는 모두 배열을 기반으로 작성되었습니다. 배열은 메모리 공간에서 연속적이며, 임의 접근(Random access)가 가능한 장점이 있지만 고정된 크기를 가지고 있으며 연속된 배열 중간의 원소를 삽입/삭제하는데 걸리는 시간이 크다는 단점을 가지고 있습니다. 이러한 단점을 해결하기 위하여 등장한 것이 '연결 리스트 (혹은 링크드 리스트) Linked List' 자료구조입니다. 링크드 리스트는 배열과 달리 원소뿐만 아니라 다음 원소가 어디 있는지에 대한 위치정보를 포함하고 있습니다. 이러한 데이터 덩어리를 '노드 Node' 라고 부릅니다. 링크드 리스트는 메모리 공간에서 연속적이지 않아도 되며 노드들 가운데 새로운 노드를 삽입하거나 삭제하는 것이 배열보다 용이하고 가변적인 크기를 가지고 .. [DS] 큐 - Queue (개념 및 배열로 큐 구현하기) 큐는 선입선출(FIFO, First-In, First-Out)의 원리에 따라 삽입과 삭제를 수행하는 자료구조입니다. 실생활의 모든 대기 줄 혹은 매장에서 음료를 판매하는 방식을 생각하면 됩니다. 다음 그림은 큐가 어떻게 동작하는지를 나타낸 것입니다. C++에서 배열을 사용하여 간단히 큐를 구현하겠습니다. 큐는 먼저 들어간 원소가 가장 먼저 삭제되기 때문에 스택과 같은 방법으로 배열을 사용한다면 원소가 하나 삭제될 때 마다 위 그림처럼 다른 원소들을 모두 이동시켜야 하므로 굉장히 비효율적인 방식으로 동작하게 됩니다. 이를 해결하기 위한 방법은 여러 가지가 있지만, 이 글에서는 배열을 환형 방식(Circular way)으로 사용하여 문제를 해결하겠습니다. 환형 배열을 사용하는 경우, 두 개의 인덱스 fron.. [DS] 스택 - Stack (개념 및 배열로 스택 구현하기) 스택은 후입선출(LIFO, Last-In, First-Out)의 원리에 따라 삽입과 삭제를 수행하는 자료구조입니다. 실생활에서 접시를 쌓아 둔 것과 비교할 수 있습니다. (접시를 층층이 쌓아 둘 때, 가장 먼저 쌓아 둔 접시는 맨 아래에 위치하게 되고, 나중에 쌓은 접시는 가장 위에 위치하게 되어 접시를 사용할 때 먼저 사용됩니다.) 스택은 구현이 쉬운 편이며 상당히 많은 분야에서 응용됩니다. 다음 그림은 스택이 어떻게 동작하는지를 나타낸 것입니다. C++에서 배열을 사용하여 간단히 스택을 구현하겠습니다. 이전에, 예외 처리를 위해 커스텀 예외 처리 클래스를 구현하였습니다. #ifndef RUNTIME_EXCEPTION_H #define RUNTIME_EXCEPTION_H #include using st.. 추가 변수(혹은 임시 변수) 없이 SWAP 구현하기 일반적으로 배열 등에 있는 두 변수를 교환할때는 call by reference로 두 변수의 메모리 주소를 함수로 넘긴 다음, 다음과 같이 임시변수를 사용하여 값을 교환합니다. void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } 다음은 third variable인 tmp변수 선언 없이 두 값을 교환하는 방법들입니다. Reference : https://www.geeksforgeeks.org/swap-two-numbers-without-using-temporary-variable/ How to swap two numbers without using a temporary variable? - GeeksforGeeks Given two variabl.. 이전 1 다음
