궤도

문제 풀이 처음엔 value(값)와 num(등장 횟수)를 저장하는 구조체를 만들어서 중복없는 배열을 만든 뒤 이분 탐색했다. 그랬더니 시간초과가 발생했다. 그러다 예전에 C++ STL에 이분 탐색 같은게 있었던 것 같은 그런 기분이 들어 검색했더니 세상에 있었다. www.cplusplus.com/reference/algorithm/lower_bound/?kw=lower_bound lower_bound - C++ Reference function template std::lower_bound default (1)template ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val); custom (2)te..

문제 풀이 이분 탐색은 문제의 크기를 반으로 잘라가며 답을 찾는 알고리즘이다. 이런 문제일 때는 주어진 배열을 정렬하고, 배열의 가운데 값(mid)과 목표로 하는 값(target)을 비교한다. 만약 mid==target이면 답을 찾은 것이니 바로 리턴하고 midtarget이면 mid를 기준으로 배열을 잘라 그 왼쪽만 탐색하면 된다. 소스코드 #include #include using namespace std; int A[1000000]; bool binarySearch(int target, int left, int right) { while (left A[mid]) //오른쪽 탐색 left = mid + 1; } return false; } int main() { ios::sync_with_stdio(f..

문제 풀이 피보나치 수를 행렬의 곱셈을 이용해 푸는 문제이다. 솔직히 뭔 말인지 몰랐다. 행렬을 배운적 없으니...그래서 검색을 해보니까 피보나치 수의 점화식을 행렬로 표현할 수 있다는 글을 봤다. 과정은 잘 모르겠고 결과만 놓고보면 이렇다고 한다. 선형대수학이라도 배워둘 걸 그럤다. 물론 배웠어도 도움이 되진 않았을 것 같다만... 아무튼 이렇게 정리가 됐으니 이 문제는 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..