알고리즘
-
[알고리즘] Two-Pointers Algorithm (투 포인터 알고리즘)알고리즘 2024. 6. 15. 11:43
정의1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해 가면서 원하는 값을 찾을때 까지 탐색하는 알고리즘배열이나 리스트에 순차적으로 접근해야 할 때 두개의 포인트의 위치를 기록하면서 처리한다배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)의 시간복잡도로 단축 시킬 수 있다이분탐색 알고리즘과 유사한 방식이다 동작 방식왼쪽 left, 오른쪽 right 또는 start, end 이런 식으로 포인트의 변수 이름을 지정한다조건은 항상 두 포인터의 관계는 left 1. 초기화 두개의 포인터를 초기화 한다, 이 포인터들은 배열의 시작과 끝 또는 특정 위치에서 시작할 수 있다 2. 반복 처리 반복문을 사용하여 두 포인터가 특정 조건을 만족할 때까지 ..
-
[알고리즘] 이분 탐색 / 이진 탐색 Java알고리즘 2024. 4. 22. 19:22
이분 탐색 / 이진 탐색 - 데이터가 정렬돼 있는 상태에서 값을 찾아내는 알고리즘 이다- 데이터의 중앙값과 찾고 하는 값을 비교해서 데이터의 탐색 범위를 절반씩 좁혀가며 탐색하는 방법이다- 데이터가 정렬되어 있어야만 사용할 수 있다 기능특징 시간 복잡도타깃 데이터 탐색중앙값 비교를 통한 대상 탐색 축소 방식O(logN) 탐색 과정1) 현재 데이터셋의 중앙값을 선택한다 2) 중앙값 > 타깃 데이터 일때 중앙값 기준으로 왼쪽 데이터셋을 선택한다3) 중앙값 4) 과정 1~3 을 반복하여 중앙값 == 타깃 데이터일때 탐색을 종료한다 Java로 하는 이분 탐색 구현 1. 반복문 구현public boolean searchBinary (int[] array, int n) { int left = 0; in..