10일차
게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 p.139 ~ p.141, 2.1, 2.2
내용 정리
9 면접 문제
02 연결리스트
- 연결리스트는 차례로 연결된 노드를 표현해주는 자료구조이다.
- 단방향 연결리스트에서 각 노드는 다음 노드를 가리킨다.
- 양방향 연결리스트에서 각 노드는 다음 노드와 이전 노드를 함께 가리킨다.
- 배열과는 달리 연결리스트에서는 특정 인덱스를 상수 시간에 접근할 수 없다.
- K번째 원소를 찾고 싶다면 처음부터 K번 루프를 돌아야 한다.
- 연결리스트의 장점은 리스트의 시작 지점에서 아이템을 추가하거나 삭제하는 연산을 상수 시간에 할 수 있다는 점이다.
연결리스트 만들기
-
LinkedList 자료구조를 사용할 수 있다.
- 연결리스트에 접근할 때 head 노드의 주소를 참조하는 방법도 사용할 수 있다.
- 두번째 방법은 여러 객체들이 동시에 연결리스트를 참조하는 도중에 head가 바뀌면 어떻게 해야 할지 생각해 봐야 한다.
- 따라서 할 수 있다면, Node 클래스를 포함하는 LinkedList 클래스를 만드는게 가장 좋다.
- 면접에서 연결리스트에 대해 이야기 할때는 단방향인지 양방향인지 반드시 인지해야 한다.
단방향 연결리스트에서 노드 삭제
- 노드 n이 주어지면, 그 이전 노드 prev를 찾아 prev.next를 n.next와 같도록 설정한다.
- 양방향 연결리스트인 경우에는 n.next가 가리키는 노드를 갱신하여 n.next.prev가 n.prev와 같도록 설정해야 한다.
- 유의해야 할점
- 널 포인터 검사
- 필요하면 head와 tail 포인터도 갱신해야 한다.
- C나 C++처럼 메모리 관리가 필요한 언어는 할당된 메모리가 반환되었는지 확인한다.
Runner 기법
- Runner(부가 포인터)는 연결리스트 문제에서 많이 활용되는 기법이다.
- 연결리스트를 순회할 때 두 개의 포인터를 동시에 사용하는 것이다.
- 한 포인터가 다른 포인터보다 앞서도록 한다.
- 예시 : a1->a2->a3->…->an->b1->b2->…->bn 을 a1->b1->a2->b2->…->an->bn 으로 정렬해보자.
- 앞선 포인터 p1을 p2가 한번 움직일 때마다 두번 움직이도록 설정하자.
- p1이 끝에 도달하면 p2는 가운데 지점에 도착한다.
- 이때 p1을 다시 앞으로 옮긴후 p2가 원소를 재배열하기 되면 p2가 가리키는 원소를 p1 뒤로 옮길 수 있다.
재귀 문제
연결 리스트 문제의 상당수는 재귀 문제로 해결될 수 있다. 하지만 재귀 호출 깊이가 n이 될 경우, O(n)의 공간을 사용하게 되니 유의하자.
면접 문제
2.1 중복 없애기
정렬되어 있지 않은 연결리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라.
나의 답 : 연결 리스트를 순회하며 원소들을 배열에 넣고 중복 여부를 검사할 것 같다.
정답
연결리스트를 순회하면서 해시테이블에 넣는다. 이미 존재한다면 삭제한다.
2.2 뒤에서 k번째 원소 구하기
단방향 연결리스트가 주어졌을 때 뒤에서 k번째 원소를 찾는 알고리즘을 구현하라.
나의 답 : 1번 순회하여 연결리스트의 길이를 측정해 n이라 한 후 맨 앞에서 n-k번째 원소를 찾는다.
정답
포인터 두개를 설정해 두 포인터의 간격을 k로 설정한다. 앞선 포인터가 끝에 도달하면 두번째 포인터는 뒤에서 k번쨰에 도달하게 된다.
읽고 나서
정글에서 malloc을 구현했었을 때가 생각난다. 그땐 뭔소린가 싶었는데.. 물론 여전히 뭔소린가 싶긴 하지만 그때 몰랐던 기초 용어들을 알게 되었다. 파이썬은 너무 고급 언어라 여기선 의미 없는것 같다.
