궤도

문제 풀이 분할정복 문제다. 일단 그냥 판을 크게 4등분 한다면 1 2 3 4 이 순서로 방문해야 한다. 그러면 판을 계속 4등분 하면서 우리가 구하고자 하는 좌표가 존재하는 사분면만 탐색하면 될 것 같은데 함수에 들어갈 인자가 뭐가 있을까... 사람마다 다르겠지만 대충 이번에 탐색할 사분면을 A라고 하면 기본적으로 들어가는 N, r, c에 더해서 A의 가장 왼쪽 위 좌표와 해당 좌표를 방문하는 순서를 저장했다. 4등분 될 때마다 N은 1씩 줄어든다. N이 0이 될 때까지 탐색하면 될 것이다. 소스코드 #include #include #include #include using namespace std; int recurZ(int N, int r, int c, int num, pair p) { if (N ..

문제 풀이 피보나치 수를 행렬의 곱셈을 이용해 푸는 문제이다. 솔직히 뭔 말인지 몰랐다. 행렬을 배운적 없으니...그래서 검색을 해보니까 피보나치 수의 점화식을 행렬로 표현할 수 있다는 글을 봤다. 과정은 잘 모르겠고 결과만 놓고보면 이렇다고 한다. 선형대수학이라도 배워둘 걸 그럤다. 물론 배웠어도 도움이 되진 않았을 것 같다만... 아무튼 이렇게 정리가 됐으니 이 문제는 myunji.tistory.com/258?category=1154147 [백준] 10830번 : 행렬 제곱 문제 풀이 myunji.tistory.com/255 [백준] 1629번 : 곱셈 문제 풀이 거듭제곱 계산 문제는 유명한 분할 정복 문제이다. A^B가 있을 때 이 문제를 어떻게 나눌 수 있을까? B가 짝수일 때 A^B = A^(B..

문제 풀이 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..