궤도

문제 풀이 myunji.tistory.com/255 [백준] 1629번 : 곱셈 문제 풀이 거듭제곱 계산 문제는 유명한 분할 정복 문제이다. A^B가 있을 때 이 문제를 어떻게 나눌 수 있을까? B가 짝수일 때 A^B = A^(B/2) * A^(B/2) B가 홀수일 때 A^B = A * A^(B-1) 종료조건은 사람마다 B myunji.tistory.com myunji.tistory.com/257?category=1154147 [백준] 2740번 : 행렬 곱셈 문제 풀이 시도때도 없이 바뀌는 교육정책과 교육과정에서 손해를 보는건 결국 학생들인데... 그런 학생들 중에서는 행렬을 배우지 못한 나같은 사람도 있다. 우리 학년부터 행렬을 배우지 않았 myunji.tistory.com 이 두문제를 섞은 문제다...

문제 풀이 시도때도 없이 바뀌는 교육정책과 교육과정에서 손해를 보는건 결국 학생들인데... 그런 학생들 중에서는 행렬을 배우지 못한 나같은 사람도 있다. 우리 학년부터 행렬을 배우지 않았다고 말하면 내 나이가 들통나겠지만 뭐...별로 신경쓰지 않겠다. 아무튼 행렬을 배우지 않은 나는 행렬의 곱셈 문제가 나올 때마다 구글링을 해야하는 처지가 됐는데... 행렬의 곱셈을 정리하면 이렇게 된다. 행렬 A와 B를 곱할때 A 행렬은 행을 기준으로 나누고, B 행렬은 열을 기준으로 나눈다. 그리고 각 행과 열에 맞춰 곱하고 더하면 된다... 인터넷엔 행렬을 배운 훌륭한 선생님들이 많으니 그 분들을 찾아가는게 나을 것 같다. 소스코드 #include using namespace std; int matrixA[100][..

문제 풀이 페르마의 소정리를 이용해 곱셈의 역원을 구하라던 힌트를 보고 당황했다. 일단 페르마의 소정리가 뭔지 모르겠고, 이항 계수문제랑 곱셈의 역원이 무슨 상관인지도 몰랐기 때문이다. 그래서 힌트를 좀 봤다. 이항계수를 정리하면 대충 이런 모습인데 우리는 이걸 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..