우선순위 큐

• 순서대로 기다리고 있는 자료들을 저장하는 자료구조라는 점에서 큐와 비슷
• 가장 먼저 입력된 자료가 가장 먼저 꺼내지는 것이 아니라, 우선순위가 가장 높은 자료가 가장 먼저 꺼내짐
• 힙 트리 사용

트립

• 입력이 특정 순서로 주어질 때 그 성능이 떨어진다는 이진 검색 트리의 단점을 해결하기 위해 고안된 일종의 랜덤화된 이진 검색 트리
• 이진 검색 트리와 같은 성징을 가지고 있지만 트리의 형태가 원소들의 추가 순서에 따라 결정되지 않고 난수에 의해 임의대로 결정
• 트리 높이의 기대치는 항상 일정
• 새 노드가 추가될 때마다 해당 노드에 우선순위를 부여

• 트리의 대표적인 사례 : 검색 트리
• 검색 트리 중 흔하게 사용되는 것 : 이진 검색 트리

트리 : 계층적 구조를 갖는 자료들을 표현하기 위한 자료구조 탐색형 트리 자료 구조 - 예: 이진 검색 트리

큐 - 선입선출

스택 - 후입선출

데크- 양쪽 끝에서 넣고 뺄 수 있음

동적 배열

배열의 문제 : 처음에 배열을 선언할 때 배열의 크기를 지정해야 하며, 그 이상의 자료를 집어넣을 수 없다는 점이다. -> 그래서 동적 배열이 고안됨 동적 배열은 대게 언어의 표준 라이브러리에 포함되어 있으므로, 배열의 특성을 그대로 이어받음

동적 계획법

• 분할 정복과 같은 접근방식을 의미
• 차이는 문제를 나누는 방식
• 동적계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있기 대문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 재활용하면서 속도 향상 -> 문제의 답을 메모리에 저장, 캐싱
• 함수의 결과를 저장하는 장소를 마련해두고 재활용하는 최적화 기법 = 메모이제이션
• 입력이 같으면 출력이 항상 같은 함수에만 메모이제이션을 적용할 수 있다
• 참조적 투명함수의 경우에만 메모이제이션이 적용 가능