5장 컴퓨터 과학61 [알고리즘] 퀵 정렬(Quick Sort) 퀵 정렬은 병합 정렬과 마찬가지로 분할과 정복 패러다임에 기반하고 있지만 모든 힘든 작업이 재귀 호출 앞에 행해지기 때문에 다소 정반대의 방법이다. 분할과 정복 분할과 정복 패러다임은 다음의 세 단계로 이루어진 일반적인 용어로 설명될 수 있다. 분할(Divide): 배열이 적어도 2개의 원소를 갖고 있다면 배열로부터 피봇(pivot)이라고 불리는 특정한 원소 x를 선택한다. 일반적으로 배열의 마지막 원소를 피봇 x로 선택한다. 배열로 부터 모든 원소를 삭제하여 이들을 세 개의 배열에 넣는다. 세 배열은 각각 x보다 작은 원소(L), x와 같은 원소(E), x보다 큰 원소(G)가 저장된다. 재귀(Recur): 재귀적으로 시퀀스 L과 G를 정렬한다. 정복(Conquer): 먼저 L의 원소, 다음 E의 원소,.. 2021. 6. 16. [알고리즘] 병합 정렬(Merge Sort) 병합 정렬은 재귀적으로 배열을 분할하여 정렬하고 다시 합병한다. 이를 분할과 정복 패러다임이라고 한다. 분할과 정복 분할과 정복 패러다임은 다음의 세 단계로 이루어진 일반적인 용어로 설명될 수 있다. 분할(Divide): 입력의 크기가 특정한 임계값보다 작다면 간단한 메소드를 사용하여 직접 문제를 풀고, 얻어진 답을 반환한다. 그렇지 않으면, 입력 데이터를 둘 이상의 분리된 부분 집합으로 분할한다. 재귀(Recur): 부분 집합에 연관된 부분 문제를 재귀적으로 푼다. 정복(Conquer): 부분 문제에 대한 답을 구해 본래 문제의 답으로 병합한다. C++ 구현 template void merge_sort(RandomIt first, RandomIt last) { if (first + 1 == last) .. 2021. 6. 16. [컴퓨터 네트워크] 응용 계층 응용 계층은 OSI 참조모델과 TCP/IP 모델의 최상위 계층으로 파일관리 및 전송 같은 응용 처리를 위한 프로세서 사이의 인터페이스 기능을 담당한다. 응용 계층은 데이터통신을 위한 응용 기능으로 가상 단말, 원격 데이터베이스, 메일함 접근 등의 자원이용 기능과 네트워크 운영에 필요한 네트워크 관리 기능 등을 제공한다. 응용 계층에 해당하는 프로토콜 및 서비스에는 FTP(File Transfer Protocol, 파일 전송 프로토콜), SMTP(Simple Mail Transfer Protocol, 간이 이메일 전송 프로토콜), DHCP(Dynamic Host Configuration Protocol, 동적 호스트 구성 프로토콜), HTTP(Hypertext Transfer Protocol, 하이퍼텍스트.. 2021. 6. 16. [컴퓨터 네트워크] UDP와 SCTP UDP의 구조와 특성 TCP가 비효율적인 경우도 있다. 실시간성을 중요시하거나 응답성을 중요시하는 프로그램이 대표적인데 이런 경우를 위해 개발된 것이 사용자 데이터그램 프로토콜인 UDP(User Datagram Protocol)이다. UDP는 오버헤드를 최소화한 매우 간단한 구조로 TCP보다 전송속도가 빠르다. UDP는 비연결성 프로토콜로 데이터 전송의 신뢰성을 보장하지 않으며 IP 서비스에 단지 프로세스 대 프로세스 데이터통신 환경만 제공한다. 다시 말해 데이터를 주고받을 때 TCP처럼 연결설정 단계를 거치지 않고 전송지에서 일방적으로 데이터를 전송하며 수신 여부도 확인하지 않는다. 흐름제어와 혼잡제어도 처리하지 않으므로 네트워크 부하가 적고, 체크섬도 최소한의 오류만 검출하도록 선택적으로 수행한다. .. 2021. 6. 16. [컴퓨터 네트워크] TCP의 혼잡제어 혼잡제어의 개념 혼잡제어란 네트워크로 유입되는 데이터 트래픽의 양이 네트워크 용량을 초과하지 않도록 유지하는 것이다. 데이터 총량이 네트워크가 처리할 수 있는 허용량을 초과하면 네트워크는 혼잡 상태가 된다. 그림에서 가로축은 사용자 트래픽의 양을 세로축은 네트워크 지연시간을 나타낸다. 사용자 트래픽 양이 네트워크 용량보다 충분히 적으면 지연 시간이 크지 않지만 네트워크 용량에 접근해가면 지연 시간이 급증한다는 것을 알 수 있다. 이와 같은 혼잡 상태는 네트워크 성능을 현저히 떨어뜨리고 결국 네트워크 기능을 마비시킨다. 따라서 네트워크 혼잡 상태를 방지하려면 혼잡제어 기능이 필요하다. TCP 혼잡제어의 원리 일반적으로 TCP는 느린 출발 알고리즘과 혼잡회피 알고리즘을 기반으로 혼잡제어를 수행한다. 다시 말.. 2021. 6. 16. 이전 1 2 3 4 5 ··· 13 다음 반응형
