본문 바로가기

Algorithm

 (30)
[Algorithm] 정렬 알고리즘 : 외부 정렬 이전에 버블, 선택, 삽입, 합병 등 여러 정렬알고리즘에 대해서 많은 게시글을 올렸었다. 정렬알고리즘의 종류로는 내부정렬, 외부정렬이 있다. 내부정렬 입력의 크기가 주기억 장치의 공간보다 크지 않는 경우에 수행되는 정렬이다. 버블, 선택, 삽입, 합병, 쉘, 힙, 합병, 퀵정렬 등 외부정렬 입력의 크기가 주기억 장치 공간보다 큰 경우, 보조기억 장치에 데이터를 저장하여 정렬을 하고자 하는 경우에 사용된다. 보조 기억 장치에 있는 입력을 여러 번에 나누어 주기억 장치에 읽어들인 후, 정렬하여 보조 기억 장치에 다시 저장하는 과정을 반복한다. 예를 들면, 주기억 장치의 용량이 1GB이고, 입력 크기가 100GB라면, 어떤 내부 정렬 알고리즘으로도 직접 정렬할 수 없어서 외부 정렬알고리즘을 사용해야한다. 1️..
[Algorithm] 동전 거스름돈 : 동적 계획 알고리즘 동전 거스름돈 문제는, 그리디 알고리즘에 대한 개념을 소개하는 포스팅에서 간단하게 설명했었다. 대부분의 경우, 그리디 알고리즘으로 해결할 수 있으나 해결 못하는 경우도 있다. 동적 계획 알고리즘은 모든 동전 거스름돈 문제에 대하여 항상 최적해를 갖는다. 💡동적계획 알고리즘으로 접근 1️⃣ 부분 문제 찾기 이전 포스팅인 배낭 문제처럼, 동전 = 물건, 거스름돈 = 배낭의 무게 라고하면 배낭문제와 유사하게 정의된다. 동전을 1원씩 증가시켜 문제를 해결해 보자 -> 이 부분문제들의 해를 1차원 배열 C에 저장하자 1원을 거슬러 받을 때 사용되는 최소의 동전 수 C[1] 2원을 거슬러 받을 때 사용되는 최소의 동전 수 -> C[2] 3원을 거슬러 받을 때 사용되는 최소의 동전 수 -> C[3] ... n원을 거..
[Algorithm] 배낭(Knapsack) 문제 : 동적계획 알고리즘 앞서, 그리디 알고리즘을 통해 해결했던 배낭문제를 동적계획 알고리즘을 이용해서 해결해보자! 💡배낭문제의 부분문제를 찾아내기 4가지 요소 : 물건, 물건의 무게, 물건의 가치, 배낭의 용량 이중에서 물건과 물건의 무게는 부분문제를 정의하는데 고려 이유 : 배낭이 비어있는 상태에서 시작하여 물건을 하나씩 배낭에 담는 것과 안 담는 것을 현재 배낭에 들어있는 물건의 가치의 합에 근거하여 결정해야하기 때문 또한 물건을 배낭에 담으려고 할 경우, 배낭 용량의 초과 여부를 검사해야한다. 따라서, 부분문제를 아래와 같이 정의! K[i,w] = 물건 1~i 까지 (임시) 배낭의 용량이 w일 때의 최대 가치 i= 1~n, w= 1~C n : 물건의 개수, C: 배낭의 용량 여기서 C의 값이 매우 크면, 알고리즘의 수행시..
[Algorithm] 편집 거리 문제 : 동적계획알고리즘 ❓문제 삽입, 삭제, 대체 연산을 사용하여 문자열 S를 문자열 T로 변환 시키는데 필요한 최소의 편집 연산 횟수, 즉 편집거리를 찾아라! 동적계획 알고리즘 Remind - 작은문제에 대한 모든 가능성을 고려해서 다음 크기의 문제에 대한 최적해를 결정 -> 항상 최적해를 구할 수 있음 - 해당 문제에서, 최적성의 원리는 만족됨! 💡생각해야할 것 문자열을 바꾸는데, 어떤 연산을 어느 문자에 수행하는가에 따라 편집 연산 횟수가 달라진다. 💡동적 계획 알고리즘으로 해결하려면 부분 문제들을 어떻게 표현? 만약 접두부에 대한 편집거리를 알고있다면 (최적성의 원리 만족), 각 스트링의 나머지 부분에 대해서 편집거리를 찾음으로써 주어진 입력에 대한 편집거리를 구할 수 있다. 부분 문제 정의 E[i,j] : S의 접두부..
[Algorithm] 연속된 행렬 곱셈 오늘의 포스팅은, 동적계획 알고리즘을 이용한 연속된 행렬곱셈이다. 문제 n개의 연속된 행렬곱셈 M = M1M2M3...Mn에서 스칼라 곱셈 횟수가 최소가 되는 곱셈 순서를 찾는 알고리즘 💡행렬곱셈의 원칙 행렬곱셈 C = AB 의 기본적인 요건은 A의 열의 개수와 B의 행의 개수가 같음 A(p x r) x B(r x q) = C(p x q) 스칼라 곱셈은 모두 ( p x r x q ) 번 무작위 기법 모든 행렬 곱셈 순서를 구하여, 각각의 스칼라 곱셈 횟수를 계산하여 비교 Xn = (n개의 행렬을 곱하는 가능한 모든 곱셈 순서의 수) 라면, Xn은 다음의 세경우의 수를 합한 것 M1을 가장 나중에 곱하는 경우의 수 = M1(M2M3...Mn)의 순서로 곱 = M2M3...Mn을 곱하는 경우의 수 = X(n..

티스토리툴바