AIHorizons

선형 탐색 (Linear Search) 순차 검색이라고도 부르며 데이터가 모인 집합의 처음부터 끝까지 하나하나 비교하며 원하는 값을 찾아내는 알고리즘. 데이터 배열이 정렬되어 있지 않아도 가능하고, 난이도가 쉽지만, 데이터의 양이 많아질수록 소요되는 시간이 많아진다. 브루트-포스처럼 모든 케이스를 결국 보는 것과 같다고 생각..? 시간 복잡도는 데이터의 길이 n의 O(n) 이다. def linear_search(arr, x): for i in range(len(arr)): if arr[i] == x: return i return -1 이진 탐색 (Binary Search) 이분 탐색이라고도 부르며, 반으로 나누어 연산하기 때문에 다음과 같은 이름이 붙었다. 이진 검색은 중간값부터 탐색을 시작하기에 중간값..

사용하는 경우 1차원 배열이 있을 경우 리스트에 순차적으로 접근해야 할 때 두 지점을 설정해 해결하는 것. 예를 들어 N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 경우 모든 케이스를 조사하는 경우 시간 복잡도는 O(N^2)이 된다. 하지만 투 포인터를 사용하는 경우 end 포인터가 배열의 끝까지 도달하면 종료되기 때문에 복잡도는 O(N)이다. (시간 복잡도 빅-오 표기법에서는 상수항을 무시하기 때문에 O(2N)같은건 없다!) 과정 위의 케이스에서 M = 5라고 가정하고 배열의 구간 합이 5가 되는 지점을 찾는다고 하자 현재 start = 0 end = 0이며, 합 S = 두 포인터가 같기 때문에 0. end가 뒤로 움직일 때는 새로 포함한 원소를 S에 더하..