DailyStudyNote

파라메트릭 서치(Parametric Search) 파라메트릭 서치(Parametric Search) 파라메트릭 서치(Parametric Search)는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. 결정 문제란, '예' 혹은 '아니오'로 답하는 문제를 말한다. '주어진 범위에서 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 파라메트릭 서치를 사용한다. 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀 나갈 수 있다. * 이진 탐색 개념 참고 [알고리즘] 이진 탐색(Binary Search, 이분 탐색) 이진 탐색(Binary Search) 이진 탐색(Binary Search) 란? 정렬되어 있는 배열에서 ..

이진 탐색(Binary Search) 이진 탐색(Binary Search) 란? 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X 와 비교한다. X 가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터를 대상으로, X 가 중간 값보다 크면 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다. 코드(Python) # 반복 알고리즘 def binary_search(arr, target): low, high = 0, len(arr) - 1 while low target: high = mid - 1 if arr[mid] == target: return mi..

이진 탐색 트리(BST, Binary Search Tree) 이진 탐색 트리 정의 이진탐색 트리란 모든 노드에 대해서, 왼쪽 서브트리에 있는 데이터는 모두 현재 노드 값보다 작고, 오른쪽 서브트리에 있는 데이터는 모든 현재 노드의 값보다 큰 성질을 만족하는 이진트리이다. 왼쪽 및 오른쪽 하위 트리도 각각 이진 탐색 트리이며, 각 노드는 중복된 키를 허용하지 않는다. 연산의 정의 ▶ insert(key, data) : 트리에 주어진 데이터 원소를 추가한다. ▶ remove(key) : 특정 원소를 트리로 부터 삭제한다. ▶ lookup(key) : 특정 원소를 검색한다. ▶ inorder(): 키의 순서대로 데이터 원소를 나열한다. ▶ min(), max(): 최소 키, 최대 키를 가지는 원소를 각각 탐색..