CS관련 도움이 된 강의와 포스트

jiholee·2021년 12월 25일
8

cs

목록 보기
1/7

양질의 무료 강의


틀린게 있을 수 있습니다. 틀린것이 있다면 댓글로 알려주세요 🙇‍♀️


이진 트리에서 전위 순회를 언제 사용하는가?

한 서버에서 트리 구조를 그대로 다른 서버에 전송하고 싶을 때
트리를 전위 순회 (parent -> left -> right)로 바이트 스트림으로 전환 -> 다른 서버에 보낸다 -> 다시 트리 구조를 형성하면 이전과 똑같이 복원된다😆

이진 트리에서 중위 순회를 언제 사용하는가?

이진 트리에서 in order traversal (left -> parent -> right) 방식을 사용하면 O(n)의 시간 복잡도로 저장된 자료의 정렬된 상태를 얻을 수 있다.

이진 트리에서 후위 순회 사용

트리를 삭제할 때 사용할 수 있다.

ox퀴즈

📌 대부분이 정렬되어 있는 경우 삽입정렬을 사용하는 것이 좋다. (o)

삽입 정렬의 가장 큰 장점은 필요한 경우에만 배열을 정렬한다는 점이다. 배열이 정렬되어 있으면 전혀 이동할 필요가 없다. 따라서 대부분의 데이터가 이미 정렬되어 있는 경우에 많이 사용된다. 고성능 알고리즘들 중에서는 배열의 사이즈가 클때 O(nlogn) 알고리즘을 쓰다가 정렬해야 할 부분이 작을때 삽입 정렬로 전환하는 것들도 있다. ex) 파이썬 팀 소트 - 병합정렬 + 삽입정렬

삽입정렬 소스코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복
        if array[j] < array[j - 1]:
            array[j] , array[j - 1] = array[j - 1], array[j]
        else:
            break
print(array)

📌 비교 정렬의 경우 nlogn 보다 빠를 수 없다. (o)

📌 병합정렬의 성능은 퀵 정렬보다 전반적으로 떨어지고, 메모리가 더 필요하지만 안정 정렬이다 (o)

📌 힙정렬은 추가적인 메모리가 필요하지 않고 항상 nlogn 성능이다. (o)

📌 배열의 크기가 커서 메인메모리에 모든 데이터를 한번에 적재할 수 없는 경우 머지정렬(Merge Sort)을 사용할 수 있다. (o)

📌 이진검색트리(Binary Search Tree)를 구성했을때 검색연산의 시간복잡도는 O(N)이 될 수 있다. (o)

한쪽으로만 계속 늘어지는 극단적인 구조를 가지게 될 경우 -> 스스로 균형을 잡는 이진 탐색 트리의 필요성을 느낄 수 있다.(avl, 레드-블랙 트리)

📌 Max-Heap을 구성했을때, 최대값을 구하는 연산의 시간복잡도는 O(logN)이다. (x, O(1))

📌 c의 구조체와 c++의 클래스의 다른점으로는 구조체의 디폴트 접근권환은 public, 클래스는 private이다 (o)

📌 ip는 비연결지향적이며 신뢰할 수 없다. (o)

📌 ssl 은 전송계층에 속한다. (x, 응용계층과 전송계층 사이에 독립적인 프로토콜 계층이다.)

📌 https는 대표적인 비대칭키를 이용하는 방식으로 대칭키 암호화를 사용하지 않기 때문에 빠른 데이터 교환이 가능하다. (x)

https는 비대칭키와 대칭키를 모두 사용해서 빠른 데이터 교환이 가능하다.

📌 Hash 암호화 알고리즘은 사용자의 비밀번호를 취급할 때 사용되기도 하며 빠른 복호화가 장점이다. (x)

비밀번호를 취급할 때 사용된다. 해시는 복호화를 할 수 없다.

📌 배열과 해시는 랜덤접근이 가능하다 (o)

📌 이분 탐색은 정렬되어 있지 않아도 된다. (x)

이분탐색은 정렬되어 있을 때만 사용 가능하다.

IPC(Inter Process Communication)

프로세스는 독립적으로 실행된다. 독립되어 있으므로 다른 프로세스에게 영향을 받지 않는다. 독립적인 프로세스 간의 통신을 해야 할 때 IPC 통신을 사용한다.

✔️ 익명 PIPE

부모-자식 프로세스 간 통신
파이프는 두 개의 프로세스를 연결하는데 하나의 프로세스는 데이터를 쓰기만 하고, 다른 하나는 데이터를 읽기만 할 수 있다.

한쪽 방향으로만 통신이 가능한 반이중 통신이라고도 부른다.

