[자구, 알고] 트리, 그래프, 인접행렬, 인접리스트 질문답변

 

 

 

● Binary Tree (이진 트리)

 - 자식노드가 최대 두 개인 노드들로 구성된 트리

 

● Full Binary Tree (전 이진 트리)

 - 모든 노드가 0개 혹은 2개의 children 을 가지고 있을 때
 - leaf 노드들을 제외한 모든 노드들이 2개의 children 을 가지는 것.

● Complete Binary Tree (완전 이진 트리)

 - 마지막 level 을 제외한 나머지 level 에 node 들이 가득 차있고, 마지막 level 에서 node 는 가장 왼쪽 부터 채워지는 형태
 - 데이터의 크기는 상관하지 않음

● Perfect Binary Tree (포화 이진 트리)

 - 모든 internal node 가 두개의 children 을 가지고 있고, 모든 leaf 노드가 같은 level 에 있는 것.

● BST (Binary Search Tree, 이진 탐색 트리)

 - 왼쪽 자식 노드는 부모보다 작은 데이터
 - 오른쪽 자식 노드는 부모보다 큰 데이터

 

 

● 이진 탐색이 무엇인지 설명하고, 시간복잡도를 증명해 보세요.

 - 중간값과 찾으려는 값의 대소를 비교한 뒤 탐색 범위를 반으로 줄여가며 값을 찾는 탐색 알고리즘
운이 좋으면 찾고자 하는 값이 중간값과 동일해서 탐색이 끝나지만 최악의 경우 남은 데이터가 하나가 될 때까지 탐색을 반복한다. 이를 고려해 시간 복잡도를 계산해보자.

 - 전체 데이터의 수를 N 이라고 하자. 
 - 1) 첫 번째 탐색 후 절반만 남아 남은 수가 N/2 개.
 - 2) 두 번째 탐색에서 다시 절반만 남아 남은 수가 N/2 × 1/2 개
 - 3) 세 번째 탐색에서 다시 절반이 남아 남은 수가 N/2 × 1/2 × 1/2 개
 - k) 규칙을 찾아보면 k번째 탐색에서 남은 데이터 수는 (1/2)^k × N 이 된다.
 - 최악의 경우에선 (1/2)^k × N = 1 이 될 때까지 탐색을 하게 됨을 다시 한 번 기억하자.
 - 위 식의 양변에 2^k 를 곱하면 2^k = N 가 되고 다시 양변에 log(2) 를 취하면 최종 식은 k = log(2)N 이 된다.
- 여기서 k는 탐색 횟수로 N에 따라 시행 횟수는 log(2)N 이 된다. 따라서 시간 복잡도는 O(log(2)N) 으로 나타낼 수 있다.

https://kangworld.tistory.com/65#:~:text=%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89%EC%9D%98%20%EC%8B%9C%EA%B0%84%20%EB%B3%B5%EC%9E%A1%EB%8F%84,%EC%94%A9%20%EC%A4%84%EC%97%AC%EB%82%98%EA%B0%80%EA%B8%B0%20%EB%95%8C%EB%AC%B8%EC%9D%B4%EB%8B%A4.

 

 

● Lower Bound, Upper Bound 는 무엇이고, 이를 어떻게 구현할 수 있을까요?

 - 중복된 자료가 있을때 유용하게 탐색할 수 있는 알고리즘
 - lower bound는 데이터내 내가 요구한 값보다 같거나 큰값이 처음 나오는 위치를 리턴
 - upper bound 는 요구한 값보다 처음으로 큰 값이 나오는 위치를 리턴해주는 알고리즘

https://jackpot53.tistory.com/33

 

 

● 삽입, 탐색, 삭제 시간복잡도

 - O(log(2)N)
 - 삭제의 경우 
 - 삭제 노드 탐색 O(log(2)N)
 - 대체 노드를 찾기 위한 서브 트리를 탐색 O(log(2)N)
 - 참조값 변경 O(1)
   => O(2*log(2)N + 1) = O(log(2)N)

