솔로 데이 첫 날.
드디어 백트래킹의 대표예제인 N-Queen을 풀었다. 백트래킹은 재귀를 이용한 dfs 방법이고 stack을 사용하는게 아니다. 라는 잘못된 개념에 사로잡혀 있었다는 것을 깨달았다. 그냥 머릿속을 백지 상태로 되돌려서 기본 dfs 개념만 가지고 생각하니까 오히려 전보다 쉽게 해결됐다.
내가 푼 문제를 리팩토링 하는 과정의 필요성을 느꼈다. 중요한 포인트인데 내가 미처 중요하다고 판단하지 못하고 지나친 부분들도 발견하고 내가 푼 방법을 더 효율적으로 구성하는 방법을 발견할 수 있어서 유익했던 것 같다. 내일은 짝수번째를 뒤집자.
X를 Y로 나눈 나머지를 R이라 할 때, X와 Y의 최대공약수는 Y와 R의 최대공약수와 같다.
나머지(R)가 0이 될 때까지 Y와 R의 나머지 연산을 반복한다.
나머지가 0이 됐을 때 Y 값의 자리에 있는 수R(n)
가 X1과 Y1의 최대공약수이다.
X1
%
Y1
=
R1
Y1
%
R1
=
R2
R1
%
R2
=
R3
...
R(n-1)
%
R(n)
=
0
예를 들어, 85와 51의 최대공약수를 유클리드 호제법으로 구한다고 가정해보자.
85
%
51
=
34
51
%
34
=
17
34
%
17
=
0
나머지가 0이 됐을 때 Y 값의 자리에 있는 17
이 85와 51의 최대공약수이다.
이 때, X와 Y의 순서(대소비교)는 중요하지 않다. 어차피 두번째 연산에서 순서가 맞춰진다.
위의 예시로 다시 살펴보자.
51
%
85
=
51
// 연산이 1회 더 진행 될 뿐 어차피 순서가 맞춰진다.
85
%
51
=
34
51
%
34
=
17
34
%
17
=
0