728x90 백준플래/기타4 백준 22940, 선형 연립 방정식 개요 문제 링크 플래 5, 선형대수학 6개 이하의 선형 연립방정식 해결하기 접근 기본적인 선형대수학 문제, 어떤 N개의 선형조합은 다음과 같이 행렬과 벡터의 곱으로 나타낼 수 있다. $a_{11}x_1+a_{12}x_2+\cdots +a_{1n}x_n=b_1$ $a_{21}x_1+a_{22}x_2+\cdots +a_{2n}x_n=b_2$ $\cdots $ $a_{n1}x_1+a_{n2}x_2+\cdots +a_{nn}x_n=b_n$ $=> AX=B$ $A(a_{ij})_{n\times n}\quad X(x_i)_{n\times 1}\quad B(b_i)_{n\times 1}$ 따라서 AX=B인 상황에서 X를 구하기 위해 우리는 $A^{-1}B$ 를 해주면 된다. 사실상 행렬의 존재이유이자 선형대수학의 핵.. 2023. 3. 14. 백준 3847, Comparing answers 개요 문제 링크 플래 2, 선형대수학, 무작위화 두 도시 사이의 길의 개수를 나타낸 행렬이 있을 때, 두 개의 길을 이용해 이동하는 경로 행렬을 잘 구했는지 검증하기 접근 Freivald's algorithm을 사용하는 세 문제 중 하나. 생소한 개념 때문에 티어가 올라갔는데 내용을 알고 있다면 크게 어렵지 않다. 우선 분할정복을 이용한 거듭제곱에서도 종종 다루는 개념인데, 경로의 개수를 나타낸 인접행렬의 k제곱은 그 경로를 k번 이용한 경로의 개수이다. 즉 여기서는 A×A=B임을 검증하면 되는 셈이다. 일반적인 행렬곱이 O(N^3)에 해결되므로 문제는 1e9번의 연산을 test개수만큼 해줘야 하는데 테스트가 1개라도 대부분 터질거다. 이때 O(kN^2)만에 할 수 있는 프리발즈 알고리즘을 이용하.. 2023. 3. 13. 백준 10875, 뱀 개요 문제 링크 플래 5, 구현, 시뮬레이션 자신의 몸이나 지도의 외벽에 닿으면 사망하는 뱀의 최대 생존시간 구하기 접근 까다로운 구현 문제. 문제를 조금만 잡고 있다보면 2차원 배열에 1을 채워서는 길이가 1억이기 때문에 절대 할 수 없다는 것을 알게된다. 그러면 선분 1000개에 대해서 교차하는 경우에 대해 생각해야 하는데 이 과정이 매우 까다롭다. 문제를 더 까다롭게 만드는 부분은 두 가지 정도가 있는데, 교점을 찾고, 교점까지의 이동시간을 찾아줘야 한다는 것이다. 일반적인 선분교차를 이용하기 어려운 이유는 이 교점과 시간 때문이다. 교점을 찾는 과정을 지금까지 지나온 모든 선분에 진행해줘야 한다. 만약 교차하는 점을 찾고 break를 걸어버리면 그 점이 끝점이 아닐 수 있다. 축에 평행한 선분이 .. 2023. 3. 3. 백준 1055, 끝이없음 개요 문제 링크 플래 3, 구현, 재귀 문자열 S내의 $를 문자열 A로 대체하는 과정을 n번 진행한 뒤의 부분문자열 출력하기 접근 재귀로 두들겨 패는 문제. 우선 문자열을 직접 구하는 건 절대 안된다. 왜냐, 우선 첫 문자열을 A라하고 n번째 문자열의 길이를 구해보자. A = x S = $*50 S(1) = x*50 S(2) = x*50*50 S(1e9) = x*50^1e9 50의 10억승 만큼의 길이의 문자열을 만들 수 있을까? 절대 안된다. 그럼 어떻게 풀까 하니 출력할 문자열의 길이가 100밖에 안된다. 각 위치에 맞는 문자열을 100번 구해주라는 의미인데 이게 생각하기가 매우 까다롭다. S.split('$') = B라고 해보자. // k = B의 크기 S0 = A S1 = B[0] .. 2023. 2. 27. 다음 728x90