IM: DAY 18
솔로 데이 첫 날.
드디어 백트래킹의 대표예제인 N-Queen을 풀었다. 백트래킹은 재귀를 이용한 dfs 방법이고 stack을 사용하는게 아니다. 라는 잘못된 개념에 사로잡혀 있었다는 것을 깨달았다. 그냥 머릿속을 백지 상태로 되돌려서 기본 dfs 개념만 가지고 생각하니까 오히려 전보다 쉽게 해결됐다.
내가 푼 문제를 리팩토링 하는 과정의 필요성을 느꼈다. 중요한 포인트인데 내가 미처 중요하다고 판단하지 못하고 지나친 부분들도 발견하고 내가 푼 방법을 더 효율적으로 구성하는 방법을 발견할 수 있어서 유익했던 것 같다. 내일은 짝수번째를 뒤집자.
오늘 한 일
- 백트래킹 문제 풀기(N-Queen)
- 졸업논문 계획서 작성 (1/2)
- 코플릿 알고리즘 문제 홀수번 리팩토링
기억할 것
DFS던 BFS던 레벨을 기준으로 구분하자
- BFS는 반복문을 사용해서 이번 레벨에 있는 노드를 전부 탐색하고 다음 레벨로 넘어간다.
- 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
내일 할 일
- 스도쿠 리팩토링
- 코플릿 알고리즘 문제 짝수번 리팩토링
- 졸업논문 계획서 작성 (조금만,,)
