13. 다이나믹 프로그래밍-3(LCS 문제)
LCS(최장공통부문자열) 문제부문자열은 문자열에서 0개 이상의 문자를 제외하고 남은 문자열을 의미YANG에서 A를 제외한 YNG같이… 하지만 AGY는 안된다! 공통 문자열은 두개의 문자열의 부문자열이 동일한 것을 말한다!이 문제는 가장 긴 길이의 공통부문자열을 찾는 문제이다! Xn 을 x1, x2, x3, … xn 즉 n개의 글자를 갖는 문자열이라고 하고,
Category: Algorithm
12. 다이나믹 프로그래밍-2(행렬 곱셈 문제)
행렬 곱셈 문제 n개의 행렬 곱셈을 최소 비용으로 푸는 문제 만약 무지성으로 pXq , qXr 인 두 행렬을 3개 for루프로 풀면, O(pqr)번 연산이 필요하다.이때 여러개의 행렬이 주어졌을 때는, 행렬을 어느 순서로 곱하느냐에 따라 기본 연산 횟수가 달라진다.a = 1x2, b=2x3, c=3x4 일때, (ab)c와 a(b
11. 다이나믹 프로그래밍-1
다이나믹 프로그래밍문제를 여러 작은 문제로 나누어 재귀적으로 해결하는 방법. divde and conquer와 차이점은? 큰 문제의 답이 작은 문제의 답들의 식으로 표현되지만,그 답을 얻을 때 재귀적으로 얻는게 아니라 미리 계산하여 기록해 놓은 값을 재귀 식에 따라 계산! 즉 원래 문제의 답을 작은 문제들의 재귀 식으로 표현하는 것이 핵심!!!!점화
10. Merge 정렬 알고리즘
Merge 정렬 알고리즘퀵 소트가 피벗을 어떻게 선택하냐에 따라 속도가 달라지는 단점을 상쇄하는 알고리즘 배열은 반으로 나눠 재귀적으로 정렬하고 정렬된 두 배열을 원소 하나씩 비교해서 병합하는 방식.주어진 배열만큼 새로운 배열을 사용해야 하기 때문에 not in-place 알고리즘이다. 먼저 중간 인덱스를 찾는다. 중간 인덱스를 기준으로 나눠서 두 배
9. Quick 정렬 알고리즘
퀵 정렬 알고리즘이론적으로는 빠르지 않지만(O(n^2)), 실제로는 가장 빠른 정렬 알고리즘quick selection과 비슷한 원리임. not in-place quick sort algorithm 어떤 list A를 퀵 정렬 하려면… 피벗을 A[0]으로 잡고, S,M,L 세가지 배열을 선언함 A에 있는 모든 수들이 피벗보다 크면 L, 작으면 S, 같으
8. 기본 정렬 알고리즘
파이썬에서 제공하는 정렬 123A = [3,1,2,-5]A.sort() #[-5,1,2,3]A.sort(reverse = True) #[3,2,1,-5] 정렬 알고리즘의 두 가지 특성 stable vs unstable만약 [2,5,2,7]을 오름차 정렬했을 때 ,[2,2,5,7]로 정렬이 될 텐데, 이 두 개의 2가 입력 순으로 정렬되면 stable하
7.피보나치
피보나치 수 피보나치 수열이란 F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)로 정의되는 수열! 구현 방법 피보나치수 정의를 그대로 재귀함수로 구현 간단하지만..O(g^n) 지수 시간이 걸림..(g는 황금비율 1.1618…) 이차원 배열을 재귀적으로 곱하기 (1 1)(F(n-1)) (1 0
6.Median of Medians 알고리즘
MoM(Median of Medians) 알고리즘퀵셀렉트는 세가지 영역으로 나누는데, 피벗보다 큰 쪽으로 너무 몰리면 수행시간이 길어졌었다. MoM 알고리즘은 피벗을 적절하게 고르는 알고리즘이다.피벗보다 작은 값의 집합 A, 피벗보다 큰 집합 B 둘 다 n/c보다 작도록 피벗을 설정하는 것이다!! 이런 과정으로 피벗을 고른다고 하면, 재귀 과정에서
5.독특한탐색
특수한 선택 문제다음과 같은 요구 조건을 가지느 문제들은 선택(Selection)문제라고 보면 된다. 입력 : n개의 값과 k(1<=k<=n) 값 출력 : k번째로 작은 입력 값 목표 : 비교 횟수 최소화 상한(upper bound) : 어떤 결과를 찾아내는데 항상 임의 횟수의 연산이면 무조건 찾아낼 수 있다.하한(lower
4.일반적인 탐색
일반적인 선택 문제n개의 값중 k 번째 작은 수 찾기 - QuickSelction 배열 중 임의의 수 p를 고른다.(이 p는 pivot) p보다 작은 값을 A에 따로 모으고, p보다 큰 값을 B에 따로 모으고, p와 같은 값을 M에 따로 모은다. 만약 A의 원소가 k보다 작으면 A의 k번째 작은 값이 전체 데이터의 k번째 작은 값이다. 이제 A에서 k보다
3.재귀 알고리즘
재귀 알고리즘재귀 알고리즘 = 알고리즘 내부에서 한번 이상 자신의 함수를 호출sum(n) = 1+2+..+nsum(n) = sum(n-1)+n 123def sum(n): if n==1 : return 1 return sum(n-1) + n 수행시간T(n) = sum(n)의 수행시간이라 할 때T(n) =
2.분할정복법
분할정복법큰 문제를 작은 문제로 분할해 재귀적으로 해결 a와 n 입력받아 a^n 값 구하는 power1(a,n)을 분할 정복법으로 해보자. power1(a, n) = power1(a, n-1)*a 이다. 123def power1(a, n): if n==1: return a return a*power1(a, n-1) power1의 걸리
1.이진탐색
이진탐색오름차순으로 정렬된 n개의 숫자가 저장된 배열 A에서 어떤 값 x가 배열에 있는지 없는지 O(log n) 비교에 알 수 있는 탐색법. 현재 탐색 범위가 A[i]…A[j]라면 가운데값(A[(i+j)/2]) 비교에 알 수 있는 탐색법. 한 번의 비교로 탐색 범위가 반씩 줄어들어 (log n +1)번 이하의 비교로 x 존재 여부 판별. 주어진