알고리즘2 [알고리즘] 누적합 알고리즘 (Prefix sum algorithm) 누적합 (Prifix sum)나열된 수의 누적된 합배열의 일부 구간에 대한 합을 매우 빠르게 구할 수 있도록 함 구간 합 구하기N개의 원소로 이루어진 배열에서 구간 합을 구하는 방법반복문을 통한 구간 합배열의 i번째 원소부터 j번째 원소까지 순회하며 값을 더함구간 [i, j]의 합 = arr[i] + arr[i+1] + ... + arr[j]시간복잡도: O(N)구간의 길이에 비례하여 시간이 증가하기 때문에 여러 번 구간 합을 구해야 할 때 비효율적 누적합 알고리즘 사용미리 배열의 누적합 배열을 계산누적합 배열 S에서 S[k]는 배열의 0번째 원소부터 k번째 원소까지의 합을 의미구간 [i, j]의 합 = S[j] - S[i - 1]시간복잡도: O(1)누적합 배열을 미리 계산하는 데 O(N)이후 각 구간 합.. 2024. 11. 5. [알고리즘] 이분탐색/이진탐색 Binary Search 이분 탐색오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘찾고자 하는 값과 중간값을 반복적으로 비교해 탐색 범위를 절반씩 좁혀가며 데이터를 탐색함변수 3개(high, low, mid) 사용 처음 리스트의 중간값을 임의의 값으로 선택 mid = (low + high) / 2그 값과 찾고자 하는 값의 크고 작음을 비교처음 선택한 중앙값이 만약 찾는 값보다 크면(mid > key) 그 값은 새로운 최댓값이 됨 (high = mid - 1) 작으면(mid ) 그 값은 새로운 최솟값이 됨 (low = mid + 1)같으면 (mid == key) 중간값 리턴 후 종료 장점검색이 반복될 때마다 탐색 범위가 반으로 줄어들어 목표값을 찾을 확률이 두 배가 되므로 속도가 빠름시간 복잡도: O(log N)비교.. 2024. 8. 13. 이전 1 다음
