본문 바로가기
728x90
반응형

알고리즘 이론

 (11)
분할정복(Divide and Conquer) 분할정복(Divide and Conquer) 분할정복(Divide and Conquer)은 컴퓨터 과학 및 알고리즘 이론에서 사용되는 문제 해결 방법 중 하나로, 큰 문제를 작은 부분 문제로 나누어 해결하는 방법입니다. 이 방법은 문제를 더 작은 문제로 분할하고, 각각의 작은 문제를 독립적으로 해결한 후 그 결과를 결합하여 원래 문제를 해결하는 전략입니다. 분할정복 알고리즘은 일반적으로 세 단계로 이루어집니다. 1. 분할(Divide): 원래 문제를 더 작은 부분 문제로 분할합니다. 이 단계에서 문제를 더 작은 크기의 하위 문제로 분리하고, 이를 해결할 수 있는 재귀적인 접근 방식을 적용합니다. 2. 정복(Conquer): 분할된 각 부분 문제를 독립적으로 해결합니다. 이 단계에서 작은 부분 문제들을 재..
나머지 부분합 배열 및 나머지가 같은 배열 개수 구하기 나머지 부분합 배열 나머지 부분합 배열(Remainder Prefix Sum Array)은 주어진 수열의 각 원소를 어떤 수 K로 나눈 나머지를 누적한 배열을 의미합니다. 이를 계산하기 위해서는 부분합 배열(Prefix Sum Array)을 먼저 계산해야 합니다. 부분합 배열이란, 주어진 수열의 각 원소를 누적한 배열로, 예를 들어 주어진 수열이 [1, 2, 3, 4, 5]라면 부분합 배열은 [1, 3, 6, 10, 15]가 됩니다. 나머지 부분합 배열은 이 부분합 배열의 각 원소를 K로 나눈 나머지를 누적한 배열입니다. 예를 들어, 주어진 수열이 [1, 2, 3, 4, 5]이고 K가 3이라면, 부분합 배열은 [1, 3, 6, 10, 15]가 되고, 이를 3으로 나눈 나머지를 누적한 나머지 부분합 배열은..
냅색(Napsack) 문제(DP) 냅색(Napsack) 문제는 DP 알고리즘을 활용하여 해결할 수 있는 대표적인 문제 중 하나입니다. 이 문제는 무게와 가치가 각각 다른 여러 개의 물건이 있을 때, 주어진 가방의 용량을 초과하지 않으면서 가치의 합을 최대로 하는 물건들의 조합을 찾는 문제입니다. 냅색 문제는 0/1 냅색과 무한 냅색으로 나누어집니다. 0/1 냅색은 각 물건을 하나만 선택할 수 있으며, 무한 냅색은 각 물건을 여러 번 선택할 수 있습니다. 0/1 냅색 문제를 예로 들면, 물건의 종류가 n개이고, 각 물건의 무게와 가치가 w와 v로 주어질 때, 가방의 용량이 W일 때, 최대 가치를 구하는 문제입니다. 이 문제를 DP로 해결하기 위해서는 물건의 종류와 가방의 용량을 하나의 축으로 하는 2차원 배열을 선언하고, 해당 배열을 채워..
LCS(Longest Common Subsequence) LCS(Longest Common Subsequence)는 두 개 이상의 문자열에서 공통으로 나타나는 가장 긴 부분 문자열을 찾는 알고리즘입니다. LCS 알고리즘은 동적 프로그래밍(Dynamic Programming)을 활용하여 구현할 수 있으며, 다양한 응용 분야에서 사용됩니다. 예를 들어, LCS는 DNA 염기서열 분석, 문서 비교 및 유사성 검색, 음악 분석, 이미지 처리 등에서 사용됩니다. LCS 알고리즘의 시간 복잡도는 O(nm)이며, n과 m은 각각 두 문자열의 길이입니다. 이 알고리즘은 다른 문자열 비교 알고리즘과 함께 문자열 비교 및 유사성 검색 문제를 해결하는 데 널리 사용됩니다. 다음은 일반적인 LCS 알고리즘의 구현 과정입니다. 1. 두 문자열 X와 Y를 입력으로 받습니다. 2. X와..
LIS 알고리즘 및 이진(이분) 탐색 LIS(Longest Increasing Subsequence) 주어진 수열에서 가장 긴 증가하는 부분 수열을 찾는 알고리즘 LIS 알고리즘은 일반적으로 동적 계획법(Dynamic Programming)을 이용하여 O(n^2)의 시간복잡도로 구할 수 있습니다. 각 인덱스에서 끝나는 LIS의 길이를 저장하는 DP 테이블을 만들고, 이전 인덱스들을 순회하며 현재 인덱스의 값보다 작은 값 중에서 가장 긴 LIS를 찾아 현재 인덱스의 DP 테이블 값을 갱신해나가는 방식입니다. 동적계획법을 이용한 LIS public static int lis(int[] arr) { int n = arr.length; int[] dp = new int[n]; //해당 인덱스의 숫자까지 증가한 숫자의 개수 저장 Arrays.fill..
Memoization Memoization(메모이제이션)은 동적 계획법(Dynamic Programming)의 일종으로, 함수의 실행 결과를 저장해놓고 나중에 다시 그 함수를 호출하면 저장된 결과를 반환하여 중복 계산을 피하는 기법입니다. 즉, 한 번 계산한 값을 저장해두고 다음에 같은 입력값으로 함수가 호출될 때 저장된 값을 반환하는 방식입니다. 메모이제이션을 사용하면 같은 입력값으로 함수를 여러 번 호출할 때, 함수 내부의 연산을 다시 수행하지 않고 이미 계산된 결과를 반환하여 중복 계산을 피할 수 있습니다. 이를 통해 함수의 실행 속도를 향상시킬 수 있습니다. 메모이제이션은 보통 재귀 함수와 함께 사용됩니다. 재귀 함수에서 중복 계산이 많이 일어날 때, 메모이제이션을 활용하여 중복 계산을 피할 수 있습니다. 예를 들어,..
2차원배열을 1차원 배열로 int[][] arrTwo = new int[n][m]; for(int i=0; i
유클리드 호제법 JAVA 두 양의 정수 혹은 두 다항식의 최대공약수를 구하는 방법. 작은 수를 a, 큰 수를 b라 하고 b는 a로 나누어 떨어지지 않는다면 b = a * q + r 로 나타낼 수 있다(q : 몫, r : 나머지) 이 때 나눈 수인 a는 나머지인 r보다 크므로 a를 r로 나눌 수 있게 되는데, a = r * q' + r'으로 나타낼 수 있고 이는 b = (r * q' + r') * q + r 이 된다. 만약 여기서 r' = 0 이라면 b = (r * q') * q + r 로 나타내어 a 와 b 모두 r을 인수로 갖고 있음을 알 수 있는데 이 규칙대로 숫자를 계속해서 나눈다면 마지막 나머지가 0 이 됐을 때 전체 숫자는 나눈 수를 인수로 갖게 되므로 그 수가 최대공약수가 된다. 예시 코드) public class M..
728x90
반응형

티스토리툴바