https://mommoo.tistory.com/101

 

 

● 이진탐색트리에서 중위 탐색을 하게 되면, 그 결과는 어떤 의미를 가지나요?

1 - 3 - 4 - 6 - 7 - 8 - 10 - 13 - 14
위와 같은 정렬된 형태를 얻을 수 있다.

 

 

● 이진탐색트리의 한계점에 대해 설명해주세요.

 - 편향이 발생하는 경우 링크드리스트와 같은 O(n)의 시간복잡도를 가지게 된다.
 - 그래서 데이터 삽입 시에 균형있는 트리가 만들어지도록 노력해야 한다.

 

 

● 이진탐색트리의 값 삽입, 삭제 방법에 대해 설명하고, 어떤식으로 값을 삽입하면 편향이 발생할까요?

 - 삭제 방식
 - 1. 자식노드가 없는 노드를 지울 때
 - 그냥 지운다.
 - 2. 자식노드가 하나만 있는 노드를 지울 때
 - 부모노드와 자식노드를 이어주고 삭제한다
 - 3. 자식노드가 2개 모두 있을 때
 - ㄱ) 왼쪽 자식노드에서 가장 큰값을 가져온다.
 - ㄴ) 오른쪽 자식노드에서 가장 작은 값을 가져온다.


 - 이진탐색트리가 편향이 발생하는 이유는 삽입 방식에 있다.
 - 삽입되는 노드의 값이 이전에 삽입된 노드들보다 작은 경우에는 왼쪽 자식 노드로 삽입되고, 큰 경우에는 오른쪽 자식 노드로 삽입된다.
 - 삽입 순서가 1, 2, 3, 4, 5, 6, 7일 때 이진 탐색 트리를 구성하면 높이가 7이 되고
 - 4, 2, 6, 1, 3, 5, 7 이면 완전이진탐색트리와 같은 3의 높이를 같는다.
 - 이처럼 이진탐색트리는 삽입순서에 따라 편향이 발생한다.

https://zeddios.tistory.com/492

 

 

● Red Black Tree에 대해 설명해주세요.

 - 자가 균형 이진 탐색 트리
 - 편향이 발생하는 이진 탐색 트리의 개선 버전
 -  노드를 레드와 블랙으로 표시하고, 트리의 가장 깊은 경로가 가장 짧은 경로의 두 배가 되지 않도록 유지하는 방식

 

 

● Red Black Tree는 어떻게 균형을 유지할 수 있을까요?

 - Red Black Tree의 주요 성질 4가지에 대해 설명해 주세요.
 - 루트노드의 색은 검정(black)이다.
 - 모든 리프 노드(NIL; null leaf)는 검정이다.
 - 빨강(red) 노드의 자식은 검정이다. 즉, 빨간 노드가 연속으로 나올 수 없다.
 - 모든 리프 노드에서 black depth는 같다. 즉, 리프노드에서 루트노드까지 경로에 검은색 노드의 개수가 같다.

 

 

● 2-3-4 Tree, AVL Tree 등의 다른 BBST 가 있음에도, 왜 Red Black Tree가 많이 사용될까요?

 - 레드-블랙 트리는 최악의 경우에 다른 BBST보다 연산을 더 적게한다. 예를 들어 AVL 트리는 레드-블랙 트리보다 더 엄격하게 균형잡혀있기 때문에, 삽입/삭제 시 더 많은 회전연산을 하게 된다. 따라서 보통 자가균형 이진탐색트리가 필요한 경우 보통 레드-블랙 트리를 사용한다.

https://woong-jae.com/algorithm/220606-BST
https://code-lab1.tistory.com/62




—----------------------------------------------------------------------------------------------------------

● 트리와 그래프의 차이는 무엇인가요?

 - 트리 : 방향성이 존재, 순환이라는 것이 없음, 루트 존재, 부모노드, 자식노드 개념.
 - 그래프 : 방향성이 있는 것도 있고 없는 것도 있음, 순환, 비순환 가능, 루트, 부모노드, 자식노드 개념 없음.

