CS

최장 증가 수열 (LIS, Longest Increasing Subsquence)

최장 증가 수열, 정확히 최장 증가 부분 수열은 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분수열을 의미한다.이 때, 부분 수열의 각 수는 서로 연속할 필요는 없다.아래의 예시 수열을 보자. 위 수열에서 최장 증가 수열을 찾으면 아래와 같다. 그림에서 붉은 칸으로 칠해진 부분 수열 (1, 2, 3, 6, 7, 9) 는 전체 수열 중 오름차순으로 증가하는 가장 긴 부분수열이다.이제 주어진 수열에서 LIS의 길이를 구하는 두 가지 방법을 알아보자.다이나믹 프로그래밍을 이용한 방법 : O(N^2)이러한 최장 증가 수열을 찾는 가장 단순한 방법은 완전 탐색일 것이다.하지만 수열에 존재하는 수의 개수가 k개일 때, 1개 이상의 원소를 갖는 모든 부분수열의 가짓수는 2^k개이므로, 모든 부분수열을 확인해 이들..

소켓 입출력 모델 - Overlapped 모델

Overlapped 모델완료 루틴을 통해 비동기 입출력 결과를 처리한다.완료루틴 - 애플리케이션이 정의한 일종의 콜백함수로 운영체제가 적절한 시점에 자동으로 호출하도록 되어 있다.동작 원리비동기 입출력 함수를 호출함으로써 운영체제에 입출력 작업을 요청한다.해당 스레드는 곧바로 alertable wait 상태로 진입한다비동기 입출력 작업이 완료되면, 운영체제는 스레드의 APC 큐에 결과를 저장한다비동기 입출력 함수를 호출한 스레드가 alertable wait 상태에 있으면, 운영체제가 APC 큐에 저장된 정보를 참조하여 완료 루틴을 호출한다 APC 큐에 저장된 정보를 토대로 모든 완료 루틴 호출이 끝나면, 스레드는 alertable wait 상태에서 빠져나온다APC Queue (Asynchronous Pr..

DoS 및 DDoS 정리

서비스 공격 거부 (DoS, Denial of Service) 1. 정의 : 공격 대상 시스템이 정상적인 서비스를 할 수 없도록 만드는 공격 2. 목적 : 가용성 저하 3. 주요 공격 : SYN Flooding Attack, 스머프 공격(Smurf Attack) 등 4. 스머프 공격(Smurf Attack), 스머핑(Smurfing)  1) 희생자의 스푸핑(Spoofing)된 원본 IP로 브로드캐스팅 방식으로 ICMP(Internet Control Message Protocol) 패킷 전송  2) 전달받은 시스템들은 원본 IP로 ICMP 응답 메시지 전송  3) 희생자 시스템은 ICMP 트래픽 과부화로 정상적인 서비스 불가능  ※ IP Spoofing : 네트워크의 취약점을 이용하여 해커가 자신의 IP를..

동적테스트 화이트박스 테스트 검증기준 (WhiteBox Test Coverage)

1) 문장 검증 기준 (Statement Coverage)문장 1회모든 문장이 한 번 실행된다. 2) 분기 검증 기준 (Decision Coverage)T/F분기점은 조건문에서의 각 분기 또는 논리적 분기 지점을 나타내고, 각 분기는 프로그램의 특정 경로를 나타내며, 조건문의 참/거짓에 따라 결정된다.모든 코드 분기가 테스트 되었을 때 100%의 분기 커버리지가 달성된다. 3) 조건 검증 기준 (Condition Coverage)TF, FT각 조건이 참과 거짓으로 평가되는 모든 가능한 경우를 테스트한다.각 조건이 최소한 한 번은 참으로, 한 번은 거짓으로 평가되도록 한다. 4) 분기/조건 기준 (Condtion Decision Coverage)TT, FF프로그램의 모든 분기점이 최소한 한 번 실행되었는지..

서브넷, 서브넷마스크, 서브넷팅

서브넷 (Subnet)IP 주소 공간을 더 작은 네트워크로 분할하는 기술이다 IP 주소 공간을 서브넷으로 분할하면 네트워크를 효율적으로 관리하고, 더 많은 호스트들을 지원하거나 보안을 강화할 수 있다.서브넷 마스크 (Subnet Mask)주어진 IP 주소를 네트워크 환경에 맞게 나누어 주기 위해서 씌어주는 이진수의 조합이다.서브넷을 만들 때 사용되는 것으로 IP 주소에는 반드시 서브넷 마스크가 있는데, 이 서브넷 마스크를 이용하여 IP주소에서 Network ID와 Host ID를 분리할 수 있다.서브넷팅 (Subnetting)네트워크를 더욱 작은 단위의 네트워크로 분할하는거다 IP주소의 낭비를 방지하고 브로드캐스트 도메인의 크기를 줄여서 성능을 향상하는 것이 주된 목적이다.예를 들어 당신이 192.167..

