synodic의 삭망월

탐색 종료의 기준을 잡는다. 내가 짠 코드는 어떤 행의 모든 열을 우선적으로 탐색하기 때문에 행이 n(체스판의 크기)가 되었을때 종료한다. 어떤 열 i, 어떤 행 j에 있다고 하자. 그 좌표를 기준으로 같은 열, 대각선에 위치하지 않으면 그 좌표를 체크해준다. 이 과정을 반복해서 종료조건에 도달했을 경우 가능한 체스판 경우를 +1해준다. #include #include #include using namespace std; #define MAX 40 int n; int cnt = 0; bool isused1[MAX]; // 같은 열 bool isused2[MAX]; // 우상 대각 bool isused3[MAX]; // 좌상 대각 /* i는 열, j는 행 */ void solve(int j) { if(j ..

3학년 이상에게 ㅊㅊ하는 글 물론 그 이하 학년도... 11049 행렬 곱셈 순서 골3 - 교재 3단원 수록 예제와 아주매우정말 똑같은 문제 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 2098 외판원 순회- 교재 3.6단원 이해는 쉽지만 구현이 까다롭다 책에도 구현은 안나옴 이 기회에 비트마스킹을 알아보는 것도... 7346 유전자 함수 - 교재 3.7단원 https://www.acmicpc.net/problem/7346 73..

연쇄 행렬 곱셈 일반적으로, 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}$$ 두 개의 행렬을 곱하는 법..

구현 srl로 8bit씩 shift하며 출력할 수 있다. fmt1: .asciz "4개의 영문자 입력 : " fmts: .asciz "%s" fmt2: .asciz "%dth 문자 = %c\n" .align 4 .global main main: save %sp, -96, %sp set fmt1, %o0 call printf nop set fmts, %o0 call scanf add %fp, -4, %o1 nop mov 4, %o1 ld [%fp-4], %o2 set fmt2, %o0 call printf nop ld [%fp-4], %o1 srl %o1, 8, %l0 mov 3, %o1 mov %l0, %o2 set fmt2, %o0 call printf nop ld [%fp-4], %o1 srl %o1..

해결 const keyword 붙이기 bool operator

이해 수학 문제다. 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..