https://bigsong.tistory.com/33

 

 

● 그래프를 구현하는 두 가지 방식에 대해 설명해주세요.

 - 인접행렬(Adjacency Matrix)
    - 2차원 배열 (aka 행렬) 을 이용
    - 두 개의 노드가 간선으로 연결되어 있다면 인접하다.
    - 인접 행렬에 그래프의 간선 정보를 저장한다.
    - 두 노드의 간선 정보를 확인하는것이 빠르다. O(1)
    - 새로운 간선을 추가하고 제거하는것이 빠르다. O(1)
    - 특정한 노드에 인접한 노드를 찾기위해서 모든 노드를 순회해야 한다.
    - 노드를 추가 하거나 제거하는데 오래 걸린다. O(N^2)
    - 그래프의 모든 간선의 수를 찾는데 O(N^2)

 - 인접리스트(Adjacency List)
    - 인접 정보를 저장하는 리스트
    - 배열의 크기는 노드의 개수와 같다.
    - 특정 노드에 직접 접근할 수 있어 인접한 노드를 찾기 쉽다.
    - 노드의 추가 삭제가 빠르다.
    - 새로운 간선을 빠르게 추가 할 수 있다. O(1)

https://hsc-tech.tistory.com/12

 

복잡도 표현 기호
https://nulls.co.kr/graph/98

 

 

 

● 두 방식의 시간복잡도, 공간복잡도 차이

 - 시간복잡도
    - N = Node의 개수, E = Edge의 전체 개수
    - 인접행렬
       - Node 추가 : O(N^2)
       - Node 삭제 : O(N^2)
       - Edge 추가 : O(1)
       - Edge 삭제 : O(1)
       - Node 추가 : 행과 열을 모두 추가해야 하므로 노드 개수의 제곱만큼의 시간이 필요합니다. 추가로 새로 생긴 행과 열에 대한 각 셀을 채워야 합니다.
       - Node 삭제
       - Edge 추가 : Edge 추가는 특정 셀의 값만 변경(0, 1)하면 되므로 상수 시간만큼 소요됩니다.
       - Edge 삭제 : Edge 삭제는 특정 셀의 값만 변경(0, 1)하면 되므로 상수 시간만큼 소요됩니다.

    - 인접 리스트
       - Node 추가 : O(1)
       - Node 삭제 : O(N+E)
       - Edge 추가 : O(1)
       - Edge 삭제 : O(E)
       - Node 추가 : 이중연결리스트 꼬리 nextNode로 지정하기 때문에 상수 시간만큼 소요됩니다.
       - Node 삭제 : 노드를 삭제하면 삭제된 공간을 채우기 위해 다시 색인하는 과정이 필요하므로 노드, 정점의 개수를 합한 만큼의 시간이 소요됩니다.
       - Edge 추가
       - Edge 삭제 : 최악의 상황은 한 줄로 노드가 연결되어 있는 경우입니다. 삭제하기 위해 마지막 Edge까지 탐색해야 합니다.
https://wjjeong.tistory.com/38

 - 공간 복잡도
    - 인접 행렬
       - O(N^2)
       - 노드수 x 노드수 만큼의 행렬이 필요하기 때문입니다.

    - 인접 리스트
       - O(N+E)
       - 정점의 수만큼 공간이 필요하고 인접한 정점을 저장하기 위해 간선 수만큼의 추가 공간이 필요하기 때문입니다.
https://yoongrammer.tistory.com/84

 

 

