궤도

문제 풀이 myunji.tistory.com/264?category=1154147 [백준] 1654번 : 랜선 자르기 문제 풀이 parametric search 문제라고 써있었다. 근데 난 이게 뭔지 모르니 검색을 해보았다. www.crocus.co.kr/1000 파라매트릭 서치(Parametric Search) 목차 1. 파라매트릭 서치(Parametric Search)란? 2. 예.. myunji.tistory.com 이 문제와 풀이가 같다. 굳이 다른 점을 찾자면 저 문제는 특정 길이에 대해 자를 수 있는 랜선의 수를 리턴한다면 이건 특정 거리에 대해 설치 가능 여부를 리턴 받는다는 점..? 이렇게 말하면 뭐가 다른 건지 감이 안올테니 바로 코드로 넘어가겠다. 소스코드 #include #includ..

문제 풀이 myunji.tistory.com/264?category=1154147 [백준] 1654번 : 랜선 자르기 문제 풀이 parametric search 문제라고 써있었다. 근데 난 이게 뭔지 모르니 검색을 해보았다. www.crocus.co.kr/1000 파라매트릭 서치(Parametric Search) 목차 1. 파라매트릭 서치(Parametric Search)란? 2. 예.. myunji.tistory.com 이 문제랑 풀이가 동일하다. 그러니 딱히 설명하지 않도록 하겠다. 소스코드 #include #include #include using namespace std; typedef long long ll; int N, M; vector tree; ll cntTree(ll length) { /..

문제 풀이 parametric search 문제라고 써있었다. 근데 난 이게 뭔지 모르니 검색을 해보았다. www.crocus.co.kr/1000 파라매트릭 서치(Parametric Search) 목차 1. 파라매트릭 서치(Parametric Search)란? 2. 예시를 통한 파라매트릭 서치(Parametric Search) 3. 시간 복잡도 4. 정리 5. 관련 문제 1. 파라매트릭 서치(Parametric Search)란? Parametric Search에 대해.. www.crocus.co.kr 이 글을 보고 완벽하게 이해했다. 그렇다면 이 문제에서 left와 right는 무엇일까? 랜선의 길이가 0cm일 수는 없으니까 left는 1일 것이다. 그리고 막연하게 right는 가장 짧은 랜선의 길이와 ..

문제 풀이 처음엔 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][..