알고리즘을 위한 간략 정리/데이터 탐색 (4) 썸네일형 리스트형 [C++] 매개변수 탐색 매개변수 탐색? - 이분 탐색(Binary search)와 상당히 유사한 알고리즘 - Nimrod Megido에 의해 발명되었으며, 최적화 문제를 "결정 문제"로 풀 수 있는 알고리즘 - 시간 복잡도(Time complexity): O(log N) 최적화 문제: 어떠한 함수값을 최적화 시키는 변수를 찾는 문제 결정 문제: 예-아니오의 형태로 답안이 나오는 문제 알고리즘 동작 방식 1. 특정 변수 값(mid)을 토대로 조건을 만족하는지 안하는지 탐색한다. ※ 이때, 구현은 이분 탐색으로 구현한다. 2. 이 탐색 과정에서 우리는 두 가지를 알 수 있다. - 조건을 만족하는 가? -> 결정문제 - 나머지 범위가 조건을 만족하는 가? -> 이분 탐색 3. 조건을 만족하는 범위를 계속 좁혀가며(start와 end.. 투 포인터(TWO-POINTER) 핵심 요약 1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해서 값을 얻는 형태 주로 while문으로 구성 문제 유형 연속된 수들의 합 부분 배열의 합 풀이 방법 포인터 2개가 같은 방향 포인터 2개가 양 끝에서 반대로 진행(이분 탐색과 유사) [C++] 이분 탐색(Binary Search) - lower_bound, upper_bound 핵심 요약 이진 탐색이라고도 불리는 이 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 그러므로, 배열 내부의 데이터가 정렬이 되어있어야 한다. 시간 복잡도는 logN이다. STL 라이브러리 사용 #include //stl 라이브러리 사용을 위함. lower_bound(begin(), end(), value); upper_bound(begin(), end(), value); lower_bound란? begin()에서 end()의 범위 중에서 value값 이상이 나타나는 가장 작은 이터레이터를 반환하는 것입니다. value가 존재 하지 않는다면 value보다 큰 값 중 가장 작은 값이 나타나는 이터레이터를 반환합니다. algorithm 헤더 안에 존재합니다. v.. [C++] 이분 탐색(Binary Search) - while문 핵심 요약 이진 탐색이라고도 불리는 이 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 그러므로, 배열 내부의 데이터가 정렬이 되어있어야 한다. 시간 복잡도는 logN이다. 코드로 구현 변수 3개(start, end, mid)를 사용하여 탐색한다. 주로 while문을 통해 구성된다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. [예제] N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 key라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 찾을 경우 1을 출력, 없을 경우 0을 출력하라. #include #include #include using namespace std; int n.. 이전 1 다음
