정리 내용
트리 자료구조란
- 데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 항상 데이터가 정렬되어 있다.
- 트리 자료구조는 노드와 노드의 연결로 표현하며 노드는 어떠한 정보를 가지고 있는 개체로 이해할 수 있다.
- 트리 자료구조는 그래프 자료구조의 일종으로 많은 양의 데이터를 관리하기 위한 목적으로 사용한다.
- 트리 자료구는 아래와 같은 특징을 가지고 있다.
1) 트리는 부모 노드와 자식 노드의 관계로 표현된다.
2) 트리의 최상단 노드를 루트 노드라고 한다.
3) 트리의 최하단 노드를 단말 노드라고 한다.
4) 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라고 한다.
5) 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.
- 정리하자면, 큰 데이터를 처리하는 소프트웨어는 대부분 트리 자료구조로 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능하다.
이진 탐색 트리
- 트리 자료구조 중에서 가장 간단한 형태.
- 이진 탐색이 동작할 수 있는 자료구조.
- 아래와 같은 특징을 가진다.
1) 부모 노드보다 왼쪽 자식 노드가 작다.
2) 부모 노드보다 오른쪽 자식 노드가 크다.
- 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드가 성립해야지 이진 탐색 트리라 할 수 있다.
- 이진 탐색 트리 자료구조를 구현하도록 요구하는 코딩 테스트 문제는 출제 빈도가 보통 낮다.
- 이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편이다.
- 데이터의 개수가 1000만 개를 넘어가거나 탐색 범위의 크기가 1000억 이상이면 이진 탐색 알고리즘을 의심하자.
- 그런데 이렇게 입력 데이터의 개수가 많은 문제에 input함수를 사용하면 시간 초과를 받을 수 있다.
- 이를 방지하기 위해 sys 라이브러리의 readline 함수를 이용하면 시간 초과를 피할 수 있다.
- sys 라이브러리를 사용할 때는 한 줄 입력받고 나서 rstrip 함수를 꼭 호출해야 한다.
- 소스코드에 realdine으로 입력하면 입력 후 엔터가 줄 바꿈 기호로 입력되는데 이 공백 문자를 제거하려면 rstrip() 함수를 사용해야 한다.
빠르게 입력받기
import sys
input_data = sys.stdin.readline().rstrip()
print(input_data)
출처 & 깃허브
이것이 취업을 위한 코딩 테스트다 with python
github
