algorithm

https://www.acmicpc.net/problem/30805수열 A와 수열 B에서 공통으로 가장 큰 수를 찾고 그 수를 ans벡터에 넣어주는 식으로 최대 공통 수열을 찾았다.여기서 수열 A와 B의 공통으로 가장 큰 수를 찾았으면 각 수열에서 공통으로 가장 큰 수의 인덱스보다 작은 인덱스 숫자들은 최대 공통 부분 수열의 원소가 될 수 없으므로 pop해준다.위의 방식을 한쪽 수열의 벡터의 크기가 0이 될때까지 반복한다. 그럼 최종 ans벡터 수열이 사전 순 최대 공통 부분 수열이 된다. #include #include #include #define endl "\n"using namespace std;int main() { int n,m,num; vector a; vector b; cin >> n; f..

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