[19회 - 데일리과제] TCP와 UDP / MST 알고리즘

1. TCP와 UDP에 대해 설명해주세요.

TCP와 UDP는 모두 인터넷 프로토콜 스택의 전송 계층에서 사용되는 프로토콜입니다. 
TCP는 연결 지향형 프로토콜로, 높은 신뢰성을 보장하지만 속도가 느립니다. 
반면, UDP는 비연결형 서비스로 신뢰성이 낮지만 속도가 빠르며 네트워크 부하가 적습니다. 
간단하게 말하면, TCP는 신뢰성이 높은 전송이 필요할 때 사용하고, UDP는 연속성이 중요한 서비스에 자주 사용됩니다.
사용예시로는 TCP는 파일전송, 메일 등에서 주로 사용되며,

UDP는 실시간 반응이 중요한 온라인게임, 화상회의에서 사용됩니다.

 

🔥꼬리질문🔥

 <  TCP의 세션 관리 과정은 어떻게 이루어지나요? >

3-way handshake는 TCP 세션 연결을 위해 수행되는 과정입니다. 
이 과정은 다음과 같습니다:
1. 클라이언트가 서버에게 SYN 패킷을 보내 세션 연결을 요청합니다.
2. 서버는 클라이언트의 SYN 요청을 받고, 클라이언트에게 요청을 수락한다는 ACK와 SYN을 보냅니다.
3. 클라이언트가 서버의 ACK를 받으면 세션이 설정됩니다.

4-way handshake는 TCP 세션 종료를 위해 수행되는 과정입니다. 
이 과정은 다음과 같습니다:
1.클라이언트가 서버에게 FIN 패킷을 보내 세션 종료를 요청합니다.
2.서버는 클라이언트의 FIN 요청을 받고, 클라이언트에게 ACK를 보냅니다.
3.서버가 통신이 끝나면, 즉 연결을 종료할 준비가 되면 클라이언트에게 FIN 패킷을 보냅니다.
4.클라이언트가 서버의 FIN 패킷을 받고 ACK를 보내면 세션이 종료됩니다.

 

< TCP 프로토콜에서 패킷의 재전송은 어떻게 이루어지나요? >

TCP 프로토콜에서 패킷의 재전송은 수신자로부터의 ACK(Acknowledgement)에 기반을 두고 이루어집니다.
수신자는 세그먼트를 받으면 다음 세그먼트를 보내 달라는 ACK를 전송합니다. 
만약 송신자가 ACK를 받지 못하면 일정 시간을 대기한 후 패킷을 재전송합니다.
만약 수신자가 순서에 벗어난 세그먼트를 받으면 중복 ACK를 전송합니다. 
이 경우 송신자는 중복 ACK를 받으면 패킷을 재전송합니다.

2. MST 알고리즘에 대해 설명해주세요.

MST는 Minimum Spanning Tree의 약자로, 최소 신장 트리를 의미합니다. 
이는 그래프 내의 모든 정점을 포함하는 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리를 말합니다.
간단하게 말하면, MST는 여러 개의 도시가 있을 때 각 도시를 모두 연결하는 도로망을 만들 때, 
가장 적은 비용으로 만들 수 있는 도로망을 찾는 것과 같습니다. 
이를 구하는 알고리즘으로는 Kruskal 알고리즘과 Prim 알고리즘이 대표적입니다.

 

Kruskal 알고리즘과 Prim 알고리즘

Kruskal 알고리즘과 Prim 알고리즘은 모두 최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 알고리즘입니다. 두 알고리즘 모두 O(ElogV)의 시간복잡도를 가지지만, 그 방법이 다릅니다.

Kruskal 알고리즘은 간선들을 가중치 순으로 정렬한 후, 가장 작은 가중치의 간선부터 선택하면서 사이클을 형성하지 않는 간선을 선택합니다. 이 과정에서 서로소 집합 자료 구조(유니온 파인드: 결합과 검색)를 이용하여 어떤 꼭짓점이 어떤 콤포넌트(component)에 속하는 지 추적합니다.

반면에 Prim 알고리즘은 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법입니다. 이전 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장합니다.

Kruskal 알고리즘은 간선 선택을 기반으로 하는 반면, Prim 알고리즘은 정점 선택을 기반으로 합니다. Kruskal 알고리즘은 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이며, Prim 알고리즘은 이전 단계에서 만들어진 신장 트리를 확장하는 방법입니다.

 

🔥꼬리질문🔥

<spanning tree란 무엇인지 설명해주세요>

스패닝 트리는 네트워크의 루프를 방지하는 방법입니다. 
순환 경로가 없는지 확인하면서 네트워크의 모든 장치를 포괄하는 트리와 같은 구조를 만듭니다. 
루프를 제거함으로써 스패닝 트리는 장치 간의 효율적이고 안정적인 통신을 유지하는 데 도움이 됩니다.

<MST에서 사이클이 발생하는 경우는 어떻게 처리되나요?>

MST는 그래프의 모든 정점을 포함하는 트리 중에서 간선의 가중치 합이 최소인 트리입니다. 
MST는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안됩니다. 
따라서 MST는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결합니다. 
이러한 이유로 MST에서 사이클이 발생하는 경우는 없습니다.