728x90 Quality control (Univ. Study)/Algorithm Design40 알고리즘 설계 실습 - 연쇄 행렬 곱셈 문제i × j 행렬과 j × k행렬을 곱하기 위해서는 i × j × k번 만큼의 곱셈이 필요합니다. 연쇄적으로 행렬 을 곱할 때, 어떤 행렬 곱셈을 먼저 수행하는지에 따라서 필요한 곱셈의 횟수는 달라지게 됩니다.예를 들어, 크기가 1×9인 행렬 A, 크기가 9×9인 행렬 B, 크기가 9×3인 행렬 C가 주어졌을 때 행 렬의 곱 ABC를 구하는 경우, 다음과 같이 여러 방법이 존재합니다. AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 1×9×9 + 1×9×3 = 81 + 27 = 108번입니다.BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 9×9×3 + 1×9×3 = 243 + 27 = 270번입니다. 행렬 N개의 크기가 주어졌을 때, 모든 행렬을 .. 2024. 5. 16. Algorithm design - 최적 이진 탐색 트리 최적 이진 탐색 트리이진 탐색 트리(BST)는 루트의 왼쪽 서브트리에 있는 원소의 키 값은 루트보다 작고, 루트의 오른쪽 서브트리에 있는 원소의 키 값은 루트보다 큰 이진 트리이다.최적 이진 탐색 트리 문제는 트리 내의 키와 각 키가 탐색될 확률이 주어져 있을 때 그 트리의 평균 탐색 비용, 즉, 평균 비교횟수를 계산하고 이를 최소화하는 탐색 트리를 구축하는 문제이다. 예를들어 키의 값이 A: 0.1 B: 0.3 C:0.6이면 아래와 같이 다양한 케이스의 트리에서 탐색비용을 계산해볼 수 있다.1번만 살펴보면 A를 탐색할때 0.1, C를 탐색할때 0.1+0.6, B를 탐색할때 0.1+0.6+0.3이 되어 3*0.1+2*0.6+1*0.3=1.8이 된다. 키 값 a_i ≤ a_i+1 ≤ … ≤ a_j 일 .. 2024. 5. 14. 알고리즘 설계 실습 - 삼각분할 문제정N각형 P는 P의 두 꼭지점 쌍들을 연결하는 선분 (모든 선분은 교차하지 않아야 함)으로 N-2개 의 삼각형으로 분할될 수 있습니다. 예를 들어, 정사각형은 두 개의 삼각형으로, 정오각형은 세 개의 삼각형으로, 정육각형은 네 개의 삼각형으로 분할될 수 있습니다. 이러한 삼각형들의 집합 T 를 P의 삼각 분할이라고 합니다.P의 삼각 분할의 집합 T 내의 두 삼각형 a와 b 사이의 거리는 a에서 b로 이동할 때 인접한 두 삼각형의 경계를 넘는 횟수로 정의됩니다. 이동하는 동안 언제든지 정N각형 P 내부에 머물러야 하며, P의 경계를 넘어서는 이동은 허용되지 않습니다. 우리는 정N각형의 삼각 분할 집합 T 내 모든 삼각형 쌍 사이의 거리의 최댓값 중에서 최소인 값을 찾는 프로그램을 작성해야 합니다.예를 .. 2024. 5. 8. Algorithm design - Matrix-chain Multiplication 연쇄 행렬곱셈i × j행렬과 j × k 행렬을 곱하기 위해서는 일반적으로 i × j × k 번 만큼의 기본적인 곱셈이 필요하다. 연쇄적으로 행렬을 곱할 때, 어떤 행렬곱셈을 먼저 수행하느냐에 따라서 필요한 기본적인 곱셈의 횟수가 달라지게 된다.예를들어 M1, M2, M3, M4이 각각 10x100, 100x5, 5x50, 50x20이라고 할때 아래와 같이 다양한 결과가 나올 수 있다. (1) M1x(M2x(M3xM4)) : 5x50x20+100x5x20+10x100x20 = 35,000(2) M1x((M2xM3)xM4) : 100x5x50+100x50x20+10x100x20 = 145,000(3) (M1xM2)x(M3xM4) : 10x100x5+5x50x20+10x5x20 = 11,000(4) ((M1x.. 2024. 5. 7. Algorithm design - DP / Levenshtein Distance Dynamic ProgrammingDynamic Programming은 동적 계획법이라는 뜻이지만 실제로 그렇게 동적이지는 않다. 오히려 기록해둔 과거 기록을 저장해두고 꺼내서 이용한다는 점에서 Tabular Method라는 이름이 어울린다.Divide-And-Conquer는 top-down approach로 나누어진 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합하다. 반면Dynamic programming은 bottom-up approach로 큰 문제를 작은 문제로 나눈 다는 점은 Divide-And-Conquer와 동일하나 작은 문제를 먼저 해결하고, 그 결과를 저장한 다음, 후에 그 결과가 필요할 때마다 다시 계산하는 것이 아니고 그 저장된 결과를 이용한다는 점이 다르다. 해답을 구축하.. 2024. 5. 2. 알고리즘 설계 실습 - Fibo_counter 문제피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 아래 소스 코드는 N번째 피보나치 수를 구하는 재귀함수이다.int fibonacci(int n) { if (n == 0) { print("0"); return 0; } else if (n == 1) { print("1"); return 1; } else return fibonacci(n‐1) + fibonacci(n‐2);}fibonacci(3)을 호출하면 다음과 같이 동작한다.- fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출- fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출- 두 번째 호출한 fi.. 2024. 5. 1. Algorithm Design - Huffman encoding / Encryption / RSA File compression시간보다는 공간을 절약하는 방법에 대해 연구된다. 대부분의 컴퓨터 화일에서 데이터가 중복되어 있다는 것에 착안된 개념이다. 파일 압축의 대상으로는 텍스트 파일 인코딩된 이미지의 래스터 파일 사운드나 다른 아날로그 신호의 디지털 표현 등이 있다. 현재는 허프만 인코딩이 거의 주를 이루지만 이 개념이 나오기까지 몇몇 다른 시도들이 존재했었다. 우선 run-length encoding(런-길이 인코딩)은 동일한 문자가 여러개 나올 경우 숫자와 문자쌍으로 화일을 압축하는 기법이다. 이진수로 표현되는 비트맵 이미지를 압축하는데 사용됐었다. 화일에서 가장 기본적인 중복은 같은 문자가 연속적으로 나타나는 것이다. 이를 다음과 같이 압축해내는 기법이다.AAAABBCCC → 4A2B3C.. 2024. 4. 18. 알고리즘 설계 실습 - KMP 문제 KMP 알고리즘을 구현하세요. 구현한 KMP 알고리즘으로 문자열 T에서 문자 열 P를 모두 찾고, 찾은 개수와 위치를 출력하세요. 첫째 줄에는 문자열 T가 주어집니다. 문자열 T의 길이 n은 1이상 100만 이하입니다. 둘째 줄에는 문자열 P가 주어집니다. 문자열 P의 길이 m은 1 이상 26 이하입니다. 문자열은 모두 알파벳 대문 자로만 이루어져 있습니다. (줄 바꿈 문자 \n을 포함하면 최대 문자열 길이가 2 추가됩니다.) 첫째 줄에는 문자열 T에서 문자열 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력하세요. 둘째 줄에는 문자열 T에서 문자열 P가 나타나는 위치를 차례대로 공백으로 구분하여 출력하세요. 예를 들면, 문자열 T의 i～i+m-1번째 문자와 P의 1～m번째 문자가 차례로 일.. 2024. 4. 17. Algorithm Design - 라빈-카프 / 패턴 매칭 Rabin-Karp 라빈-카프 알고리즘은 스트링을 숫자값으로 바꾼 다음 해시 값을 계산하여 매칭하는 알고리즘이다. 최악의 시간 복잡도는 O(MN)이지만 평균적으로는 선형에 가까운 빠른 속도를 가지는 알고리즘이다. 첫 번째 M 자리의 나머지를 구한 다음부터는 한 자리씩만 추가하면서 간단한 계산으로 나머지를 구할 수 있으므로 빠른 시간에 스트링 탐색을 수행한다. 해시 값이 다르다면 두 문자열이 다르다는 것이 보장된다. 그러나 해시 값이 같다고 해서 두 문자열이 같다는 것이 보장되지는 않기 때문에 해시값이 같은 경우 문자열을 비교하는 과정을 거친다. 찾고자하는 패턴은 한번 연산을 해두면 해시값이 정해져있지만 한칸씩 넘어가며 텍스트와 비교를 할때 텍스트에서 비교하고자 하는 부분의 해시값을 매번 다시 연산하는 것.. 2024. 4. 17. 이전 1 2 3 4 5 다음 728x90