따라서 양쪽으로 모두 송/수신을 하고 싶으면 2개의 파이프를 만들어야 한다.

✔️ Named PIPE

익명 파이프는 통신할 프로세스를 명확히 알 수 있는 경우에 사용한다. (부모-자식 프로세스 간 통신처럼)

Named 파이프는 전혀 모르는 상태의 프로세스들 사이 통신에 사용한다.

즉, 익명 파이프의 확장된 상태로 부모 프로세스와 무관한 다른 프로세스도 통신이 가능하다

하지만, Named 파이프 역시 읽기/쓰기 동시에 불가능함. 따라서 전이중 통신을 위해서는 익명 파이프처럼 2개를 만들어야 한다.

✔️ 공유 메모리

파이프, 메시지 큐가 통신을 이용한 설비라면, 공유 메모리는 데이터 자체를 공유하도록 지원하는 설비다.
공유 메모리는 프로세스간 메모리 영역을 공유해서 사용할 수 있도록 허용해준다.

프로세스가 공유 메모리 할당을 커널에 요청하면, 커널은 해당 프로세스에 메모리 공간을 할당해주고 이후 모든 프로세스는 해당 메모리 영역에 접근할 수 있게 된다.

✔️ 소켓

네트워크 소켓 통신을 통해 데이터를 공유한다.

클라이언트와 서버가 소켓을 통해서 통신하는 구조로, 원격에서 프로세스 간 데이터를 공유할 때 사용한다.

서버(bind, listen, accept), 클라이언트(connect)

이러한 IPC 통신에서 프로세스 간 데이터를 동기화하고 보호하기 위해 세마포어와 뮤텍스를 사용한다. (공유된 자원에 한번에 하나의 프로세스만 접근시킬 때)

I/O Multiplexing

I/O Multiplexing 대두

네트워크 프로그램을 그냥 구현하다보면, I/O 블럭킹이 발생해서 다수의 클라이언트들과 연결할 수 없거나 성능 저하를 겪게 된다.

이를 해결하기 위한 방법 몇가지는 아래와 같다.

  • Fork : 클라이언트 요청이 있을때마다 프로세스를 복사하여 여러 사용자에게 서비스를 제공.
  • Threads : 프로세스 방법이 아닌 쓰레스를 생성해서 여러 사용자들에게 서비스를 제공.
  • I/O Multiplexing : 여러 소켓에 대해 I/O를 병행적으로 하는 기법. 다수의 프로세스 혹은 스레드를 만들지 않고도 여러 파일을 처리할 수 있기 때문에 less memory, less context switching이 가능해 성능 개선됨.
  • 비동기 I/O : I/O가 비동기적으로 처리되는 기법. 시그널이 병행되어 존재함.
  • Event Driven I/O : I/O multiplexing을 추상화함. libev, pyev, libevent 라이브러리가 있음.

이중에서 I/O Multiplexing 구현하기 위한 시스템 호출로 select, poll, epoll, kqueue등이 구현되어 있다.

I/O Multiplexing 기능은 프로그램에서 여러 파일 디스크립터(소켓)를 모니터링해서 어떤 종류의 I/O 이벤트가 일어났는지 파악하고 각각의 파일 디스크립터가 Ready 상태가 되었는지 인지하는게 주요 목적이다.

  1. select
  • 등록된 file descriptor를 하나하나 체크를 해야하고 커널과 유저 공간 사이에 여러번의 데이터 복사가 있음.
  • 관리 file descriptor 수에 제한이 있음.
  • 사용 쉽고 지원 OS가 많아 이식성 좋음.

file descriptor를 하나 하나에 체크하기 때문에 O(n)의 계산량이 필요하다. 따라서 관리하는 file descriptor의 수가 증가하면 성능이 떨어진다. 또한 관리 수가 한정되어 있기 때문에 그 수를 초과하면 사용할 수 없다.

  1. poll

poll은 거의 select와 동일하지만 다음과 같은 차이가 있다.

  • 관리 file descriptor 무제한.
  • 좀더 low level의 처리로 system call의 호출이 select보다 적음.
  1. epoll

linux커널 2.6.x이상 버전에만 지원되고 특징은 다음과 같다.

  • 관리 fd의 수는 무제한.
  • select, poll과 달리, fd의 상태가 kernel 에서 관리됨.
  • 일일이 fd 세트를 kernel 에 보낼 필요가 없음.
  • kernel이 fd를 관리하고 있기 때문에 커널과 유저스페이스 간의 통신 오버헤드가 대폭 줄어듬.
  1. kqueue

BSD 계열(유닉스)의 epoll


참고 사이트

1개의 댓글

comment-user-thumbnail
2022년 6월 18일

퍼갑니다 잘쓸게요 ^^

답글 달기