개발65 [알고리즘 이론] 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. [알고리즘 이론] 13. LIS (최장 증가 부분 수열) LIS Longest Increasing Subsequence 의 약자로, 최장 증가 부분 수열 또는 가장 긴 증가하는 부분 수열 이라고 불린다. 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건(오름차순)을 만족하고, 그 길이가 최대인 부분 수열을 찾는 알고리즘이다. 일반적으로 LIS의 간편한 방법에는 DP가 있다. DP에 대해서는 아래 게시글 참고. https://hoozy.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EB%A1%A0-12-DP-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95 이분탐색을 이용한 LIS 이분탐색에 대해서는 아래 게.. 2023. 5. 9. 이전 1 2 3 4 5 6 ··· 17 다음
