![]()
3.4. LU 분해의 순서 앞 절의 설명한 LU 분해의 순서를 형식적으로 풀어낸 과정 분해를 했더라도 L, U를 각각 행렬로서 다루면 메모리를 비효율적으로 사용하게 된다. 비어 있는 장소나 1로 정해져 있는 장소 등은 기록할 필요가 없다. 3.5. LU 분해 정방행렬 A에 대하여 A = LU 상태로 분해되면 행렬식 det A는 바로 구해진다. 3.6. 일차방정식 LU 분해로 풀다 방향과 계획 푸는 방법 연산량 변수소거법 가우스 요르단 소거법(Ax = y) LU 분해 Lz = y로 풀다 Ux = z를 풀다 나눗셈 n n n 0 n 곱셈 n^3 / 3 n^3 / 2 n^3 / 3 n^2 / 2 n^2 / 2 뺄셈 n^3 / 3 n^3 / 2 n^3 / 3 n^2 / 2 n^2 / 2 같은 A에서 여러 가지 ..
![]()
3.3.1. 정의 주어진 행렬 A에 대해 A를 하삼각행렬 L과 상삼각행렬 U의곱으로 나타내는 것 분해해서 무엇이 좋은가 처음부터 그런 분해가 되는가 분해된다고 해도 계산량은 어떤가 3.3.2 분해하면 뭐가 좋나요? 행렬식을 구하거나 일차방정식을 푸는 것이 간단해진다. 3.3.3. 처음에 분해가 가능한가요? 1행, 1열, 2행, 2열 ... 순서로 앞이 정해지면 뒤는 줄줄이 결정된다. 순서만 잘 따지면 분해가 된다고 이해할 수 있다. 대부분의 경우 A = LU 로 분해된다. 3.3.4. LU 분해의 계산량은? 연산 횟수 정리 출처: 히라오카 카즈유키, 호리 겐, 『프로그래머를 위한 선형대수』, 이창신, 길벗, 2017.
3.1.1. 수치 계산을 얕보지 마라 주의할 사항 수치의 정도는 유한하다. 계산량 및 메모리 소비량을 줄여야 한다. 3.1.2. 이 책의 프로그램에 대해 소스코드를 내려받을 수 있다. 학습용으로 제공되는 것이고 본방용은 아니다. 3.2. 준비 운동 벡터까지의 합 for 루프를 돌려 성분마다 조작 행렬과 벡터의 곱 이중 루프 앞 행렬의 열 수와 뒷 행렬의 행 수가 같은지 확인 각 대응하는 성분을 곱하여 합계 구하기 행렬끼리의 곱은 삼중 루프가 된다 출처: 히라오카 카즈유키, 호리 겐, 『프로그래머를 위한 선형대수』, 이창신, 길벗, 2017.
문제 링크 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 소스 코드 import sys input = sys.stdin.readline from collections import deque for _ in range(int(input())): a,b = map(int,input().split()) q = deque() q.append((a,"")) # 변경 전,경로 visit = [False] * 10000 # 방문 리스트 초기화..
문제 링크 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 소스 코드 import sys input = sys.stdin.readline n,m = map(int,input().rstrip().split()) nums = list(map(int,input().rstrip().split())) for i in range(1,n): # 누적 합 구하기 nums[i] = nums[i-1] + nums[i] nums.insert..
문제 링크 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 소스 코드 import sys input = sys.stdin.readline n = int(input().rstrip()) graph = [] for i in range(n): graph.append(list(map(int,input().rstrip().split()))) answer = {-1:0, 0:0, 1:0} # 카운트를 저장할 딕셔너리 def dfs(x,y,n):..
