반응형 웹개발80 [Data-Structure] Tree (트리)와 Binary Search Tree (이진 탐색 트리) (2)Binary Search Tree (이진 탐색 트리) 란 지난번 글에 이어서 이번에는 Binary Search Tree (BST, 이진 탐색 트리) 에 대해서 알아보았다. 이진 탐색 트리는 최대 2개의 자식만 갖는 트리이다. 트리 구조는 재귀적이므로, 자식 노드 역시 최대 2개의 자식을 갖는다. 이진 탐색 트리에서는 노드의 값이 정렬 방법에 따라 순서가 존재하는데 노드의 왼쪽 서브 트리에는 노드의 값보다 작은 값이, 오른쪽 서브 트리에는 노드의 값보다 같거나 큰 값이 존재하게 된다. 이진 탐색 트리는 트리 자료구조를 활용한 자료구조로 데이터 탐색 속도를 높일 때 사용한다. 이진 탐색 트리가 주어졌을 때, 세가지 방법으로 순회가 가능하다. 전위 순회(Preorder Traversal): 부모 → 좌 → 우 중위 순회(Inorder Traversal): 좌 → 부.. 2020. 10. 26. [Data-Structure] Tree (트리)와 Binary Search Tree (이진 탐색 트리) (1)Tree 구조란 오늘은 트리 구조(Tree)와 이진 탐색 트리(Binary Search Tree)에 대해서 공부해보았다. 트리 구조란 노드로 구성된 계층적 자료구조이다. 최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 트리 구조를 구현할 수 있다. 트리 구조와 관련하여 반드시 알아야 할 개념들이다. [정보통신기술용어해설] 참조 A, B, C, D 등 트리의 구성요소를 노드(node) 라고 한다. 위 그림의 A처럼, 트리 구조에서 최상위에 존재하는 노드를 root이다. 루트를 기준으로, 다른 노드로의 접근하기 위한 거리를 depth 라고 한다. 같은 부모를 가지면서 같은 depth에 존재하는 노드들은 sibling 관계에 있습니다. (같은 부모를 가진 노.. 2020. 10. 26. [Data-Structure] 선형구조와 비선형구조 오늘은 자료구조에 대해서 공부했다. 자료구조(data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택 문제는 대개 추상 자료형의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다. (위키백과) 이 자료구조에는 선형 구조와 비선형 구조로 나뉘는데 선형 구조는 데이터들이 순차적으로 나열된 형태(하나의 데이터 뒤에는 하나.. 2020. 10. 26. [2020.10.25] 10월 넷째주 회고록 오늘은 오랜만에 회고록을 준비했다. 저번 주에는 휴식기를 가졌고 이번 주부터 다시 공부에 들어갔다. 이번 주에는 Data-Structure에 대해서 공부했는데 다양한 자료구조에 대해서 공부할 수 있었다. 스택, 큐, 연결 리스트, 해시 테이블에 대해서 공부했는데 오랜만에 공부하는 자료 구조라 헷갈리는 부분도 있었지만 그래도 잘 구현해냈다. 주말에는 복습을 위주로 공부했고 간단한 알고리즘 공부도 진행하였다. 주말에 공부하는 분량도 회고록에 넣기 위하여 금요일에 쓰던 회고록을 일요일로 바꾸었다. 갈수록 공부가 어려워져 시간이 더 들어가긴 하지만 작은 과제를 하나씩 해결할 때마다 뿌듯함이 점점 더 크게 느껴졌다. 또 자료구조를 직접 구현해보면서 이전의 배운 자바스크립트 기초 문법을 복습해볼 수 있었고 배운 부.. 2020. 10. 25. 이전 1 ··· 9 10 11 12 13 14 15 ··· 20 다음 반응형
