https://www.acmicpc.net/problem/12020 요즘 선형대수학을 공부하고 있는데 백준에 예제가 잘 나와있어서 연습하기 참 좋다.어떤 행렬 A를 하삼각행렬과 상삼각행렬로 분해하는 과정이다.Ax = b 라는 선형연립방정식을 풀 때 단순히 가우스 소거법을 이용하여 풀어도 되지만, LU분해를 사용하면 훨씬 효율적으로 계산할 수 있다. 가우스 소거법을 활용한 선형연립방정식의 Time complexity: N³LU분해를 활용한 선형연립방정식의 Time complexity: N²  LU분해를 하는 과정에서 가우스 소거법이 필요해서 최초의 분해를 하는 데에는 N³의 시간복잡도를 필요로 하지만, 분해는 한번 해 놓으면 다시 할 필요가 없다는 점에서 이득을 볼 수 있다. 한마디로 Ax = b에서 b가..

https://www.acmicpc.net/problem/27977 27977번: 킥보드로 등교하기 첫 번째 줄에 학교까지의 거리, 킥보드 충전소의 개수, 최대 충전소 방문 횟수를 나타내는 세 정수 $L, N, K$가 공백으로 구분되어 주어진다. 두 번째 줄에 $i$번째 충전소의 위치를 나타내는 $N$개 www.acmicpc.net #include using namespace std; int l,n,k,diff = -1; int arr[100002]; int main() { cin >> l >> n >> k; arr[0] = 0, arr[n+1] = l; for(int i = 1; i > arr[i]; } for(int i = 1; i

https://www.acmicpc.net/problem/5095 5095번: Matrix Powers The input consists of a number of problems. Each problem starts with a line holding three numbers (N, M, and P) separated by single spaces. 1 ≤ N ≤ 100 is the size (N by N) of the matrix to be processed. 1 ≤ M ≤ 32000 is the modulo base and 1 ≤ www.acmicpc.net 10830 행렬제곱 문제와 똑같은 문제다. 알고리즘 포스팅에서 분할정복을 주제로 한 포스팅이 있었는데, 마지막 부분에 분할정복 연습문제로 분할..

https://www.acmicpc.net/problem/22953 22953번: 도도의 음식 준비 첫째 줄에 요리사의 수 $N$ ($1 \le N \le 10$), 만들어야 할 음식의 개수 $K$ ($1 \le K \le 1\,000\,000$), 격려해줄 수 있는 횟수 $C$ ($0 \le C \le 5$)가 주어진다. 둘째 줄에 길이가 $N$인 정수 수열 $A$가 주어 www.acmicpc.net 다른 골드4의 매개변수 탐색보다 많이 까다로운 문제다. 값의 범위가 작기 때문에 브루트 포스를 의심하는 것이 첫 번째 단계다. 도도가 요리사에게 격려를 해줄 수 있는 모든 경우의 수를 나이브하게 따져도 10의 6승이고, 각각의 경우에 매개변수 탐색은 log2(10^6 * 10^6) 이므로 시간적으로 10의..

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까지의 자연수로만 이루어져 있는데 과정..

https://www.acmicpc.net/problem/27650 27650번: 마법박스 다음을 표준 출력 스트림(stdout)으로 한 줄에 출력하여, $i$ 이하의 $2$ 이상의 양의 정수가 마법박스에 모두 들어있는지 질의할 수 있다. 질의에 대한 답변은 모두 들어있다면 $1$, 그렇지 않다면 $0 www.acmicpc.net 인터렉티브 문제로 채점 방식이 특이하다. "?"를 출력하여 문제에게 질문해야하고, 문제가 답을 주면 범위를 줄여서 물어보고... 그러다가 "!"로 답을 출력해야한다. 이 문제에서는 질문할 수 있는 횟수가 20번이므로 스무고개라고 생각하면 된다. 처음으로 이런 유형을 풀어봤고 문제랑 대화하는 느낌이 들어서 재밌었다. 마법박스에 들어있는 수 중에서 가장 작은 정수를 찾으면 되는데,..