정수론 (3) 썸네일형 리스트형 AtCoder Beginner Contest 293 후기 (ABC 293 4솔) 에디토리얼이 제공되어 있다. 저번처럼 ABCD를 풀고, E F번 문제를 보면서 정수론 문제 같다고 감을 잡았지만 풀지는 못했다. 이번 E F 문제는 특히 알면 풀고 모르면 못 푸는 경향이 강한 것 같다 도와줘요수학귀신 2503등을 하고 129점이 올랐다!! 다음 앳코더는 브론즈 승급전이라고 생각하고 더 열심히 해야겠다 A번 : 문자열, 1차원 배열, swap 문제 제목처럼 string의 홀수번과 짝수번을 swap해서 출력하기만 하면 된다 인덱스 범위를 넘기지 않도록 조심하자 B번 : 1차원 배열, 구현 #include #define fastio cin.tie(0)->sync_with_stdio(0) #define ll long long using namespace std; int ary[200001]; .. [BOJ 11444, 약간 쉬움] 피보나치 수 6 (C++) 개인적인 난이도 약간 쉬움 알면 풀고 모르면 못푼다 모르겠어서 아이디어 부분을 구글링하고 구현만 내가 했다 복습) 피보나치 수열을 컴퓨터로 표현하는 방법은 여러 가지가 있다. 1. 재귀함수를 이용해 계산한다 2. dp를 이용해 계산한다 3. (오늘 배울 방법) : 행렬의 거듭제곱을 이용해 계산한다. 1. 기본적인 모듈러 연산의 성질을 알아야 한다. 모듈러 연산의 합/차/곱에 대해 교환법칙과 분배법칙이 성립함을 알고 있으면 된다. 입력과 출력 사이의 과정에서 매우 큰 수를 다뤄야 할 때 자주 나온다. 2. 분할정복을 이용한 거듭제곱을 할 줄 알아야 한다 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A.. [BOJ 1629, 쉬움] 곱셈 (C++) 개인적인 난이도 쉬움 알면 1분만에 풀고 모르면 그냥 틀린다 매우 중요한 개념이 2 가지 들어있다. 정수론(모듈러 산술) & 분할정복(log N) 몰라서 2번 틀렸다 처음엔 정수론 몰라서 오버플로우로 틀리고 두번째엔 분할정복 몰라서 시간초과로 틀림 성공한 풀이) 핵심 1) 모듈러연산은 신기하게 덧셈 뺄셈 곱셈 분배법칙이 가능하다. 핵심 2) 거듭제곱 계산(pow) 는 분할정복을 이용해 계산하면 log N 안에 끝남 성공한 코드 #include #define fastio cin.tie(0)->sync_with_stdio(0) #define ll long long using namespace std; int main(void) { fastio; ll A,B,C;cin>>A>>B>>C; A%=C; ll ans.. 이전 1 다음
