Computer Science20 [Algorithm] 버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort) 두 개의 인접한 요소를 비교하고 필요한 경우 위치를 교환(Swap)하여 리스트를 정렬합니다. 버블 정렬은 모든 요소를 탐색하며 정렬 조건(오름차순, 내림차순 등)에 해당하는 요소가 가장 뒤로 이동할 때까지 반복됩니다. 정렬 시 거품이 올라오는 것처럼 보여 버블 정렬이라고 이름이 지어졌습니다. 출처 예제 먼저 다음과 같이 정렬되지 않은 배열이 있다고 가정하겠습니다. 위 배열을 오름차순으로 정렬하기 위한 버블 정렬 알고리즘은 다음과 같이 동작합니다. 첫 번째 인덱스부터 시작하여 첫 번째 요소와 두 번째 요소를 비교합니다. 첫 번째 요소가 두 번째 요소보다 크면 교체됩니다. 마지막 요소에 도달할 때까지 이전 절차가 반복됩니다. 첫 번째 인덱스부터 시작하여 첫 번째 요소와 두 .. 2023. 10. 17. [Data] 우선순위 큐(Priority Queue) Priority Queue 우선순위 큐는 데이터를 저장하는 자료구조 중 하나로 각 요소에 우선순위를 할당하고 그 우선순위에 따라 요소들을 정렬하는 자료구조입니다. 우선순위가 가장 높은 요소가 항상 첫번째 인덱스에 위치해 있으며 삽입 시점에 상관없이 가장 먼저 제거됩니다. 또한 두 요소의 우선순위가 동일한 경우 순서에 따라 제거됩니다. Heap 힙이란 각 노드의 값이 특정한 우선순위 규칙을 따르는 자료구조입니다. 힙은 이진 트리로 구성되며 각 노드는 최대 두개의 자식 노드를 가질 수 있습니다. 일반적으로 힙은 보통 완전 이진 트리의 형태를 가지며 왼쪽부터 차례대로 노드가 채워집니다. 최소 힙 출처 각 노드의 값은 그 자식 노드의 값보다 작거나 같은 힙으로 루트 노드가 가장 작은 값을 가집니다. 최대 힙 출.. 2023. 9. 7. [CS] 내부 기억장치(Internal Memory)(1) 기억장치 기억장치의 분류와 특성 CPU가 어떤 정보를 기억장치에 쓰거나 기억장치로부터 읽는 동작을 액세스(access)한다고 말하는데 액세스 유형은 일반적으로 다음과 같이 분류됩니다. 순차적 액세스(sequential access): 기억장치에 젖아된 정보들을 처음부터 순서대로 액세스합니다. 자기 테이프(magnetic tape) 저장장치가 이방식을 이용하는데 저장되는 모든 정보는 테이프의 처음 위치에서 시작하여 연속적으로 위치하게 됩니다. 그 내용들은 내부적으로 레코드(record)라고 불리는 정보 단위로 분리되어 저장되고 각 레코드는 고유의 주소를 가집니다. 테이프 내 임의의 위치에 저장된 특정 정보를 읽기 위해서는 그위치에 도달할때까지 앞부분의 테이프를 모두 통과해야합니다. 따라서 정보가 저장된 위.. 2023. 8. 16. [Network] 트랜스포트 계층(Transport Layer)(4) 연결지향형 트랜스포트: TCP 혼잡 제어에 대한 접근법 실제로 TCP가 혼잡 제어를 수행하는 두 가지 광범위한 접근 방식이 있습니다. 가장 크게 보면 네트워크 계층이 혼잡 제어를 목적으로 트랜스포트 계층에 어떤 직접적인 도움을 제공하는지에 따라 혼잡 제어 접근을 구별할 수 있습니다. 종단 간의 혼잡 제어: 혼잡 제어에 대한 종단 간의 접근 방식에서 네트웤 ㅡ계층은 혼잡 제어 목적을 위해 트랜스포트 계층에게 어떤 직접적인 지원도 제공하지 않습니다. 네트워크에서 혼잡의 존재는 단지 관찰된 네트워크 동작에 기바초하여 종단 시스템이 추측해야합니다. IP 계층은 네트워크 혼잡에 관해 종단 시스템에게 어떠한 피드백 제공도 요구받지 않으므로 TCP가 혼잡 제어를 위한 종단 간의 접근 방식을 취합니다. TCP 세그먼트.. 2023. 8. 15. [Network] 트랜스포트 계층(Transport Layer)(3) 연결지향형 트랜스포트: TCP 흐름 제어 TCP 연결의 각 종단에서 호스트들은 연결에 대한 개별 수신 버퍼를 설정합니다. TCP 연결이 순서대로 올바르게 바이트를 수신할 때 TCP는 데이터를 수신 버퍼에 저장합니다. TCP는 송신자가 수신자의 버퍼를 오버플로시키는 것을 방지하기 위해 애플리케이션에게 흐름 제어 서비스(flow-control service)를 제공합니다. 흐름 제어는 속도를 일치시키는 서비스로 수신하는 애플리케이션이 읽는 속도와 송신자가 전송하는 속도를 같게 합니다. 송신자 제어의 이 형태는 혼잡 제어(congestion control)이라 부릅니다. TCP는 송신자가 수신 윈도(receive window)라는 변수를 유지하여 흐름 제어를 제공합니다. 수신 윈도는 수신 측에서 가용한 버퍼 .. 2023. 8. 14. [Network] 트랜스포트 계층(Transport Layer)(2) 연결지향형 트랜스포트: TCP TCP가 신뢰적인 데이터 전송을 제공하기 위해 오류 검출, 재전송 누적 확인응답, 타이머, 순서 번호와 확인응답 번호를 위한 헤더 필드를 포함한 방법을 설명하겠습니다. TCP 연결 TCP는 애플리케이션 프로세스가 데이터를 다른 프로세스에게 보내기 전에 두 프로세스가 서로 '핸드셰이크'를 먼저 해야하므로 연결지향형(connection-oriented)입니다. 즉 데이터 전송을 보장하는 파라미터들을 각자 설정하기 위한 어떤 사전 세그먼트들을 보내야합니다. TCP 포로토콜은 오직 종단 시스템에서만 동작하고 중간의 네트워크 요소(라우터와 링크 계층 스위치)에서는 동작하지 않으므로 중간의 네트워크 요소들은 TCP 연결 상태를 유지하지 않습니다. (중간 라우터들은 이들의.. 2023. 8. 12. [Network] 트랜스포트 계층(Transport Layer)(1) Transport Layer 트랜스포트 계층 프로토콜은 각기 다른 호스트에서 동작하는 애플리케이션 프로세스간의 논리적 통신(logical communication)을 제공합니다. 논리적 통신은 애플리케이션 관점에서 보면 프로세스들이 동작하는 호스트들이 직접 연결된 것처럼 보인다는 것을 의미합니다. 또한 트랜스포트 계층은 프로토콜은 네트워크 라우터가 아닌 종단 시스템에서 구현됩니다. 트랜스포트 계층 세그먼트라고 알려진 트랜스포트 계층 패킷으로 변환되어 네트워크 계층 패킷(데이터그램) 안에 캡슐화되어 목적지로 전달됩니다.(라우터는 데이터그램 안에 캡슐화된 트랜스포트 계층 세그먼트의 필드를 검사하지 않습니다.) 이 후 수신 애플리케이션의 트랜스포트 계층에서 세그먼트 내부의 데이터를 이용할 수 있도록 수신된 세.. 2023. 8. 11. [CS] 유니코드(Unicode) & 인코딩(Encoding) Unicode 유니코드는 다양한 언어와 문자를 컴퓨터에서 표현하기 위해 탄생했습니다. 예를 들어 영어와 같은 알파벳 기반 언어의 문자는 아스키(ASCII)라는 문자 인코딩을 통해 1 byte(8 bit)만을 사용해 표현할 수 있지만, 다른 언어의 문자들은 1 byte로 표현할 수 없었습니다. 이로 인해 언어 간 데이터 교환, 다국어 텍스트 처리, 국제화 및 로컬라이제이션 작업 등에서 어려움이 발생했습니다. 전 세계의 다양한 언어와 문자를 효과적으로 표현하고 처리하기 위해서는 통일된 표준이 필요했고 이런 필요성을 해결하기 위해 유니코드가 등장하게 되었습니다. 1991년 처음으로 유니코드는 발표되었고 초기에는 16 bit로 최대 65,536개의 문자를 표현할 수 있는 UCS-2라는 인코딩 방식을 사용했습니다.. 2023. 8. 8. [CS] CPU의 구조와 기능(2) CPU의 구조와 기능 명령어 파이프라이닝 CPU 성능은 컴퓨터 시스템의 프로그램 처리 시간에 직접 영향을 주기 때문에, 그 속도를 향상시키기 위하여 여러 가지 방벙들이 사용되고 있습니다. 그 중에서 가장 간단하면서도 분명한 효과를 얻을 수 있는 방법이 명령어 파이프라이닝(instruction pipelining) 입니다. 이것은 명령어를 실행하는데 사용되는 하드웨어를 여러 개의 독립적인 단계(stage)들로 분할하고, 그들로 하여금 동시에 서로 다른 명령어들을 처리하도록 함으로써 CPU의 성능을 높여주는 기술을 말합니다. 명령어 파이프라인은 분할되는 단계의 수가 많아질수록 처리 속도가 높아지는데, 최근에는 CPU의 속도를 더욱 높이기 위하여 여러 개의 명령어 파이프라인들을 설치하기도합니다. 2-단계 명령.. 2023. 8. 8. 이전 1 2 3 다음
