[필기+면접] 연결리스트, 트리

최근에 도서관에서 발견한 '프로그래밍 면접 이렇게 준비한다'를 읽으면서 내용을 간단하게 요약하여 남기면 좋을 것 같다는 생각이 들었다. 취업준비를 하면서 매일 참고했던 자료들을 돌이켜보면 봤던 내용을 보고 1회성에 멈춘것이 마음에 걸렸다. 물론 공부내용을 연습장에 적었지만 나만의 사이트를 통해 간단하게 정리하면 더 좋을것 같다.

이 책은 학부과정을 충실히 이해하면 알 수 있는 기본내용으로 필기시험 및 기술면접을 돌이켜보면 반정도는 관련내용이 들어있었다.

내가 잘 아는 내용보다는 생소하고 필요한부분만을 간단하게 정리할 예정이다.

코드수정 -> 

                 1. 데이터가 함수에 제대로 들어오는가

                 2. 코드 한줄한줄 작동하는가

                 3. 함수에서 데어터가 올바르게 나오는가

                 4. 빈번히 발생되는 오류조건 체크(비어있는 자료, NULL포인터 다룰때)

* 손코딩 및 코드를 분석할 때, 이 내용을 숙지하고 아는내용을 말한다면 좋은 점수를 받을 것이다. * 

-연결리스트-

(연결리스트는 persuade code를 바탕으로 C/C++카테고리에 포스팅하였다.)

삭제할때 적어도 2개의 포인터 변수 필요, 삽입도 마찬가지이지만

삭제시, 하나는 리스트에 있는 원소를 위해 쓰이고 다른 하나는 메모리 할당에 의해 반환되는 포인터용!!

보통 연결리스트 응용문제를 위해 메모리와 시간을 최적화 하기위해 포인터를 2개를 써서 활용할 수 있다.

* 필기시험에서 연결리스트를 생성하고 삽입 삭제에 대한 코드를 작성해보라고 한다.

스텍 : 연결리스트

동적배열이 좀더 빠르다 -> 배열크기를 자주 조절하지 않아도 되고 적당한 크기의 배열을 쓰는경우에서

덜복잡하고 좋음, 스텍은 구조의 한쪽끝만을 사용하기에 동적배열의 임의접근성을 고려해야한다.

트리 : 이진 트리 -> BST 이진검색트리        구조체{값,좌픅포인터, 우측포인터} -> 트리형성이 중요

보통 면접에서 트리라 하면 이진트리이고 이진검색트리라고 생각하면 된다.

찾는연산(look up) : O(logn), 정렬된 상태 : O(n)  삭제,삽입 : O(logn)

트리형성:  

typedef struct tree { 
    int val;
    tree *l;
    tree *r;
}T;
 

트리순회 : Preorder(전위순회)   - 노드 -> 왼쪽-> 오른쪽           *학부과정에서 배우는 순회방식, 이 개념으로 전위, 후위표기법을 나타낼 수 있다.

              Inorder(중위순회)     - 왼쪽 -> 노드 -> 오른쪽           관련 문제 (출처 : https://www.acmicpc.net/problem/1991 )

              Postorder(후위순회)  - 왼쪽 -> 오른쪽 -> 노드           위의 구조체를 사용하여 직접 트리를 형성하여 문제를 해결해보면 좋을 것 같다.

* 필기문제에서 트리가 주어지고 순회방식에 따른 탐색순서를 표기하는 문제는 자주 출제되었다.

(최대)힙 : 노드의 각 자식의 값은 노드 자신값 이하, (루트가 가장 큰 값), 최대값 상수시간으로 구함, 삽입삭제 : O(logn) , 

     최대값 혹은 최소값을 빠르게 찾을때, 우선순위 큐로 문제해결 가능

*필자는 C++의 STL <prioirty_queue> 라이브러리를 이용한다. 힙은 다익스트라 알고리즘을 해결하는데 자주 사용한다.

LCA : 최소공통조상 

관련문제 (출처 : https://www.acmicpc.net/problem/11437)

*LCA관련 내용은 옆의 출처를 통해 공부할 수 있다 : https://www.crocus.co.kr/660

1. 트리를 만들기 : DFS나 BFS로 깊이와 현 노드의 부모노드를 저장하면서 탐색

2. LCA는 두 깊이가 다른 점을 같게 만들어주는것부터 시작

불균형 이진 검색 트리 : 이진검색트리 속성을 유지하면서 규형이진트리 변환 -> 트리회전필요 -> AVL, red-black tree

                               (좌측은 노드보다 작고 우측은 노드보다 크다)

* 불균형 이진 검색 트리의 내용을 하면서 트리의 회전과 변환이 필요하다. 이 내용은 트리파트에서 어려운 내용에 속한다.

   AVL트리와 Red-Black Tree, B+Tree 등에 대해 알고 직접 프로그램을 짤 수 있다면 실력이 있는 프로그래머라고 필자는 생각한다.

   필자는 필기시험이나 면접에서 아직 위 트리에 대해 질문받은적은 없다.