[백준 7561번] 크래머의 공식 (C++)
·
📚알고리즘/백준
https://www.acmicpc.net/problem/75613 X 3 동차선형연립방정식을 크래머의 공식을 이용하여 풀어내라는 문제다.선형대수학에 나오는 개념이며, Determinant(행렬식)의 개념을 알고 있으면 문제를 이해하기 쉽다.크래머 공식을 단순 구현하는 문제이긴 부동소수점을 조절해주어야 하고, 선형대수학에 나오는 개념을 미리 알고 있는 사람이 아니면 생각보다 코드를 작성하기 시작하는데 오래걸릴거 같다. 각 원소의 범위가 -1000 ~ 1000이므로 행렬식을 계산하는 도중에 int형 범위를 넘어갈 수 있음에 유의하자.#include #define ep 0.0005#define lint long longusing namespace std;lint n, detA, detA1, detA2, de..
[백준 12020번] LU 분해 (C++)
·
📚알고리즘/백준
https://www.acmicpc.net/problem/12020 요즘 선형대수학을 공부하고 있는데 백준에 예제가 잘 나와있어서 연습하기 참 좋다.어떤 행렬 A를 하삼각행렬과 상삼각행렬로 분해하는 과정이다.Ax = b 라는 선형연립방정식을 풀 때 단순히 가우스 소거법을 이용하여 풀어도 되지만, LU분해를 사용하면 훨씬 효율적으로 계산할 수 있다. 가우스 소거법을 활용한 선형연립방정식의 Time complexity: N³LU분해를 활용한 선형연립방정식의 Time complexity: N²  LU분해를 하는 과정에서 가우스 소거법이 필요해서 최초의 분해를 하는 데에는 N³의 시간복잡도를 필요로 하지만, 분해는 한번 해 놓으면 다시 할 필요가 없다는 점에서 이득을 볼 수 있다. 한마디로 Ax = b에서 b가..
[백준 22940번] 선형 연립 방정식 (C++)
·
📚알고리즘/백준
https://www.acmicpc.net/problem/22940 22940번: 선형 연립 방정식 하나 이상의 미지수에 대해 최고차항의 차수가 1을 넘지 않는 방정식을 선형 방정식이라 한다. 족, 다음과 같은 식을 의미한다. A1x1 + A2x2 + ... + Anxn = B 선형 연립 방정식이란 유한개의 선형 방 www.acmicpc.net 다른 풀이가 당연히 있겠지만, 컴퓨터공학을 전공한다면 Gauss - Jordan 소거법을 사용할 듯 하다. 선형대수학에서 배운 기본 행 연산을 통해 계수행렬을 RREF(Reduced Row Echelon Form)으로 만들는 과정을 그대로 구현하면 된다. 이 문제에서는 주어지는 행렬이 최대 6 by 6이고, 계수들도 모두 10까지의 자연수로만 이루어져 있는데 과정..
루오
'선형대수학' 태그의 글 목록