Study/Algorithm_C++ 썸네일형 리스트형 [5주차] 이분 탐색 (이진 검색; Binary Search) 이분 탐색 (Binary Search)이란? 개념 정렬된 데이터에서 특정 데이터를 찾을 때 탐색 범위를 절반씩 줄여가며 탐색하는 방법 모든 데이터를 순회하며 확인하는 방식보다 빠름 시간복잡도 \(O(log_2N)\) 중앙값과 찾으려는 데이터를 비교하여 중앙값의 왼쪽 또는 오른쪽 절반 선택 중앙값 > 탐색 데이터 : 왼쪽 중앙값 < 탐색 데이터 : 오른쪽 구현 패턴 데이터 정렬 (필요 없는 경우도 존재) 탐색 범위 지정 low : 0 (또는 초기 탐색 범위의 최소값; 구현 시 편의를 위해 lo로 사용) high : 배열크기 - 1 (또는 초기 탐색 범위의 최대값; 구현시 편의를 위해 hi로 사용) 중앙값 설정 mid : (low + high) / 2 중앙값과 비교 arr[mid] == toSearch : .. [3주차] DP (Dynamic Programming; 동적 계획법) 다이나믹 프로그래밍(동적 계획법)이란? 개념 복잡한 문제를 작은 부분 문제(최적 부분 구조)로 나누어 해결 (≒ 분할정복) 점화식 활용 (점화식; 재귀적으로 정의되는 수학적 함수) cf) 다이나믹 프로그래밍(중복&메모이제이션 o) vs 분할정복(중복&메모이제이션 x) 중복되는 부분 문제(overlapping subproblems) 동일한 부분 문제가 중복 계산될 경우 한 번만 계산하여 결과 재활용 - 계산 중복 횟수는 분할 깊이가 깊어질수록 지수적으로 증가하기 때문 - 계산 결과 재활용 시 속도 향상 가능 계산 결과를 재활용하려면 메모리에 저장 필요 → 메모이제이션(memoization) → 1 & 2 모두 만족하는 경우 다이나믹 프로그래밍 적용 구현 패턴 값 저장 공간 초기화 (계산 결과가 될 수 없는.. 이전 1 다음
