시간복잡도 (2) 썸네일형 리스트형 [Algorithm] 5. 이진 탐색(Binary Search) 알고리즘 흔히 for 문을 이용해 배열의 처음부터 끝까지 탐색하는 선형탐색은 O(n) 이라는 시간복잡도로 효율성이 떨어집니다.이를 보완하는 탐색 알고리즘으로 대체되는 이분탐색 (Binary Search, 이진 탐색이라고도 합니다 )은 O(log N) 의시간 복잡도를 가지고 있습니다. 주어진 범위의 절반씩 삭제하며 윈도우를 조절하며 찾아가는 기법으로주어진 배열은 순서대로 정렬이 되있어야 사용할 수 있는 알고리즘입니다. 32를 찾는 순서는 아래와 같이 절반의 범위를 줄여가며 진행됩니다 /** * 정렬된 배열에서 특정 요소의 인덱스를 찾는 이진 탐색 함수 * @param {Array} arr - 검색할 정렬된 배열 * @param {*} elem - 찾고자 하는 요소 * @returns {number} - 요소.. [Algorithm] 알고리즘 기본 패턴 3 - Sliding Window 3. Sliding Window 배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용합니다. 창문을 하나 만들어야 합니다. 여기서 말하는 창문이란 개념은 주어진 데이터의 범위를 나타냅니다.그 창문을 만들고 데이터 안에서 창문을 여는 것처럼 이동을 시키며주어진 조건을 클리어하는 알고리즘 패턴입니다. 이 기법은 윈도우의 크기를 나타내는 변수와 하위 배열, 또는 다른 문자열이 주어지며,윈도우의 크기는 고정되거나 가변적인 크기가 될 수 있습니다. 조건에 따라 창문을 이동시키며, 시작 위치에서 시작하면 보통 왼쪽에서 오른쪽으로 이동합니다. 오른쪽에서 왼쪽으로 이동도 가능하고 가운데 위치에서 시작할 수도 있습니다. 그러나 보통 창문을 왼쪽, 즉, 요소.. 이전 1 다음
