궤도

문제 풀이 페르마의 소정리를 이용해 곱셈의 역원을 구하라던 힌트를 보고 당황했다. 일단 페르마의 소정리가 뭔지 모르겠고, 이항 계수문제랑 곱셈의 역원이 무슨 상관인지도 몰랐기 때문이다. 그래서 힌트를 좀 봤다. 이항계수를 정리하면 대충 이런 모습인데 우리는 이걸 1,000,000,007로 나눈 나머지를 구해야 한다. 그렇다고 이럴 순 없다. 왜냐하면 나머지는 0이 나올 수도 있고, 분모가 0이 되면 안되기 때문이다. 그래서 B의 역원을 구한 뒤 그 값에 대해 나머지 연산을 해야한다. 그리고 그 역원 계산에 페르마의 소정리가 필요한 것이다. ko.wikipedia.org/wiki/%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98_%EC%86%8C%EC%A0%95%EB%A6%AC 페르마의 소..

문제 풀이 거듭제곱 계산 문제는 유명한 분할 정복 문제이다. A^B가 있을 때 이 문제를 어떻게 나눌 수 있을까? B가 짝수일 때 A^B = A^(B/2) * A^(B/2) B가 홀수일 때 A^B = A * A^(B-1) 종료조건은 사람마다 B가 0일때 하거나 1일때 하거나 하던데 난 그냥 1로 했다. 소스코드 #include using namespace std; typedef long long ll; ll divide(ll A, ll B, ll C) { ll tmp; if (B == 1) //더이상 나눌 수 없음 return A % C; else { if (B % 2 == 0) { //짝수 거듭제곱일 때 tmp = divide(A, B / 2, C); return (tmp * tmp) % C; } el..

문제 풀이 myunji.tistory.com/251 [백준] 2630번 : 색종이 만들기 문제 풀이 전형적인 분할 정복 문제다. divide and conquer라고 부르는데 문제의 수를 쪼개가며 푸는 것이다. 문제를 쪼갤 때는 보통 재귀함수를 많이 사용한다. 이 문제도 색종이의 색이 모두 같을 myunji.tistory.com 이 문제에서 거의 한줄만 수정하면 된다. 4번 쪼개던걸 9번 쪼개니까 4(2*2)번 돌던 for문을 9(3*3)번 돌게 하면 되는 것이다. 소스코드 #include using namespace std; int paper[2187][2187]; int nums[3]; //nums[0] = -1, nums[1] = 0, nums[2] = 1 bool isSame(int size, i..

문제 풀이 myunji.tistory.com/251 [백준] 2630번 : 색종이 만들기 문제 풀이 전형적인 분할 정복 문제다. divide and conquer라고 부르는데 문제의 수를 쪼개가며 푸는 것이다. 문제를 쪼갤 때는 보통 재귀함수를 많이 사용한다. 이 문제도 색종이의 색이 모두 같을 myunji.tistory.com 이 문제와 유사한 문제이다. 분할을 하는 지점에서 괄호를 입력한다는 걸 깨달으면 문제 자체는 금방 풀린다. 소스코드 #include using namespace std; int video[64][64]; bool isSame(int size, int row, int col, int color) { for (int i = row; i < (size + row); i++) { for..

문제 풀이 전형적인 분할 정복 문제다. divide and conquer라고 부르는데 문제의 수를 쪼개가며 푸는 것이다. 문제를 쪼갤 때는 보통 재귀함수를 많이 사용한다. 이 문제도 색종이의 색이 모두 같을 때까지 색종이를 4등분하며 문제를 쪼개나가면 된다. 소스코드 #include using namespace std; int paper[128][128]; int colors[2]; //colors[0] = white, colors[1] = blue bool isSame(int size, int row, int col, int color) { for (int i = row; i < (size + row); i++) { for (int j = col; j < (size + col); j++) { if (p..

문제 풀이 문제 자체도 시간초과 때문에 아주 만만한 문제는 아닌데 입력이 아주 재미나게 들어와서 난이도를 더하는 문제다. 문제의 제목은 입력을 처리하다 나오는 말을 쓴 것 아닐까? 아무튼 시간초과를 보고 싶지 않다면, 이걸 생각하면 된다. R이 나왔을 때 꼭 배열을 뒤집을 필요는 없다. 한 수열에 대해 뒤에서부터 출력하면 reverse한 수열을 앞에서부터 출력하는 거랑 다를게 없다. 소스코드 #include #include #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); string p, arr; int T, n; cin >> T; for (int i = 0; i < T; i++) { ci..

문제 풀이 입력을 어떻게 처리할지만 구상하면 이 문제는 끝난거나 다름 없다. 이 문제에서 가장 신경써야 하는 것은 각각 다른 위치에 있는 숫자들을 정해진 순서로 뽑아야 하는 것이다. 그니까 입력에서 주어진 수들 말고는 신경 쓸 필요 없고, 입력값들도 그걸 그대로 저장하는 것이 아니라 입력된 위치에 순서 정보로 넣어주면 된다. 예제 입력 2에 대해 입력을 처리하면 0 1 0 0 3 0 0 0 2 0 이렇게 된다. 1, 2, 3의 순서로 숫자가 뽑히도록 할 것이니 2번, 9번, 5번에 위치한 수들이 순서대로 뽑힐 것이다. 소스코드 #include #include using namespace std; int left_move(deque dq, int index) { int cnt = 0; deque tmp =..

문제 풀이 덱(deque)을 풀어쓰면 double ended queue이다. 그니까 앞뒤로 접근 가능한 큐라는 건데 빨대라고 생각하면 되겠다. www.cplusplus.com/reference/deque/deque/?kw=deque deque - C++ Reference difference_typea signed integral type, identical to: iterator_traits ::difference_type usually the same as ptrdiff_t www.cplusplus.com 풀이 #include #include #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false)..