synodic의 삭망월

연쇄 행렬 곱셈 일반적으로, i * j 행렬과 j * k 행렬을 곱하면 원소단위 곱셈의 실행 횟수는 다음과 같다. i * j * k 번 실행 횟수가 행렬의 크기에 따라 결정된다. 따라서 최적의 순서도 행렬의 크기에만 의존한다. n개의 행렬 \({A}_{1}\) ... \({A}_{n}\))을 곱하는 모든 순서의 가지 수를 \({T}_{n}\)이라고 하자. A1을 마지막으로 곱하는 순서의 집합의 가지수는 \({T}_{n-1}\)이다. (A_1...A_n까지 곱하는 서로 다른 순서의 가지수) An을 마지막으로 곱하는 순서의 가지 수 또한\({T}_{n-1}\)일 것이다. 따라서 다음과 같은 부등식이 나온다. $$T_n >= T_{n-1} +T_{n-1} = 2 * T_{n-1}$$ 두 개의 행렬을 곱하는 법..

이해 수학 문제다. Josephus problem은 wiki에도 잘 나와있다. https://en.wikipedia.org/wiki/Josephus_problem Josephus problem - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. A drawing for the Josephus problem en.wikipedia.org 1에서 인..

이해 입력 D의 범위 안에서 최대 점수('현재 점수 * 다음 점수'의 합)을 구한다. 입력받은 2차원 배열과 같은 크기의 dp[i][j]를 만들자. dp[i][j]가 i행 j열 까지의 최대 점수라고 할 때, dp[i][j]는 i행 j열로 가기 전 단계 x행 y열에서, 'x행 y열의 점수 * i행 j열의 점수' 연산을 더하는 값과, 더하지 않는 값 중의 최댓값이다. 따라서 dp[i][j] = max(dp[i][j], dp[x][y] + cur*next); 라는 점화식을 떠올리는 것은 쉽다. 틀렸습니다 70%쯔음에서 '틀렸습니다'를 받았다면 INF(dp배열 또는 답의 초기값의 최저)의 값을 너무 낮게 설정했을 수 있다. 메모리 초과가 났다면 입력의 2차원 배열을 int arr[100001][100001]로 ..

https://www.acmicpc.net/problem/17398 17398번: 통신망 분할 첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q www.acmicpc.net 아이디어 union find인데 제거할 때 나오는 비용을 세는 대신, 전부 분리한 다음 분리하지 않을 간선만 이은 채로 union을 전부 돌면 된다. 전부 서로소 집합인 상태에서 끊지 않을 간선을 제외한 노드들(예제에서는 1,2)을 union할때와 이후 답을 찾기위한 union은 같으나 후자에서는 부모노드 확인과정을 거친 후 비용을 곱해서 저장해야 한다. 아이디..

문제 이해 평범한 플로이드 와샬 문제다. map[i][j] = min(map[i][j], map[i][k] + map[k][j]); 정말 평범한 플로이드 와샬 문제를 풀고싶다면: https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 여기서 아이템의 개수를 저장할 배열을 추가로 만든다. 그리고 예은이가 갈 수 있는 범위 안에서 아이템의 개수를 전부 더해주고, max함수로 매번 갱신하면 된다. 다시 말해서, 예은이가 도달할 지역 n개를 전부 체크한다. ..

아이디어 n의 입력을 받고 n*2 만큼의 팀원을 둘씩 짝지으면 된다. 그렇다면 오름차순으로 정렬하고 제일 작은 수 + 제일 큰 수 식으로 팀을 맺으면 최소의 평균값이 나올 것이다. https://www.acmicpc.net/problem/20044 20044번: Project Teams 입력은 표준입력을 사용한다. 입력의 첫 번째 행에는 팀 수를 나타내는 양의 정수 n(1 ≤ n ≤ 5,000)이 주어진다. 그 다음 행에 학생 si 의 코딩 역량 w(si)를 나타내는 2n개의 양의 정수가 공백으로 www.acmicpc.net 코드 #include #include #include using namespace std; using ll = long long; const int INF = 1e8; int mai..

그리디 알고리즘 종료시간 기준 정렬 코드 #include #include #include using namespace std; int n, m, a, b, cnt; int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n; vector v; for(int i = 0; i > a >> b; v.push_back({ b, a }); // 종료시간 기준 정렬 } sort(v.begin(), v.end()); a = 0, cnt = 0; for(int i = 0; i < v.size(); i++) { if(v[i].second < a) continue; a = v[i].first; cnt++; // 최..

string 이나 char 사용법을 경험해봤으면 해서 이 문제를 알고리즘 학습 동아리 문제 셋에 추가해봤다. string은 헤더파일에 존재하므로 추가가 필수이다. 코드 #include #include #include using namespace std; using ll = long long; const int MAX = 1000; int N; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N; // string을 쓴다면 사실상 의미 없음 string s; cin >> s; int ans = 0; for (int i = 0; i < s.size(); i++) { ans += s[i] -'0'; } cout

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 이해 이 문제를 이해하기 위해서 종이에 그림을 그려 보라. 단번에 어떤 자료구조가 필요할지 떠오르지 않아도 괜찮다. 앞에서 K번째 원소까지 탐색하고, 원소를 지우고, 탐색하고, 지우고... 를 반복하면 되겠구나! 하고 떠오르면 문제 이해가 끝났다. Queue 이제 큐를 사용해보자 K번째 원소까지 어떻게 셀까? 1. 큐의 맨 앞 원소를 뒤에 붙이고(push), 그 원소를 지운다(pop) 이 과정을 K번동안 반복한다. 그럼 초기에 앞에서 K번째에 있던 원소가 맨 앞으로 왔을 것이다. 2..

dp 사용 코드 #include #include #include #include using namespace std; using ll = long long; int n, sum, arr[100001], dp[100001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; dp[0] = -1000; sum=-1000; for (int i = 0; i > arr[i]; dp[i] = max(arr[i], dp[i - 1] + arr[i]); sum = max(sum, dp[i]); } cout