CS/자료 구조 및 알고리즘17 [알고리즘 이론] 15. 펜윅트리 펜윅트리 세그먼트 트리의 가장 흔한 사용 예는 바로 구간 합을 빠르게 구하는 것이다. 이 경우 세그먼트 트리 대신 쓸 수 있는 세그먼트 트리의 진화 형태로 펜윅트리(Fenwick Tree) 혹은 이진 인덱스 트리(Binary Indexed Tree) 라고 불린다. 구간 합 대신 부분 합만을 빠르게 계산할 수 있는 자료구조로 만들어도 구간 합을 계산할 수 있다. 세그먼트 트리는 아래 게시글 참조 https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC-Segment-Tree 필요없는 구간 지우기 tree 배열은 오른쪽 끝 위치가 arr인 구간의 합이.. 2023. 5. 9. [알고리즘 이론] 14. 최단거리 최단 거리 그래프 최단 거리 구하는 알고리즘이다. 1. 다익스트라 알고리즘 그래프의 최단 경로 구하는 알고리즘. 하나의 정점에서 출발하는 최단 거리를 구함(출발지만 정함) 음수 가중치 없어야 함 인접 행렬로 표현된 그래프의 경우 시간 복잡도 : O(n^2) 우선순위 큐를 사용하여 시간 복잡도를 O(mlogn)까지 낮출 수 있다 -> 개선된 다익스트라 알고리즘 탐욕법과 동적 계획법 사용 원리 자세한 원리는 아래 게시글 참조 https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 알고.. 2023. 5. 9. [알고리즘 이론] 12. DP (동적 계획법) DP (Dynamic Programming) 큰 문제를 작은 문제들로 나누어 푸는 알고리즘이다. DP의 조건 작은 문제의 반복이 일어나는 경우 같은 문제는 구할 때마다 정답이 같다. 1. Memoization 을 이용한 피보나치 수열 알고리즘 반복하면서 구한 정답은 또 구하지 않게 저장하면서 작은 문제로 나누어 푸는 알고리즘. public class Fibonacci { static int[] dp = new int [1000]; static int fibonacci(int n) { if (n == 0) return 0; if (n == 1) return 1; if(dp[n] != 0) return dp[n]; dp[n] = fibonacci(n - 2) + fibonacci(n - 1); return .. 2023. 5. 9. [알고리즘 이론] 11. 이분탐색 / 이진탐색 (Binary Search) 이분 탐색 / 이진 탐색 (Binary Search) 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다. 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 과정이다. 원리 처음 범위는 인덱스 0부터 끝까지이고, 이 때 중간 인덱스를 mid로 한다. mid의 값과 찾는 원소를 비교한다. 찾는 원소와 mid의 값이 같다면 탐색 종료한다. mid start는 mid+1로 하고 다시 반복한다. mid > 찾는 원소 -> end는 mid-1로 하고 다시 반복한다. 만약 end > start가 된다면 해당.. 2023. 5. 9. 이전 1 2 3 4 5 다음