● node의 개수가 N개, edge의 개수가 N^3 일 경우, 무엇이 더 효율적일까

 - 인접 리스트가 인접 행렬보다 효율적입니다. 이는 인접 행렬의 공간 복잡도가 O(N^2)이고, 간선의 개수가 N^3이므로, 총 공간 복잡도는 O(N^2 + N^3)이 되기 때문입니다. 반면 인접 리스트의 공간 복잡도는 O(N + N^3)이므로, 더 효율적입니다.

 

 - 또한 간선의 개수가 N^3개인 경우, 인접 리스트를 사용하면 각 노드마다 평균 O(N^2)개의 인접 노드를 가지므로, 인접 리스트를 사용한 그래프 탐색 및 최단 경로 알고리즘의 시간 복잡도는 O(N^5)입니다. 반면 인접 행렬을 사용하면 간선의 개수가 많기 때문에 탐색 및 최단 경로 알고리즘의 시간 복잡도는 O(N^6)이 됩니다.

 

 

● 각 방법에 대해, "두 노드가 연결되었는지" 확인하는 시간복잡도와 "한 노드에 연결된 모든 노드를 찾는" 시간복잡도, 그리고 공간복잡도를 비교해 주세요.

 - 인접행렬
    - 두 노드가 연결되어 있는지 확인하는데는 O(1) 의 시간복잡도
    - 한 노드에 연결된 모든 노드를 찾는데는 O(N)의 시간복잡도
    - 인접행렬은 N x N 크기의 2차원 배열로 구현되므로, 공간복잡도는 O(N^2)
 - 인접리스트
    - 두 노드가 연결되어 있는지 확인하는데는 O(E)의 시간복잡도
    - 한 노드에 연결된 모든 노드를 찾는데는 O(E)의 시간복잡도
    - 인접리스트는 각 노드마다 인접한 노드들의 리스트를 저장하므로, 공간복잡도는 O(N+E)

● Minimum Spanning Tree

 - Minimum Spanning Tree(MST)는 가중치 그래프에서 모든 정점을 연결하는 부분 그래프 중에서 가중치의 합이 최소인 트리이다.
 - 두 가지 대표적인 알고리즘으로 Kruskal 알고리즘과 Prim 알고리즘이 있다.
 - 두 가지 모두 탐욕적인 방법(greedy method) 를 사용한다.

 

 

● Kruskal algorithm

 - 엣지들을 가중치의 오름차순으로 정렬한다.
 - 가장 가중치가 작은 엣지부터 선택하며, 이때 선택된 엣지가 사이클을 형성하지 않는 경우에만 그래프에 추가한다.
 - 모든 노드를 연결할 때까지 2번의 과정을 반복한다.

 

 

● Prim algorithm

 - 임의의 시작 노드를 선택하고, 해당 노드에 연결된 모든 엣지을 우선순위 큐에 추가한다.
 - 우선순위 큐에서 가장 가중치가 작은 엣지을 선택하고, 해당 엣지와 연결된 노드가 MST에 포함되지 않은 경우에만 해당 노드를 MST에 추가한다.
 - 새로 추가된 노드와 연결된 모든 엣지을 우선순위 큐에 추가한다.
 - 모든 노드가 MST에 포함될 때까지 2~3번의 과정을 반복한다.

● Kruskal algorithm 은 인접 리스트와 인접 행렬 중 무엇을 쓰나요?

 - 인접 리스트와 인접 행렬 두 가지 방법 모두 사용가능하지만 간선들의 정렬과 사이클 검사에 많은 시간이 소요되므로, 인접 리스트를 사용하면 각 정점마다 연결된 간선들을 쉽게 탐색할 수 있기 때문 더 효율적인 구현이 가능

● 사이클이 없는 방향 그래프는 모두 트리인가요? 그렇지 않다면, 예시를 들어주세요.

 - 비순환 그래프(Acyclic Graph)라고 모두 트리는 아니다.
 - 예로 사이클이 없는 그래프인 DAG와 여러 트리로 이루어진 Forest가 있다.

https://2jinishappy.tistory.com/225
https://velog.io/@jeewoo1025/%ED%8A%B8%EB%A6%AC-Tree

● 그래프에서, 최단거리를 구하는 방법에 대해 설명해 주세요.
 - 그래프에 가중치가 없을땐 BFS
 - 음의 가중치가 없을땐 다익스트라
음의 가중치가 있을땐  벨만포드