자료구조와 알고리즘

1. BST의 최악의 경우의 예와 시간복잡도에 대해서 설명해주세요.

• 답

  BST에서 삽입 순서에 따라 최악의 경우 skewed 트리가 됩니다. 평균 O(log2n), 최악 O(n)이며 이진 탐색 트리를 완전 이진 트리로 바꿀 수 있다면 최악의 경우를 없앨 수 있습니다.

2. 피보나치 수열을 코드로 구현하는 방법에 대해서 설명해주세요.

• 답

  수학적인 개념에서 피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 말합니다.

  메모제이션이란 재귀함수에서 이미 연산했던 값은 더 이상 연산하지 않아 불필요한 연산을 제거하여 연산을 효율적으로 하며 재귀함수 형식을 따라 가독성이 높은 코드를 작성하기 위한 기법입니다.

  메모제이션을 통해 재귀 함수 구현의 단점인 성능을 대폭 향상시킬 수 있습니다.

  from functools import lru_cache
  
  @lru_cache(maxsize=None)
  def fib(n):
      if n == 0:
          return 0
      elif n == 1 or n == 2:
          return 1
      else:
          return fib(n - 1) + fib(n - 2)
  
  n = 50
  print('Fibonacci({}): {}'.format(n, fib(n)))

  • 파이썬에는 무한한 수열을 다루기 위한 장치로 제너레이터라는 기능이 있습니다. 다른 함수들과 다른 특징은 바로 return 이 없고 yield 가 있다는 것 입니다. 편하게 yield 가 될 때 a 가 리턴된다고 생각하시면 됩니다. 또한 제너레이터는 이터레이터의 성질을 모두가지고 있어서 for 루프에 넣을 수 있습니다.

    def fibo3(n):
        # 제너레이터를 사용한 버전
        # 캐시가 필요없다.
        # O(N)
        a, b = 1, 1
        for n in range(n):
            yield a
            a, b = b, a + b
    
    for n in fibo3(3):
        print(n)

3. 정렬, 탐색에 대해 설명해주세요.

• 답

  탐색이나 정렬 모두 요소를 찾는다는 점에선 같지만, 선형탐색과 이진 탐색 중 이진탐색이 알고리즘 중에서는 더 효율적입니다. 선형탐색은 정렬되지 않은 리스트, 정렬된 리스트 모두에서 사용할 수 있는 반면 이진탐색은 정렬된 리스트에서만 우리가 기대하는 효율을 낼 수 있기 때문에, 정렬이라는 것은 이진탐색을 하기 위한 용도라고 볼 수도 있을 것 같습니다.

  즉, 정렬을 하는 목적은 결국에는 정렬이라는 행위를 통해 찾으려는 값을 빠르게 찾는 것(탐색)에 있다고 생각합니다.

  • 정렬의 목적 : 요소 탐색 시 효율적으로 탐색이 이루어지도록 하게 함(특히 이진 탐색에서 그러하고, 제한적으로는 선형 탐색에서도 그러함)

  • 탐색의 목적 : 최대한 빨리 원하는 요소를 찾아내는 것. 이 때, 선형탐색과 이진탐색 중 보통은 이진탐색이 더 효율적임

    https://www.codeit.kr/community/threads/5410

네트워크

1. TCP와 UDP의 차이점에 대해서 설명해보세요.

• 답

  1. TCP는 Connection 지향이며, UDP는 Connectionless 프로토콜입니다.

  2. TCP는 전송 된 정보의 확인을 위해 유용한 데이터를 전송할 때 높은 신뢰성을 제공합니다. 그리고 손실 패킷이있는 경우 이를 다시 보냅니다. UDP의 경우 패킷이 손실되면 재전송을 요구하지 않고 대상 컴퓨터가 손상된 데이터를 수신합니다. 따라서 UDP는 신뢰할 수없는 프로토콜입니다.

  3. TCP는 데이터를 전송하기 전에 TCP가 연결을 설정하고 패킷의 적절한 전달을 보장하므로 UDP와 비교할 때 속도가 느립니다. 반면에 UDP는 전송 된 데이터가 수신되었는지 여부를 확인하지 않습니다.

  4. UDP의 헤더 크기는 8 바이트이며 TCP의 헤더 크기는 두 배 이상입니다. TCP 헤더 크기는 20 바이트이므로 TCP 헤더에는 옵션, 채우기, 체크섬, 플래그, 데이터 오프셋, 확인 번호, 시퀀스 번호, 원본 및 대상 포트 등이 포함됩니다.

  5. TCP와 UDP는 모두 오류를 검사 할 수 있지만 TCP만이 정체와 흐름 제어를 모두 가지고 있으므로 오류를 수정할 수 있습니다.

     https://ko.gadget-info.com/difference-between-tcp

2. TCP 3,4 way handshake에 대해서 설명해보세요.

• 답

  3-way handshake의 과정은

  1. 클라이언트는 서버에 접속을 요청하는 SYN 패킷을 보냅니다. 이 때 클라이언트는 SYN을 보내고 SYN/ACK 응답을 기다리는 SYN_SENT 상태가 됩니다.

  2. 서버는 SYN 요청을 받고 클라이언트에게 요청을 수락한다는 ACK과 SYN Flag가 설정된 패킷을 발송하고 클라이언트가 다시 ACK으로 응답하기를 기다립니다. 이 때 서버는 SYN_RECEIVED 상태가 됩니다.

  3. 클라이언트는 서버에게 ACK을 보낸 후부터 연결이 이루어지고 데이터가 오가게 되는 것입니다. 이 때 서버 상태는 ESTABLISHED가 됩니다.

     4-way handshake 과정은

  4. 클라이언트가 연결을 종료하겠다는 FIN Flag를 전송합니다.

  5. 서버에서는 FIN 패킷을 정상적으로 받았다는 ACK를 클라이언트에 전송해줍니다. 그 후 서버는 CLOSE-WAIT 상태로 빠져듭니다.

  6. 연결을 종료한 후 서버는 클라이언트에게 FIN flag를 전송합니다.

  7. 서버로부터 전송된 FIN Flag를 받은 클라이언트는 확인을 알리는 ACK를 서버로 전송한 후, 일정 시간동안 TIME-WAIT 상태에 빠지게 된다.

  8. 클라이언트로부터 ACK을 받은 서버는 소켓을 Close하고 두 TCP간의 세션이 종료된다.

  9. TIME-WAIT에 빠진 클라이언트는 서버로 부터 FIN을 수신하더라도, 일정시간 동안 세션을 유지하며 도착하지 않은 패킷을 기다린다.

3. HTTP와 HTTPS의 차이점에 대해서 설명해보세요.

• 답

  HTTP는 암호화가 추가되지 않았기 때문에 보안에 취약한 반면, HTTPS는 안전하게 데이터를 주고받을 수 있습니다. 하지만 HTTPS를 이용하면 암호화/복호화의 과정이 필요하기 때문에 HTTP보다 속도가 느립니다.(오늘날에는 거의 차이를 못느낄 정도이다.) 또한 HTTPS는 인증서를 발급하고 유지하기 위한 추가 비용이 발생합니다.

  개인 정보와 같은 민감한 데이터를 주고 받아야 한다면 HTTPS를 이용해야 하지만, 단순한 정보 조회 등만을 처리하고 있다면 HTTP를 이용하면 됩니다.

  [MangKyu's Diary]

  https://mangkyu.tistory.com/98