책읽기003)프로그래밍 면접 이렇게 준비한다 - 2

1. 디버거를 쓰지 않고 체계적 분석, 중점적으로 살펴봐야 할 부분

- 데이터가 함수에 제대로 들어오는지 확인한다.

- 함수의 각 줄이 제대로 작동하는지 확인한다.

- 함수에서 데이터가 올바르게 나오는지 확인한다.

- 흔히 발생하는 오류 조건을 확인한다.

2. 연결 리스트의 마지막에서 m번째 원소 찾기

문제

단일 연결 리스트가 주어졌을 때 리스트의 맨 뒤에서 m번째 원소를 찾아내는 알고리즘을 만들어 보라.

이때 시간 및 공간 효율을 모두 고려해야 한다. 오류 조건의 처리에 주의하여 알고리즘을 구현하라.

여기에서 "맨 뒤에서 m번째 원소"는 m = 0일 때 리스트의 마지막 원소를 변환하는 식으로 생각한다.

순차적으로 찾는 방법

가장 기본적인 알고리즘은 Head에서부터 Tail까지 리스트를 종주하고 전체 리스트를 체크한다.

그리고 Head에서 전체 길이를 L이라 했을 때 L-m번째 노드를 찾으면 된다.

문제점

이렇게 찾아버리면 최악의 케이스의 O가 n제곱의 성능을 가지게 된다. 

물론 m번째가 Head와 같으면 O(n)의 시간복잡도를 가지긴하지만.. 역시 효율적이진 않다.

항상 O(n)으로 찾는 알고리즘?

책에서 보고 깜짝 놀랬다. 물론 충분히 생각할 수 있는 구현방법이지만.. 역시.. 똑똑한 사람은 많다.

p_start와 p_follow를 만들고 p_start를 m만큼 이동한다.

p_start를 m만큼 이동하면 남은 이동수는 L-m의 길이를 가지게 된다.

p_start의 남은 L-m 만큼 p_follow를 이동하면 찾는 노드로 갈 수 있다.

이렇게 하면 m과 관계없이 항상 O(n)의 알고리즘으로 문제를 해결할 수 있다.

집합으로 치면 약간 여집합을 이용한 느낌인데.. 정말 생각지도 못한 풀이다.

역시 배울게 많은 책인거같다.