[Linear Algebra] #36~38. 행렬식의 여러가지 성질 · 효율적 계산 · 행렬식의 곱

다이나믹 프로그래밍 적용 문제 (4) 최장 공통 부분순서 LCS 문제 설명 부분순서와 공통 부분순서의 예시는 다음과 같다. 는 문자열 의 부분순서. 는 문자열 와 의 공통 부분순서. 최장 공통 부분순서(Longest Common Subsequence)란 공통 부분순서들 중 가장 긴 것을 말한다. 예를 들어, 다음 두 문자열의 LCS를 구하면 다음과 같다. h e r o i c a l l y s c h o l a r l y 결과 문자열 : holly, LCS : 5 주어지는 두 문자열의 LCS를 구하라. 점화식 LCS(i, j) : 문자열 X[i] = "x1,x2, … ,xi" 과 Y[j] = "y1,y2, … ,yj" 의 LCS 길이 LCS(i, j) = { 0 ( if i = 0 or j = 0 ) L..

[Linear Algebra] #33~35. 행렬식과 여러가지 성질들

[Linear Algebra] #30~32. LU분해② · LU분해③ · LU분해④

[Linear Algebra] #28~29-1. 해집합의 성질③ · LU분해① · 대각 행렬의 거듭제곱

다이나믹 프로그래밍 적용 문제 (3) 행렬 곱셈 순서 문제 설명 행렬 A1, A2, A3, . . . , An을 곱하는 수를 최소로 하는 최적의 곱셈 순서를 구하라. 예로, 행렬 A(2 × 3), B(3 × 5), C(5 × 2)가 있을 때 곱할 수 있는 경우의 수는 다음과 같다. (AB)C = 2 × 3 × 5 + 2 × 5 × 2 = 50 A(BC) = 3 × 5 × 2 + 2 × 3 × 2 = 42 두 경우의 수에서 최솟값인 42에 해당하는 연산이 최소의 곱셈 횟수 42와 최적의 곱셈 순서 A(BC) 가 된다. 마지막 행렬 곱셈이 수행되는 상황을 다음과 같이 정리할 수 있으며, 경우의 수는 총 n - 1이다. 점화식 Ak의 크기 : pk-1 * pk m[i, j] : 행렬 Ai, …, Aj의 곱을 ..

다이나믹 프로그래밍 적용 문제 (2) 조약돌 놓기 문제 설명 • 3×N 테이블의 각 칸에 양 또는 음의 정수가 기록되어 있다 • 조약돌을 놓는 방법 (제약조건) - 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다 - 각 열에는 적어도 하나 이상의 조약돌을 놓는다 • 목표: 돌이 놓인 자리에 있는 수의 합을 최대가 되도록 조약돌을 놓는다 5 2 -1 3 -1 8 -5 0 2 3 12 7 • 임의의 열을 채울 수 있는 패턴은 모두 4가지다. 패턴 위치 P1 ● P2 ● P3 ● P4 ● ● • 서로 양립할 수 있는 패턴은 다음과 같다. 패턴 양립 가능한 패턴 P1 P2 P3 P2 P1 P3 P4 P3 P1 P2 P4 P2 예로, 어떤 i열의 패턴이 P3라면 전 열에 올 수 있는 패턴은 P1과 P..

다이나믹 프로그래밍 적용 문제 (1) 행렬 경로 문제 설명 양수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 우하단까지 이동한다. • 이동 방법 (제약조건) - 오른쪽이나 아래쪽으로만 이동할 수 있다 - 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다 • 목표: 좌상단에서 우하단까지 이동하되, 방문한 칸에 있는 점수들의 최대합을 구한다. 점화식 maxSum[i, j] = 위치 (i, j) 에 이르는 최대합 m[i, j] = 위치 (i, j) 에 해당하는 원본 값 0 ( if i = 0 or j=0 ) m[i, j] + max(maxSum[i - 1, j], maxSum[i, j - 1]) ( else ) 최대합 = maxSum(n, n) (i, j)의 위치에 있는 값은 위치의 위쪽 혹은 왼쪽 ..

다이나믹 프로그래밍 (Dynamic Programming) 기본 개념 최적화 문제를 해결하는 알고리즘 기술이다. 전체 문제의 최적 해가 부분 문제의 최적 해를 포함함을 활용한다. 이전에 계산한 값을 저장함으로써 동일 계산의 반복을 제거한다. 재귀적 구조 - 큰 문제 안에 닮음꼴의 작은 문제가 들어있는 구조다. - 관계중심으로 문제를 간명하게 파악 가능하다. 재귀적 해법 - 잘 쓰면 보약, 잘못 쓰면 맹독이다. - 심각한 중복 호출이 일어나는 경우가 있다. > 재귀적 해법이 바람직한 예 - 퀵 정렬, 병합 정렬 등의 정렬 알고리즘 - 계승(factorial) 구하기 - 그래프의 DFS > 재귀적 해법이 치명적인 예 - 피보나치수 구하기 - 행렬곱셈 최적순서 구하기 대표 문제 : 피보나치 수 아주 간단한 문..

[백준 C++] 알고리즘 10250. ACM 호텔 작성 코드 #include using namespace std; int main() { int H, W, N, o; scanf("%d", &o); for (int i = 0; i < o; i++) { int p = 1; int x, y = 1; scanf("%d %d %d", &H, &W, &N); while(p

[백준 C++] 알고리즘 2869. 달팽이는 올라가고 싶다. 작성 코드 #include using namespace std; int main() { int A, B, V; scanf("%d %d %d", &A, &B, &V); int sum = 1; int diff = (V - A) / (A - B); if ((V - A) % (A - B) == 0) sum += diff; else sum += diff + 1; printf("%d", sum); } 후기 A, B, V간의 규칙을 찾아내면 가볍게 풀어낼 수 있는 문제였습니다. 달팽이가 도착하기 까지 걸리는 일 수를 구하는 문제인데 문제 안에 숨어있는 규칙을 찾아내면 (A - V) / (A - B) 일이 나옵니다. 이 때 계산 값의 나머지가 0이면 sum에..

데이터 과학 분야에서 가장 기본이 되면서 중요한 파이썬 라이브러리인 NumPy 기본 강의를 제작 중입니다. 현재 기획한 강의안이 총 7 Section 중 마지막 Section 까지 약 90% 정도 녹화가 끝난 상태이며 예정 중인 강의명은 『 데이터 과학을 위한 파이썬 NumPy Basic 』 입니다. 파이썬 문법 중 가장 기본적인 변수, 리스트, 튜플, 반복문(예제 문제 풀이를 위한 조건문 까지)에 관한 동작 원리만 알고계신다면 프로그래밍 입문자분, 혹은 비전공자분들도 모두 원활히(아마도..) 학습하실 수 있으며 강의 진행에 있어서 꼭 필요한 약간의 선형대수학 이론을 다루었고 함수 적용 예시 위주로 강의를 진행합니다. 블로그에서 글로만 작성을 해오다가 온라인 영상 강의를 제작해본 것은 처음이라 혼자서 들..