합병정렬 과 쾌속정렬 비교 - 합병정렬은 최악의 경우에도 O(nlogn)을 보장하지만 퀵소트 즉, 쾌속정렬은 최악의 경우 O(N^2)이 되기도 합니다. 그런데 퀵소트가 빠른 이유는 임시저장공간이 필요한 합병정렬과 달리 임시저장공간이 필요없어서 옮기고 가져오는데에 시간이 필요하지 않기 때문에 평균적으로 쾌속정렬이 빠릅니다.

빅오, 빅쎄타, 빅오메가 들의 차이를 설명하세요.

빅오 계산법에 대해 설명하시오

• 빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용 되며 필요한 계산 횟수를 정확한 숫자로 표현하느 것이 아니라 입력 크기와의 관게로 표현한다

퀵 정렬 방법에 대해 설명하시오

1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
4. 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
5. 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
6. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.

여러 정렬 방법중 가장 효율적인 정렬은 무엇인가?

• 답 최선의 경우 평균적인 경우 최악의 경우

  삽입정렬	O(N)	O(N^2)	O(N^2)
  퀵 정렬	O(NlogN)	O(NlogN)	O(N^2)

• 퀵정렬. 아래의 표와 같이 평균적인 경우를 고려했을때 가장 시간 복잡도가 낮음

1. Big O의 필요성

• 답처리 속도, 메모리등은 하드웨어의 스펙에 의해서 좌지우지되지만 처리단계는 하드웨어와 상관없이 일정하다.
• 정량적으로 알고리즘의 성능을 판단하기 위한 기준으로서 필요.

DFS, BFS를 사용하기 적합한 상황은 언제일까?

• DFS는 주로 모든 노드를 방문하고자 하는 경우에 사용하고, BFS는 두 노드 사이의 최단 경로를 찾고 싶을 때 선택한다.

최소 신장 트리는 무엇인가?

• 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프를 신장트리라고 하는데, 이 신장 트리들 중에서 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장트리를 최소 신장 트리라고 한다

DFS 와 BFS의 차이점에 대해 설명하시오

DFS : 모든 노드를 방문하고자 할 때 사용하는 탐색 알고리즘

순환 알고리즘으로 동작한다.

BFS : 두 노드 사이의 최단 경로나 임의의 경로를 찾고 싶을 때 사용하는 탐색 알고리즘

재귀적으로 동작하지 않으며 큐를 사용한다.(FIFO)

그리디 알고리즘의 장점과 단점에 대해 설명하시오.

• 장점
  • 다른 최적해 계산 알고리즘에 비해 적은 비용 (빠른 속도)
• 단점
  • 당장 그 순간의 최적 값을 찾기 때문에 항상 최적 해를 찾는 것은 불가능

MST의 특징은 무엇인가요?

• 간선의 가중치의 합이 최소여야 한다.
• n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
• 사이클이 포함되어서는 안된다.

DFS가 BFS보다 더 사용하기에 적합할 때는 언제인가?

DFS는 예를 들어, a에서 b까지 갈 때 조건을 검사하거나 특징을 기억해둘 수 있기 때문에 경로의 특징을 기억해야 하는 경우에 경로의 특징을 가지지 못하는 BFS보다 사용하기에 적합하다.

Greedy알고리즘으로 문제를 해결할 수 없는 경우에는 어떻게 풀어야할까?

그리디 알고리즘은 현재 최적의 답안을 찾는 방법이므로 최적의 답안을 찾을 수 없다면 모든 경우의 수를 파악해서 풀어야 한다. 따라서 다이나믹 프로그래밍으로 해결해야 한다.

DFS와 BFS 각각의 시간 복잡도는 어떻게 되나요?

1. DFS (Depth-First Search)와 BFS (Breadth-First Search) 각각의 시간 복잡도는 그래프의 크기를 나타내는 노드 수와 간선 수에 따라 달라집니다.

   DFS의 시간 복잡도는 O(V+E) 입니다. 여기서 V는 그래프의 정점 수이고, E는 그래프의 간선 수입니다. DFS는 한 정점에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색합니다. 따라서 각 정점과 간선은 최대 한 번씩 방문하므로, 시간 복잡도는 O(V+E)입니다.

   BFS의 시간 복잡도도 O(V+E) 입니다. BFS는 시작 정점으로부터 모든 정점을 탐색하고, 각 정점을 방문할 때마다 해당 정점과 연결된 모든 간선을 검사합니다. 따라서 각 정점과 간선은 최대 한 번씩 방문하므로, 시간 복잡도는 DFS와 동일한 O(V+E)입니다.

최소신장트리를 찾는 알고리즘을 구현할 때, 어떤 자료구조를 사용하는 것이 효율적인가요?

1. 최소신장트리를 찾는 알고리즘을 구현할 때 효율적인 자료구조는 해당 알고리즘의 특성에 따라 다릅니다. 하지만 대부분의 경우, 우선순위 큐 혹은 Union-Find 자료구조가 효율적인 선택입니다.
2. Prim 알고리즘에서는 우선순위 큐를 사용하여 현재 트리와 연결된 간선 중 가장 작은 가중치를 가진 간선을 빠르게 찾아내어 처리할 수 있습니다.
3. Kruskal 알고리즘에서는 각 정점을 Union-Find 자료구조를 사용하여 속한 집합을 찾을 수 있습니다. Union-Find 자료구조는 노드 간의 연결 정보를 트리 형태로 저장하며, 경로 압축(path compression)과 크기 기반 합침(union by rank) 등의 최적화를 통해 시간 복잡도를 개선할 수 있습니다.

BFS와 DFS를 쓰기 적절한 경우는?

• 답

최소신장트리가 쓰이는 경우는?

• 답

부정확한 답이 나올 수도 있는 그리디 알고리즘을 사용하는 경우?

A. 최적의 답이 아니더라도 근사치를 구하는 것이 목표인 경우, 속도가 빠른 그리디 알고리즘을 사용하는 것이 만족할 만한 결과를 얻어낼 수 있어 사용된다.

크루스칼 알고리즘과 프림 알고리즘의 차이점?

크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택한다면, 프림 알고리즘은 특정 정점에서 시작해서 해당 정점에 연결된 가장 작은 가중치를 선택한다.

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제

미로 찾기 등 최단거리 문제의 경우, BFS가 유리. 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

검색 대상 그래프가 정말 크다면 DFS를 고려하지만 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS를 사용합니다.