AIB 섹션 5 컴퓨터공학 N521 Data Structure Intermediate
- 재귀와 기존 프로그래밍의 동작방식의 차이점
- 재귀는 재활용의 개념. 마지막 종료 조건 확인해서 끝내기
- 재귀를 통해 데이터를 다루는 방법은?
- 트리자료 대표 특징
배울 것: 검색과 재귀, 트리의 기본구조
검색
기본적으로 선형 검색으로, 컬렉션이 무작위, 즉 정렬이 되지 않은 경우 사용한다.
일반적으로 다양한 알고리즘에서 최적 알고리즘 경로를 측정하는데 사용한다고 함.
재귀
재호출. 반복해서 다시 호출한다. 제자리 재귀
스택 개념과 연결된다. 스택의 순서로 보면 맨 마지막에 들어온 것부터 처리되는데, 재귀 맨 끝은 맨 마지막에 들어갔고, 그것부터 처리됨.
반복적으로 함수를 호출하기 때문에 메모리를 더 사용할 경우가 많다. 그럼에도 복잡한 문제를 해결할 때 용이할 수 있다.
장점: 변수 개수 줄일 수 있다. for i에서 i 필요 없음.
분할정복법을 잘 활용하기 위해 재귀개념이 필요하므로 미리 배운다.
조건 세 가지:
- 기본 케이스/조건이 있어야 한다. 재호출이 아니라 기본 조건에서 종료할 수 있도록
- 추가 조건과 기본 조건에 차이점이 있어야 한다.
- 반드시 자기 자신을 호출해야 한다.
파이썬은 기본적으로 재귀 깊이를 1000으로 제한하고 있기 때문에, 그 제한을 조절하기 위해 sys.setrecursionlimit(num)을 사용한다.
사용 예: 크롤링, 특정 버튼으로 웹사이트 초기화
트리
ADT 중 하나. 이 구조만의 특징을 알아보기
노드의 형식이 다양하고, 1차적인 방향으로만 흐르지 않는다.
용어: Root, parent, siblings, leaf, child, subtree(자식이면서 부모인 노드가 있는 부분), 차수
정(full), 포화(perfect), 완전(complete), 검색(BST)
BST는 값의 크기 조건에 맞도록 값을 넣어주는 트리이다.
트리 사용 예: 디렉토리, 이진탐색트리로 자료 정리, decision tree
댓글남기기