TIL0814
오늘 배운 것
- 분할 정복 (Divide and Conquer)
- 큰 문제를 동일한 형태의 작은 문제로 나누는 기법이다.
- 응용 예시로는 같은 색 공간 만들기가 있다.
- 탐욕 알고리즘 (Greedy Algorithm)
- 이진 탐색 (Binary Search)
- 정렬된 상태의 데이터에서 특정 값을 찾는 탐색 방법이다.
- 적용 아이디어적 접근 형태를 다룬다.
java.util.Arrays 클래스에서 binarySearch라는 이름의 이진 탐색 API를 제공한다.- 이 API는 찾는 데이터가 있으면 해당 인덱스를 반환하고 , 찾지 못하면 삽입 위치에 1을 더한 값에 음수를 취한 값을 반환한다.
- Lower Bound & Upper Bound
- Lower Bound: 목표 값보다 같거나 큰 값이 처음 나오는 위치를 찾는다.
- Upper Bound: 목표 값보다 큰 값이 처음 나오는 위치를 찾는다.
Lower Bound와 Upper Bound의 차이는 등호 사용 여부에 있다.
- 파라메트릭 서치 (Parametric Search)
- 답의 범위가 주어졌을 때, 중간 지점에서 시작하여 이진 탐색처럼 움직이며 정답을 찾는 방법이다.
- 자료 구조
- TreeMap: 키를 기준으로 정렬하는 효과가 있다.
- TreeSet: 정렬된 원소 집합의 효과가 있다.
- A형 등급 검정 준비를 위해 Array, List, Map, Set, Stack, Queue, Graph 등의 자료구조를 다룬다.
- Graph는 인접 행렬, 인접 리스트, 간선 리스트 등으로 표현될 수 있다.