Simple in Complex with Simple

1. 문제

 다음과 같은 그림에서 초록색 노드를 찾는 알고리즘을 작성하시오.

2. 코드

2-1) 메인

2-2) 교차 리스트 생성 함수

2-3) 메인 알고리즘 함수

2-4) 출력

3. 해설

 이 문제는 아주 간단하다. 2개의 리스트 생성 시간 O(n+m)에 검색시간 O(n)을 더해서 최종적으로 빅오를 따지기에

O(n+m)에 풀린다. 스택이나 다른 방법으로도 충분히 풀어낼 수 있지만 이 포스팅에서는 Hash방법을 이용해서 

풀었다. 메인 알고리즘은 처음 생성한 리스트의 노드 주소를 모두 Hash 테이블에 저장한 뒤, 두 번째 리스트와

Hash 테이블을 같은 노드의 주소가 나올 때까지 비교한다. 

 딱히 어려운 알고리즘은 아니지만 굳이 포스팅한 이유는 Hash라는 기법에 더 익숙해지기 위해서이다. 왜냐하면 모든

기초 알고리즘은 모든 경우를 다 검색하는 Brute Force기법, 정렬을 이용한 기법, 스택이나 큐를 이용한 자료구조를

활용한 기법 그리고 마지막으로 Hash 방법을 사용하여 풀어내는 기법. 총 4가지로 구분되기 때문이다. 앞으로 알고리즘

을 생각할 때에는 위의 순서에 준해서 생각한다.

1. 코드

1-1) 메인

1-2) 함수

1-3) 출력

2. 해설

 이번 선형 자료구조인 링크드 리스트 뒤집기 알고리즘은 먼저 O(n)에 풀리는 알고리즘이다. 아주 간단한 알고리즘이지만 

포인터를 활용하는데 가장기초적인 부분이기 때문에 연습삼아 작성했다. 핵심은 3가지다. 기존 주소의 보존, 알고리즘 처리, 

다음 단계로의 이동. 이 코드는 무척 단순하지만 모든 반복문 코드가 이 세가지에서 이루어진다. 그렇기때문에 이를 명확히 

기술할 수 있는 지에 대한 연습이었다.

1. 개요

 문제는 이렇다. 어떤 리스트가 있다. 그 리스트의 구조는 모른다. 이 때, 이 리스트의 구조가 순환 형태인지 아닌지 어떻게

알 수 있을까? 

 이 문제를 O(n)에 풀어내는 알고리즘이 플로이드의 순환 찾기 알고리즘이다.

플로이드의 순환 찾기 알고리즘을 단순히 표현하면 이렇다. 만약

 (출처) https://nol2soft.wordpress.com/2013/07/13/linked-list-cycle-detection-explanation

 이런 형태의 순환 리스트가 있을 때, 토끼와 거북이가 시작점에서 출발한다. 토끼는 거북의 속도보다 2배 더 빠르다. 

토끼가 먼저 출발한다. 당연히 토끼보다 느린 거북이는 평생 토끼를 잡을 수 없다. 그렇지만 만약 둘이 만나게 되면

이 리스트는 순환 구조를 가졌다고 판명된다. 

 여기까진 굳이 플로이드의 순환 찾기 알고리즘이라는 거창한 이름없이 그냥 당연한 알고리즘이다. 하지만 이제부터 

엄청난 사실이 등장한다. 바로 이 순환의 시작점을 어떻게 찾을까? 라는 문제가 나온다면 어떻게 풀어야할까? 

2. 풀이

 즉, 위의 그림에서 m의 길이를 어떻게 찾아낼까? m의 값을 모른다. n의 값도 모른다. 

 이 문제는 정수 이론의 핵심이다. ( 나는 잘모른다. ) 하지만 이론은 일단 제쳐두고 아주 간단한 사실이있다.

 답은 이렇다. 

 토끼는 토끼와 거북이가 만난 자리인 k에서 출발하고 거북이는 시작점에서 출발한다. 

 이 때, 둘이 만나는 최초의 자리가 바로 순환의 시작점이다.

 너무 놀랍다. 그리고 한동안 이게 왜 이런지 알 수가 없었다. 하지만 우리가 색깔을 판단할 때 파랑은 파랑이지

파랑색을 이루는 가시광선이 어떤지 알 필요는 없다. 마찬가지로 나도 이해없이 이 사실만을 알아두고 훗날 필요한

일이 있을 때 써먹어 보고 싶었지만 너무 궁금해서 증명을 찾아냈다.

 m = 순환까지의 거리 (찾아야 할 값)

 n = 순환 루프의 길이

 k = 순환 시작점에서 토끼와 거북이가 만난 자리까지의 거리

 자, 여기서 위의 이론을 증명하려면 k와 시작점에서 한 칸씩 이동했을 때 둘이 만나는 장소가 순환의 시작점이다.

=> m + k (시작점에서 만난 자리까지의 거리) + n - k (루프 길이에서 k값을 뺀 나머지) 이 m이라면 성립된다.

=> ( m + k ) + ( n - k ) = m 에서 n - k가 m과 같냐는 것을 보이고 싶기 때문에 n - k = m을 대입한다.

=> ( m + k ) + m = m

=> m + k = 0

=> m = -k

하지만 거리를 구하는 것이기 때문에 절대값을 붙이면 m == k는 동등하다.

3. 결론

 일단 역시 스승님은 위대하다. 이런 사실을 알게 해주셔서. 하지만 솔직히 이 이론을 언제 써먹어서 코드로 작성

할 날이 올지 모른다. 아마 평생 안올지도 모른다. 하지만 굳이 이 글을 쓴 이유는 이 알고리즘을 이해하려고 노력

하면서 처음으로 수학적 공식을 대입하며 증명을 해보려 노력하였다. 한 번 해봤으니 앞으로도 수학적 이론이 겹친

문제에서 이렇게 풀이할 수 있다는 접근법을 알게되었다. 이와같은 방법으로 계속 연습하여 수학 코딩에서 역량을

발전시키자!! 할 수있다! 쫄지말자!