[GCD 알고리즘] 최대공약수 알고리즘
GCD 알고리즘 GCD(Greatest Common Divider, 최대공약수)를 구하는 방법 중 하나로 유클리드 호제법(유클리드 알고리즘, Euclidean algorithm)이 있습니다. 유클리드 호제법은 간단합니다. a, b의 최대 공약수를 (a, b)라고 정의하면 다음과 같은 관계가 성립합니다. $$ \begin{align}(a, b) = (b, r) \newline &where, a \geq b, 0 \leq r < b\end{align} $$ 단, a, b는 정수이고, a를 b로 나눈 나머지는 r 입니다. 증명은 비교적 간단하지만, 수식이 조금 복잡할 수 있습니다. 따라서 최대한 핵심 수식만 쓰고, 나머지는 말로 풀었습니다. 증명은 다음과 같습니다. 1) $$ (a, b) = d, a = d ..
2019. 10. 18.
13460 구슬 탈출 2
삼성 SW 역량 문제. 방향이 4방향이니까, 한 방향에 대해서 깊히 생각해보고 구현하면 나머지는 비슷한 방법이다. 그래서 코드도 비슷하지만, 길어진 코드가 되었다. 총평 - 모든 경우의 수를 세는 dfs는 잘 구현했다. - dfs 기저조건에서, 최솟값을 구하는 방법을 이제는 낯설어 하지 말자. - 결국, 시뮬레이션의 디테일한 구성사항을 논리적 오류없이 구현해야하는 것이 중요했다. - 반례들을 몇 십 차례 적용해 본 결과로 논리적 허점을 찾고, 수정하여 답을 얻었다. - 문제였던 곳은, 빨간공과 파란공이 같은 선 상에 있을 때, 움직인 후 겹치지 않게 처리하는 부분이었다. 이 부분을 알고리즘 처음 짤 때부터, 신중히 생각하고 만들었으면, 더 좋았을 것 같다. #include int N, M; char a[..
2019. 10. 6.
14889. 스타트와 링크
사람은 총 N명, 최대 20명 이를 순열로 늘어 놓아서 앞에는 스타트팀, 뒤에는 링크팀으로 하면 중복계산도 상당히 많고, 총 경우의 수는 20! = 상당히 큰 수이다 >>>>>>>>>>>> 1억 당연히 시간초과가 난다. 문제를 풀면서 자연스럽게 생각할 수 있는 것은 사실 조합이다. 20C10 는 10! 보다 작을 것이라는 것을 예측할 수 있는데 실제로 그 결과는 10!(3백만)보다 훨씬 작다. 18만정도이다. 여기에 각 팀 스코어를 계산해야하는 시간이 (N/2) x (N/2) 이므로 100이라고 하면, 1800만 < 2초 안에 가능하다. 내가 맨 처음에 한 것은, 예를들어 1, 2, 3을 뽑았으면 총 1, 2, 3, 4, 5, 6 인 set에서 1, 2, 3을 뽑는 것이다. 즉 4, 5, 6을 만드는 것..
2019. 9. 21.
14888. 연산자 끼워넣기
같은 것을 포함한 순열이라는 느낌을 받고, 이를 구현해보려고 하다가, 잘 안되서 결국 못했다. 조합을 여러번 하는 것으로 구현해보려고 하다가, 너무 복잡해지는 감이있어서, 다시 완전탐색을 시도. 연산자는 최대 10개이고, 같은 연산자라도 다 다르다고 취급하고, 순열의 수를 생각해봤을 때, O(N!)의 시간복잡도를 가진다. 10! = 3,628,800 이므로 충분. 처음에는, 마지막 기저조건(return)에서 모든 결과값을 계산하는데 O(N)시간을 써먹어서 시간이 좀 느리게 나왔다. #include int N; int nums[12]; char opers[12]; int chk = 1
2019. 9. 19.
