본문 바로가기

Algorithm/배열 탐색

 (3)
Binary Search (이분 탐색) Binary Search (이분 탐색) 설계 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다. 동작 정렬된 배열에서 이진 탐색(Binary Search) 알고리즘을 사용해 보자 13을 찾는다고 경우를 보자 i. 데이터 집합의 중앙값를 선택한다. ii. 중앙 요소의 값과 찾으려는 값을 서로 비교한다. 찾으려는 값(13) < 중앙값(9) 이면, 중앙값(9)의 왼편에서 중..
슬라이딩 윈도우 알고리즘 슬라이딩 윈도우 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 유용한 알고리즘이다. 예를들어 정수로 이루어진 배열 [4, 25, 64, 1, 23, 2, -10, 3, 2] 에서 길이가 3인 서브배열의 합계가 가장 큰 서브배열은 무엇인가? 같은 문제에서 사용될 수 있다. 설계 하나씩 다 더해보면 아래와 같다. 서브 배열 합계 체크 (브루트 포스) #include #include using namespace std; int main() { int n, k; cin >> n >> k; vector v; for (int i = 0; i > input; v.push_back(input); } int sum, max = -1; for (int i =..
투 포인터 알고리즘 Two pointer 어떤 특정 조건을 만족하는 연속 구간을 구할 때 $ O(N) $ 으로 풀 수 있도록 도와주는 알고리즘 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다. 2 개의 포인터를 사용하여 구간의 길이를 가변적으로 잡아가며 특정 조건을 만족하는 구간을 찾는다. 모든 연속 구간을 잡는다면 $ O(N^2)$ 이 될 것이지만 투 포인터 알고리즘을 사용하면 O(N) 의 시간복잡도로 풀 수 있다. 두 포인터 각각 N번 움직이기 때문에 N + N = 2N 번의 연산이 있는 셈이다. 즉, $ O(2N) = O(N) $ 이 된다. (중요) : 항상 e..

티스토리툴바