OSI 7계층 개념 정리

OSI (Open System Interconnection) 7계층은 국제 표준화 기구인 ISO (International Standardization Organization)에서 개발한 컴퓨터 네트워크 프로토콜 디자인과 통신을 계층으로 나누어 설명한 개방형 시스템 상호 연결 모델이다.AH : Application HeaderPH : Presentation HeaderSH : Session HeaderTH : Transport HeaderNH : Network Header / NT : Network TailDH : Data Link Header / DT : Data Link Tail계층을 지날 때마다 헤더(Header)가 붙는데, 이것은 해당 계층의 기능과 관련된 제어 정보가 포함 되어 있다.제어 정보들..

IaaS, PaaS, SaaS 차이

IaaS, PaaS, 및 SaaS는 클라우드 컴퓨팅 모델을 나타내는 서비스 유형이다.차이점은 각각 다른 수준의 관리와 책임을 제공하고, 사용자가 원하는 만큼의 제어와 유연성을 제공한다.SaaS는 소프트웨어 기반 서비스PaaS는 플랫폼 기반 서비스IaaS는 인프라 기반 서비스IaaS Infrastructure as a ServiceIaaS는 가장 기본적인 클라우드 서비스 모델로, 가상화된 컴퓨팅 리소스(가상 머신, 스토리지, 네트워킹 등)를 제공하는 것이다.사용자는 여기에 운영체제부터 응용프로그램, 데이터 등 전반적인 관리 책임을 갖게 된다. IaaS는 기본 인프라를 프로비저닝(IT 인프라를 설정하는 프로세스)하고 관리하는 데 필요한 컨트롤을 제공하면서도 하드웨어와 물리적 자원에 대한 걱정을 줄여준다.ex..

SRT, SJF 스케줄링 알고리즘 문제

5개의 작업에 대한 도착 시간과 CPU 사이클 시간이 아래표와 같다고 다음 물음에 답하시오위에서 SRT, SJF 스케줄링 알고리즘을 적용할 경우 평균 대기시간과 반환시간을 구하시오. A)선점형 스케줄링은 하나의 프로세스가 cpu를 점유하고 있을 때 작업중인 프로세스를 중단시킬 수 있는 방식으로 srt가 여기에 속한다.비선점형 스케줄링은 하나의 프로세스가 cpu를 점유하고 있을 때 작업중인 프로세스를 중단시킬 수 없는 방식으로 sjf가 여기에 속한다. SRT 방식남아있는 도착 시간이 가장 짧은 작업을 먼저 처리한다. 위의 그림을 보면 a가 먼저 시작이 되므로 1을 처리하고 a의 남은 시간은 5가 된다.b가 들어오는데 a보다 b가 남은 시간이 짧으므로 a는 대기 상태가 되고 b가 처리된다. b가 1을 처리하..

BGP (Border Gateway Protocol)

개념사실 모든 BGP 프로토콜이 서로 다른 AS들을 연결해주는 것은 아니다. Border Gateway Protocol의 이름에서 알 수 있듯이, AS의 가장 자리에 위치한 BG (Border Gateway)들 간의 프로토콜이다, 물론 다른 AS들에 속한 BG간의 연결에도 관여하지만, 같은 AS 내의 BG 간의 연결에도 관여한다. 이러한 역할의 차이에 따라 BGP는 크게 두 가지로 구분할 수 있다.1) iBGP서로 같은 AS 상의 Border Gateway들 끼리의 연결을 담당하는 BGP 2) eBGP서로 다른 AS 상의 Border Gateway들 끼리의 연결을 담당하는 BGP, inter-AS 라우팅이다.역할서로 다른 AS에 존재하는 IP주소로도 쉽게 패킷을 전달할 수 있는것이 다 BGP 때문이다. ..

라우팅 Routing

라우팅 기능과 주요 프로토콜 이해간단한 라우팅 프로토콜거리-벡터 프로토콜링크 상태 프로토콜외부 라우팅 프로토콜최단 경로 라우팅거리 기준은 다양하지만 중간에 거치는 홉(hop) 수로 판단패킷이 목적지로 가는 동안 거치는 라우터 수가 최소가 되도록 경로를 선택a > d로 가려면 a-b-d 경로 선택, a > g로 가려면 a-c-g 경로 선택기타 거리 기준) 패킷의 전송 지연, 전송 대역폭, 통신 비용 등플러딩 (Flooding)입력된 패킷을 라우터가 출력 가능한 모든 경로로 중개하는 방식확실하게 전달할 수 있다는 장점이 있지만 네트워크에 패킷이 무한 개 만들어질 위험이 있음홉 수를 일정 범위로 제한하고 제거하는 방식으로 대처 가능중요한 데이터를 모든 호스트에게 동시에 전달하는 환경에서 제한적으로 사용거리-벡..