블루휴고 스토어

블루휴고

개인인증

팔로워3 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

12개
전체 판매량

101개
최근 3개월 판매량

17개
자료후기 점수

평균A+
자료문의 응답률

100%

전체자료 12개

행정고시(5급공채) 전산직 OS(운영체제) 합격자 서브노트 평가A+최고예요

Chapter 1. 서론(Introduction)1.1 운영체제가 할 일o 컴퓨터 시스템의 구성 요소- 하드웨어, 운영체제, 응용 프로그램, 사용자o 하드웨어의 구성 요소 - CPU, 메모리, I/O 장치o 사용자 관점, 시스템 관점o 운영체제의 정의1.2 컴퓨터 시스템의 구성1.2.1 컴퓨터 시스템 연산(Computer-System Operation)o 공통 버스에 연결된 여러 개 장치 제어기와 하나 이상의 CPU, 메모리 제어기o 초기 프로그램(bootstrap program)- 펌웨어(ROM 또는 EEPROM)에 저장- 커널을 찾아 메모리에 적재, init 프로세스 실행, 이벤트 기다림o 인터럽트, 시스템 콜 - 인터럽트 서비스 루틴 실행 방식1.2.2 저장 장치 구조(Storage Structure)o 프로그램과 자료가 주 메모리에 영원히 존재하지 못하는 이유- 1. 주 메모리는 너무 작다. 2. 주 메모리는 휘발성이다- 따라서 보조 저장 장치가 필요하다o 저장 장치 계층 - 속도, 가격, 크기, 휘발성의 차이1.2.3 입/출력 구조(I/O Structure)o 장치 제어기(device controller)- 공통 버스에 연결된 각 장치 제어기가 특정 유형의 장치를 담당- 한 장치 제어기에 하나 이상의 장치가 부착될 수도 있음(ex. SCSI 제어기의 경우 7개의 장치를 붙일 수 있음)- 지역 버퍼 저장 장치, 특수 목적용 레지스터 집합- 지역 버퍼 저장 장치와 주변 장치간의 자료 전송을 담당- 운영체제는 각 장치 제어기마다 장치 드라이버를 가짐o 장치 제어기의 입/출력 방식- 인터럽트 방식: 소량에는 문제없으나, 대량의 경우 높은 오버헤드- 직접 메모리 접근(DMA) : CPU의 개입 없이 장치 제어기의 버퍼 장치와 메모리 간 자료 블록 단위로 전송1.3 컴퓨터 시스템의 구조1.3.1 단일 처리기 시스템(Single-Processor System)o 하나의 주 CPU와 여러 전용 처리기o 전용 처리기의 존재는 CPU의 오버헤드를 감소시킴(ex. 디스크널 프로그램을 위한 영역을 포함- 커널 스택: 프로세스가 커널 모드에 있는 동안 수행한 호출과 복귀를 관리- 공유 주소 공간: 운영체제 코드와 데이터가 공유 주소 공간에 있어서 모든 사용자 프로세스에 의해 공유됨3. 프로세스 기반 운영체제 (Process-based OS)o 운영체제를 시스템 프로세스들의 집합으로 구성- 장점1: 각 모듈 간에 최소의 명료한 인터페이스를 가진 모듈화된 운영체제를 사용하여 프로그램 설계 원칙에 충실- 장점2: 중요하지 않은 기능을 개별 프로세스로 쉽게 구현- 장점3: 다중처리기나 다중컴퓨터 환경에서 유용 (운영체제의 몇 가지 서비스를 지정된 처리기에서 수행하여 성능 향상)☞ 키워드 정리① Nonprocess Kernel: 분리된 개체, 특권 모드, 전통적② Within User Process: 모드 전환, 커널 스택, 공유 주소 공간③ Process-Based: 모듈화, 개별 프로세스, 다중처리기Chapter 4. 쓰레드(Thread)4.1 개요(Overview)쓰레드o 쓰레드는 CPU 이용의 기본 단위 (LWP, Lightweight Process)- 공유: 코드, 데이터, 자원(파일 등)- 개별: 쓰레드 ID, PC, 레지스터 집합, 스택Stallings※ 프로세스가 가지는 2가지 특성1. 자원 소유권 (프로세스 이미지, 입출력 장치, 파일 등)2. 스케줄링/수행☞ 두 가지 특성은 운영체제에 의해 독립적으로 취급될 수 있다!o 다중쓰레딩(Multithreading): 운영체제가 하나의 프로세스 내에서 수행되는 여러 개의 쓰레드를 지원하는 기능 (Stallings)4.1.1 동기(Motivation) - (쓰레드 사용 예시)몇 개의 제어 쓰레드를 가진 프로세스의 예시o 웹브라우저: 이미지/텍스트 표시 + 네트워크에서 자료 수신o 워드프로세서: 그래픽 표시 + 키보드 입력 + 문법 체크o 웹서버: 여러 개의 클라이언트 요청을 받아들임⇒ 각 요청마다 별도의 프로세스를 만드는 오버헤드는 불필요함o RPC 서버: 대부분 다중 쓰레드 시 프로세스 동기화(Process Synchronization)모니터(Monitor)☞ 세마포어 사용 시 문제- 세마포어의 경우 프로그래머가 세마포어를 잘못 사용할 때 다양한 유형의 오류가 너무나도 쉽게 발생할 수 있음=> 프로그래밍 언어에서 지원하는 구조물(construct)이 개발됨o 모니터(Monitor)- 프로그래밍 언어에서 지원하는 구조물(construct)- 사적인 자료(Private Data)가 있으며 공개 메소드(Public Method) 만을 사용하여 이 데이터에 접근할 수 있음- 모니터 안에 항상 하나의 프로세스만이 활성화되도록 보장※ 프로세스가 메소드 호출 시 (이미 사용중이면) 진입 큐로 들어감o Condition Variable(조건 변수)- 모니터 내에서만 접근 가능하며, 모니터 내의 프로세스가 condition의 signal을 기다리며 wait할 수 있음- 각자의 큐를 가짐- 다음의 두 연산만이 가능함* wait(): 모니터의 락을 포기하며, 다른 프로세스가 해당 condition에 대해 signal()을 호출하기를 기다림* signal(): condition에 대해 wait하는 한 개의 process를 wakeup시킴. wait하는 프로세스가 없다면 아무 일도 하지 않음※ 세마포어의 signal()과 모니터의 signal()의 차이점- 세마포어 signal(): 항상 세마포어의 상태에 영향을 줌(history)- 모니터의 signal(): wait하는 프로세스가 없다면 아무 일도 안함o signal() 호출 시의 동작- 프로세스 P가 조건 x에 대기한 프로세스 Q를 x.signal()로 깨운 경우, 다음의 두 가지 가능성이 존재함1. Signal and Wait (Hoare)- P는 Q가 모니터를 떠날 때까지 기다리거나 다른 조건을 기다림2. Signal and Continue- Q는 P가 모니터를 떠날 때까지 기다리거나 다른 조건을 기다림세마포어모니터signal() 호출은 항상 세마포어의 상태에 영향을 미침(history 기억)si)case 2) 공유 메모리를 메모리 사상 파일로 제공 (Windows)메모리 사상 입/출력 (Memory-Mapped I/O)o 메모리 사상 입/출력 (Memory-Mapped I/O)- 특정 메모리 영역에 장치 레지스터를 매핑할 수 있도록 함- 이 영역에 대한 읽기, 쓰기는 장치 레지스터로의 자료 전송으로 처리- 비디오처리기와 같은 응답 시간이 매우 빠른 장치에 적합공유 메모리프로세스 간 메모리 공유메모리 사상 파일메모리 페이지를 디스크 파일 블록에 사상메모리 사상 입/출력메모리 페이지를 장치 레지스터에 사상9.8 커널 메모리의 할당Chapter 9. 가상 메모리(Virtual Memory)커널 메모리의 할당o 커널 메모리를 사용자 프로세스와는 별도의 자유 메모리 풀에서 할당하는 이유1) 단편화 최소화: 커널은 다양한 크기의 자료 구조를 가지며, 단편화에 의한 낭비를 최소화하고자 함2) 연속적 메모리: 물리 메모리에 직접 접근하는 특정 하드웨어 장치는 물리적으로 연속적인 메모리를 필요로 하는 경우가 있음버디 시스템o 버디시스템- 물리적으로 연속된 페이지들로 이루어진 고정된 크기의 세그먼트로부터 2의 멱승 단위로 메모리를 할당함ex) 커널이 21KB 메모리를 요청 시, 32KB의 버디가 할당됨- First-fit처럼 할당하는 게 아니라, Best-fit처럼 할당함※ 크기가 2k이고 주소가 x인 블록의 버디의 주소는?- x+2k (if x mod 2k+1=0), x-2k (if x mod 2k+1 = 2k)o 장점: 인접한 버디들이 손쉽게 합병되어 하나의 큰 세그먼트로 합쳐질 수 있음o 단점: 할당된 세그먼트 내에 단편화가 발생 (☞ 슬랩 할당)슬랩 할당 (Slab Allocation)o 슬랩 할당(Slab Allocation)슬랩(Slab)o 하나 이상의 물리적으로 연속된 페이지들o 슬랩이 가질 수 있는 세 가지 상태- Full: 슬랩 내 모든 객체가 사용중- Partial: 슬랩 내 일부 객체가 사용중- Empty: 슬랩 내 모든 객체가 자유캐시(Cache을 때)☞ 디스크가 병목이 아닌 시스템에 적합 (LFB)[LIFO, Last-In Last-Out]o 최근의 요청을 먼저 처리- 장점: 순차 파일 접근 시 암의 이동이 아주 적거나 아예 없음- 단점: 디스크 부하가 많으면 기아 상태가 발생할 수 있음SSTF[SSTF, Shortest Seek Time First]o 현재 위치로부터 가장 가까운 요청을 우선 처리- 장점: FCFS보다 성능 향상- 단점: 기아 상태 발생 가능 (큐의 길이가 길수록 더 심각)- 단점: 중앙의 요청들을 선호하는 경향이 있음 (불균형)SCAN, C-SCAN[SCAN / Elevator Algorithm] : 양방향o 양방향 스캔- 장점: 기아 상태를 해결- 단점: 대기시간이 불균일* 한쪽 끝에 도달했을 때, 근처에는 대기중인 요청이 거의 없고 반대쪽 끝으로 가장 많은 요청들이 몰려 있음* 가장 최근에 통과한 위치에 비우호적이며, 지역성을 활용하지 않음[C-SCAN] : 단방향o 단방향 스캔 (반대쪽으로 되돌아가서 스캔)- 장점: 각 요청에 걸리는 시간을 좀 더 균등하게 함LOOK, C-LOOK[LOOK]o SCAN에서 요청이 없으면 끝으로 이동하지 않음[C-LOOK]o C-SCAN에서 요청이 없으면 끝으로 이동하지 않음Arm Stickiness 문제※ Arm Stickiness 문제- 한 트랙에 대한 요청이 반복되면, 장치를 독점할 수 있음- SSTF, SCAN, C-SCAN 등에서 발생하는 문제- N-Step-SCAN, FSCAN으로 해결N-Step-SCAN, FSCAN[N-Step-SCAN]o 디스크 요청 큐를 길이가 N인 하위 큐로 분할하고, 한 번에 하나의 큐를 SCAN으로 처리함- 새로 들어온 요청은 다른 큐에 추가되어야 함- N값이 커지면, SCAN에 가까움- N값이 1이 되면, FIFO에 가까움[FSCAN]o 두 개의 하위 큐를 사용- 스캔이 시작되면, 모든 요청은 하나의 큐에 존재함- 새로운 모든 요청은 다른 큐에 들어감※ 대부분의 문제에서는 SCAN이라고 하면 LOOK

기타| 2023.03.26| 76페이지| 20,000원| 조회(655)

행정고시, OS, 기술고시, 운영체제론, 전산직, 전산개발, 5급공채

미리보기

닫기
행정고시(5급공채) 전산직 NW(네트워크) 합격자 서브노트 평가A+최고예요

L2. 데이터링크 계층[개요]L2 데이터링크 계층 개요 (Frz)o “프레임”: 데이터링크층에서의 패킷o 데이터링크층에서 제공하는 서비스(일반적)① 프레이밍 (Framing)- 네트워크층에서 전달받은 패킷을 프캡슐화② 흐름 제어 (Flow Control)- 수신자의 버퍼가 가득 차면 패킷을 버리거나, 송신자에게 피드백을 전송함③ 오류 제어 (Error Control)- 오류 검출 및 수정o 링크의 두 종류(F250)① 점-대-점 링크② 브로드캐스트 링크o 데이터링크층의 두 하위 계층(F250)① DLC (Data Link Control)- 프레임 짜기, 흐름 제어, 오류 제어② MAC (Media Access Control)[인코딩 / 프레이밍]인코딩※ 인코딩 / 디코딩- 송신 노드: 비트를 신호로 인코딩,- 수신 노드: 신호를 비트로 디코딩o NRZ(Non-Return to Zero)- 기본신호는 안쓰고, 고신호/저신호만 씀- 1: 고신호, 0: 저신호- 목적: 가장 기본적인 방식- 단점: 기준값 혼돈(baseline wander), 클럭 복구(clock recovery)o NRZI(Non-Return to Zero Inverted)- 1: 현재 신호 반대로, 0: 현재 신호 그대로- 목적: NRZ의 문제점 해결- 단점: 0이 연속될 경우 효과가 없음o 맨체스터 인코딩(Manchester Encoding) (☞ 이더넷)- 데이터를 클럭과 XOR 하여 전송 (1: 고위->저위, 0: 저위->고위)- 단점: 변조 속도(baud rate)가 두 배가 되어, 비트 전송률은 변조 속도의 절반이 됨o 4B/5B- 모든 4bit를 5bit로 인코드하되, 앞부분에는 최대 1개의 0이, 뒷부분에는 최대 2개의 0이 나오도록 하여 연속된 0이 최대 3개를 넘지 않도록 함. 인코드한 5bit를 NRZI로 전송함- 목적: NRZI의 연속된 0 문제를 해결함- 단점: 80%의 효율을 얻음 (4비트 데이터당 5비트 전송)※ 4bit를 5bit로 인코딩하면 32bit가 남으므로, 다른일 때, 어떤 경로를 선택할 것인가?- 핫 포테이토 라우팅: 경계 라우터의 비용이 가장 적은 것을 선택o 경로 선택 방법① 지역 선호값: Local Preference가 가장 높은 경로를 선택② AS-PATH: AS-PATH가 가장 짧은 경로를 선택③ NEXT-HOP: NEXT-HOP의 cost가 가장 적은 경로를 선택④ BGP식별자: BGP 식별자가 가장 낮은 루트를 선택☞ BGP는 크게 두 가지 이슈로 나누어 생각할 것1) 외부 목적지에 대한 경로 알아내기- eBGP & iBGP=> BGP Path Table2) 외부 목적지를 포워딩 테이블에 추가하기- 인트라-도메인 라우팅 프로토콜의 비용을 그대로 사용- 핫 포테이토 라우팅[멀티캐스트]L3. 네트워크 계층(IP)멀티캐스트o 멀티캐스트 (Multicast)- 하나의 근원지, 하나의 목적지 그룹이 존재- 멀티캐스트 라우터는 하나 이상의 인터페이스를 통해 동일한 데이터그램의 복사본을 전달할 수 있음o 멀티캐스트 vs 다중 유니캐스트다중 유니캐스팅멀티캐스팅근원지에서 n개의 패킷 출발근원지에서 1개의 패킷 출발, 라우터에서 패킷을 복사각 패킷의 대상 주소가 다름모든 복사본의 대상 주소가 동일한 링크에 여러 복사본이 이동한 링크에는 한 복사본만 이동더 많은 대역폭 사용더 적은 대역폭 사용 (효과적)근원지 지연 발생 (패킷 복사)근원지 지연 없음※ 멀티캐스트 응용① 분산 데이터베이스② 정보 보급 (ex. 소프트웨어 업데이트)③ 원격 회의④ 원격 교육o IPv4 멀티캐스트 주소- D클래스 주소: 224.0.0.0/4 (최대 2^28개)111028 bits- 224.0.0.0/4 : 네트워크 내부에서 사용 (라우터 전달 X)- 224.0.1.0/24: 전체 인터넷에서 사용 (라우터 전달 O)- 232.0.0.0/8: SSM (Source-Specific Multicast)- 233.0.0.0/8: GLOP 블록, AS 내부에서 사용※ GLOP: AS 번호가 x.y인 경우 233.x.y.0/24 범위를 사용함o 이더넷 멀티 패킷: 버리고 누적 ACK(3을 기다리는 중에 4를 받으면 3으로 ACK)o 예: 송신자가 패킷 1, 2, 3을 보냈는데 1이 손실된 경우 (p740)- 수신자: ACK1, ACK1 보냄- 송신자: ACK1, ACK1 받고 무시나중에 타임아웃 발생 시 1, 2, 3 전부 재전송o 예: 수신자가 ACK 2, 3, 4를 보냈는데 2가 손실된 경우 (p739)- 송신자: ACK3, ACK4를 받았으므로 정상 진행※ NOTE: 타임아웃이 발생하지 않음! (CumACK의 장점)o 송신 윈도우 영역1) 전송되었고 ACK 받은 영역 (사본 보관 X)2) 전송되었고 ACK 안받은 영역 (Outstanding 패킷)3) 전송 가능하지만 응용에서 데이터가 내려오지 않은 영역4) 전송 불가능한 영역Sf Sn67012345670Sf: First Outstanding,Sn: Next to Sendo 수신 윈도우 영역1) 수신하였고 이미 ACK를 보낸 영역2) 수신을 기다리는 영역 (수신 윈도우, 1개)3) 수신 불가능한 영역 (받으면 버려짐)Rn01234567012Sn: Next Expected☞ GBN은 하부 네트워크의 패킷 손실이 많은 경우 비효율적- 하나만 손실되어도 전부 재전송해야 하므로※ 모든 3가지 프로토콜에서, SWS + RWS ≤2m 이어야 함- S&W: 1 + 1 ≤ 21- GBN: (2m-1) + 1 ≤ 2m- SR: (2m-1) + (2m-1) ≤ 2m☞ 항상 3가지 상황을 생각해보자① 프레임 성공, ACK 성공② 프레임 손실③ 프레임 성공, ACK 손실 ⇒ 순서번호 필드 길이를 결정하는 예시Selective Repeat윈도우송신 윈도우: 2m-1L4. 트랜스포트 계층(TCP)수신 윈도우: 2m-1순서번호0 ~ 2m-1 (m 비트)송신자동작타임아웃: ACK 안받은 패킷만 재전송 (모든 Outstanding)순서에 어긋난 ACK: ACK로 기억 (무시하지 않음)수신자동작선택적 ACK (2, 4, 5를 받으면 2, 4, 5로 ACK)순서에 어긋난 패킷: 버퍼에 저장2)o TCP와 SR의 유사점- 순서에 어긋난 세그먼트를 수신함 (Frz p792)☞ TCP는 GBN과 SR의 혼합으로 볼 수 있지만, SACK을 사용할 경우 SR과 더 유사함 (Krs, Frz)[TCP 혼잡제어]혼잡 제어 (Congestion Control)[Slow Start]o 1MSS에서 시작o RTT마다 cwnd를 2배로 증가시킴- ACK를 받을 때마다 1MSS 씩 증가시킴- Delayed ACK를 사용하는 경우, 더 느리게 증가함(ACK가 패킷 2개 당 하나씩 올 수 있으므로)[Congestion Avoidance]o RTT마다 cwnd를 1MSS씩 증가시킴- ACK를 받을 때마다 (MSS/cwnd)*MSS 씩 증가시킴[Fast Recovery]o 중복 ACK를 수신할 때마다 cwnd를 1MSS씩 증가시킴상태이벤트전이ssthreshcwndSS새 ACK--cwnd + 1MSSssthreshCA--3중복 ACKFRcwnd/2ssthresh + 3MSS타임아웃(SS)cwnd/21 MSSCA새 ACK--cwnd + MSS*(MSS/cwnd)3중복 ACKFRcwnd/2ssthresh + 3MSS타임아웃SScwnd/21 MSSFR새 ACKCA-ssthresh중복 ACK--cwnd + 1MSS타임아웃SScwnd/21 MSS☞ 주의: 3중복 ACK는 4번째 수신한 같은 번호의 ACK임!- (2번째: 1중복, 3번째: 2중복, 4번째: 3중복)TCP 버전o TCP Taeho (TCP Taho)- 타임아웃 발생 시 Slow Start 수행- 3중복 ACK 발생 시 Slow Start 수행 (Fast Recovery 하지 않음)o TCP Reno (가장 일반적)- 타임아웃 발생 시 Slow Start 수행- 3중복 ACK 발생 시 Fast Recovery 수행o TCP NewReno- 중복ACK의 수가 윈도우 끝보다 작으면, 그 패킷도 함께 재전송(즉, 손실된 패킷이 2개 이상이라고 판단함)o TCP Vegas- 손실이 발생하기 전에 혼잡을 발견함- 임박한 패킷 손실이사용)② 라우팅- 객체에 대한 참조의 저장을 책임지는 노드로 질의를 라우팅하는 것- 구현마다 조금씩 다르지만, 참조의 저장을 책임지는 노드와 가까운 노드로 라우팅하기 위해 각 노드가 링에 대한 부분적인 지식을 가져야 한다는 개념을 사용함③ 합류와 탈퇴 (Arrival and Departure)- 구성원들의 들어오기와 떠나기를 처리하는 명백하고 효율적인 전략이 있어야 함☞ P2P에 적합한 응용 (Krs R2-25)- File Distribution- Instant Messaging- Video Streaming- Distributed Computing※ 공통사항- 파일 해시값(k), 노드 해시값(N)- 파일 k에는 책임자 노드 N이 존재하는데, 이 노드는 실제 파일을 가지고 있는 서버 v에 대한 정보를 책임지고 저장함(N이 실제 파일을 갖고 있는게 아님. 매핑 정보를 가지고 있음)Chord식별자 공간원형으로 된 2m의 식별자 공간 (링)책임자 노드k의 후임자 노드가 (k,v) 정보를 저장함라우팅 테이블o 핑거 테이블- 1개의 전임자, m개의 후임자에 대한 정보 저장※ N: 자기 자신i타겟 키후임자후임자 정보전임자-전임자IP주소, 포트1N+20N+1의 후임자IP주소, 포트2N+21N+2의 후임자IP주소, 포트............mN+2m-1N+2m-1의 후임자IP주소, 포트검색(라우팅)o k의 전임자 후보(A) 찾음 (find_closest_predecessor)- 내 핑거테이블상의 k값의 전임자 A를 찾음(A는 실제 k의 전임자는 아닐 수 있음)o k의 실제 전임자(X) 찾음 (find_predecessor)- A에게 후임자[1]을 요청하여 B를 얻음- B에게 후임자[1]을 요청하여 C를 얻음...- 이런 식으로 반복하여 k의 실제 전임자 X를 찾음o k의 실제 후임자(Y) 찾음 (find_successor)- X에게 후임자[1]을 요청하여 k의 후임자 Y를 찾음☞ Y가 k를 가진 서버의 위치 정보를 갖고 있음!!합류(가입)o 안정화 함수, 핑거 변경 함수를 줌

기타| 2023.03.26| 52페이지| 20,000원| 조회(314)

행정고시, 기술고시, 네트워크론, 전산직, 전산개발, 5급공채

미리보기

닫기
행정고시(5급공채) 전산직 DS(자료구조) 합격자 서브노트 평가A+최고예요

[DS][증명 모음]이진 트리 (Binary Tree)214레벨 i의 최대 노드 수 =2^i-1 ```(i geq 1)214깊이 k인 이진 트리의 최대 노드 수 =2^k - 1 ``` (k geq 1)215공백이 아닌 이진 트리에서 n0 = n2 + 1216n개의 노드를 갖는 완전 이진 트리의 높이는 ?log2(n+1)?278n개의 키 값을 가지는 상이한 이진 트리의 수M156이진 트리에서 임의 노드의 평균 높이는 O(logn)분리 집합 (Disjoint Set)266n개의 노드를 가진 트리 T가 weightedUnion 함수로 만들어진 트리라면, T에 있는 어떤 노드도 ?log2n?+1보다 큰 레벨을 가질 수 없음그래프 (Graph)311Kruskal 알고리즘이 최소 비용 신장 트리를 생성함을 증명-Prim 알고리즘이 최소 비용 신장 트리를 생성함을 증명정렬 (Sorting)360Quicksort의 최선의 시간복잡도는 O(nlogn)360Quicksort의 평균 시간복잡도는 O(nlogn)-quickSelect의 평균 시간복잡도는 O(n)363n개의 서로 다른 원소들을 정렬하는 결정 트리의 높이는 적어도 log2(n!) + 1364비교만으로 정렬하는 알고리즘은 최악의 경우 Ω(nlogn) 연산 시간을 가짐372최대 히프 구성 시간은 O(n)해싱 (Hashing)428체인법에서U_n approx alpha,S_n approx 1 + alpha / 2최적 이진 탐색 트리513n개의 내부 노드를 가진 이진 트리에서 내부 경로의 길이가 I, 외부 경로의 길이가 E이면 E = I + 2n (n≥0)506I의 최대값: I = n(n-1)/2506I의 최소값: I = Σ?log2i? = O(nlog2n)524AVL 트리의 최악의 삽입 시간은 O(logn)530레드-블랙 트리에서 루트로부터 외부 노드로의 2개의 경로 P, Q가 있을 때, length(P) ≤ 2length(Q)530레드-블랙 트리의 높이를 h, 내부 노드 수를 n, 루트의 랭크를 r이라 할 때의 3가지 정mes upper_{n-1}+ ``` i_{n-1}=alpha + sum _{j=0} ^{n-1} i_j a_j{cases{a_j = sum _{k = j + 1} ^{n-1}upper_k & (0 leq j < n-1)# a_n-1 = 1&}}2.7 스트링 [12]o C언어 스트링C언어 스트링char* strcat(char* d, char* s)char* strcmp(char* s1, char* s2)char* strcpy(char* d, char* s)o 패턴 매칭패턴 매칭o패턴 매칭nfind()시간: O(nm)KMP 알고리즘KMPpmatch()시간: O(m)fail()시간: O(n)o 실패함수 계산: j = 8, i = 3f(j) = cases{ ``````` i & ``````````p_0 p_1 ... p_i ```=``` p_{j-i} p_{j-i+1} ... p_j# -1& ``````````otherwise}j0123456789patabcabcacabf-1-1-10123-101o 패턴 매칭o str[i]와 pat[j]에서 불일치가 일어난 상황- f(j-1) = 3이므로, 직전 pat[0~3]은 이미 일치함을 알고 있음- 따라서 pat[4]부터 다시 비교를 시작하면 됨o 실패함수 계산 - fail[j]o 실패 함수를 구하고 패턴 매칭을 수행하는 데 걸리는 총 시간= O(strlen(pat) + strlen(string))☞ 각각 시간복잡도 구하는 과정 이해할 것!! (p102, p103)3장 스택과 큐3.1 스택3.2 동적 배열을 사용하는 스택스택 (배열 표현)element stack[MAX_STACK_SIZE]삽입pust()1) 스택 Full: 에러 메시지2) 아니면: ++top삭제pop()1) 스택 Empty: 에러 메시지2) 아니면: top--스택 (배열 표현, 동적 할당)element* stack동적 할당stackFull()스택의 capacity를 두배로(REALLOC)※ 스택의 3가지 응용 (M.Weiss)1. Balancing Symbo(i)- (2i≤n): 2i- (2i>n): leftChild가 없음(3) 인덱스 i인 노드의 rightChild(i)- (2i+1≤n): 2i+1- (2i+1>n): rightChild가 없음o 장점: 노드 i의 왼쪽/오른쪽 자식, 부모의 위치를 쉽게 결정 가능o 문제점1) 공간 낭비: 깊이 k인 편향 트리는 총 2k-1개의 공간 중 k개만 사용2) 삽입,삭제: 삽입, 삭제 시 노드 레벨의 변경에 따라 많은 노드의 위치가 변경되어야 함※ m-차 트리인 경우 배열 표현에서 노드 i의 부모, 자식의 인덱스- TODO5.3 이진 트리 순회 [6]5.4 이진 트리의 추가 연산 [6]이진 트리 (연결 표현)중위 순회전위 순회후위 순회inorder()preorder()postorder()inorder: LVRpreorder: VLRpostorder: LRV반복적중위 순회iterInorder()시간: O(n)공간: O(n)L1. LC 따라가면서 전부 스택 push()L2. pop() & 출력L3. RC로 이동한 후 1번부터 반복레벨 순서 순회levelOrder()0. (루트를 큐에 넣음)L1. 큐에서 하나 꺼냄L2. 출력 & LC 큐 삽입 & RC 큐 삽입트리 복사copy()동일성 검사equal()o 이진 트리에서 스택을 위한 추가적인 공간 없이 트리 순회하는 방법1) 각 노드에 parent 필드를 추가2) 각 노드에 두 비트를 추가하여 스레드 이진 트리로 표현※ 반복적 전위/후위 등도 연습해볼 것!!Satisfiability(만족성 문제) 트리Satisfiability 후위 연산postOrderEval()시간: O(n)1. LC, RC 먼저 재귀적으로 계산2. 연산자에 따라 계산(LC, RC 사용)5.5 스레드(Thread) 이진 트리 [5]스레드(Thread) 이진 트리o leftThread, rightThread- leftThread = TRUE: leftChild는 중위 선행자- leftThread = FALSE: leftChild는 왼쪽 자식o 헤드 노드(roo(G') ⊆ E(G)인 그래프 G'o 경로, 길이, 단순 경로, 단순 방향 경로o 사이클, 방향 사이클o 차수(degree)- 방향 그래프: 진입 차수(in-degree), 진출 차수(out-degree)인접 행렬 (그래프 표현 1)o 인접 행렬(Adjacency Matrix): n x n 의 2차원 배열- 간선 (vi, vj)가 E(G)에 속하면 a[i][j] = 1- 간선 (vi, vj)가 E(G)에 없으면 a[i][j] = 0o 인접 행렬: 무방향 그래프- 대칭- 정점의 차수: 행의 합o 인접 행렬: 방향 그래프- 대칭이 아닐 수 있음- 정점의 진출차수: 행의 합- 정점의 진입차수: 열의 합인접 리스트 (그래프 표현 2)o 인접 리스트(Adjacency List): (1) 체인 표현- 각 정점에 대해 1개의 체인이 존재- 체인 i에 있는 각 노드들은 정점 i로부터 인접된 정점을 나타냄- 무방향 그래프: 2e개 노드, 방향 그래프: e개 노드- 필요한 공간:n times log`n ``+`` 2e times (log`n + log`e) . logn 크기의 포인터 n개. (logn + loge) 크기의 노드 2e개o 네트워크: 가중치 간선을 가진 그래프 (weight 필드를 추가)※ AOE 네트워크, AOV 네트워크o 인접 리스트(Adjacency List): (2) 배열 표현- node[i]는 정점 i에 대한 리스트의 시작 지점 (ex: node[0]=9)- node[n]은 n+2e+1 (ex: node[8] = 8 + 2*7 + 1 = 23)o 역 인접 리스트(Inverse Adjacency List)- 방향 그래프(digraph)에서 각 정점으로 향하는 정점을 연결함o 직교 리스트 (skip)인접 다중리스트 (그래프 표현 3)o 인접 다중리스트(Adjacency Multilists)- 각 간선에 대해 오직 하나의 노드가 존재하며, 이 노드는 두 리스트에 연결됨mvertex1vertex2link1link2- m: Boolean 마크 (검사 여부 표시)- 고 |T| T는 MSTPrim 증명1단계: 신장 트리가 존재하는 경우 Prim 방법이 신장 트리를 생성o 각 단계마다 TV안에서 한 정점, TV 밖에서 한 정점을 연결함- G가 연결 그래프라면, 모든 정점으로 향하는 경로는 반드시 존재- 각 단계에서 생성되는 중간 결과는 반드시 사이클이 없는 연결 그래프임o 따라서 최종 결과는 1) 모든 정점을 포함하는 2) 사이클이 없는 연결 그래프가 됨 => 신장 트리를 생성2단계: 생성된 신장 트리 T가 최소 비용임을 보임o 그래프 G의 MST가 U일 때, T ≠ U라고 가정함o T에만 있고 U에는 없는 간선 중 가장 먼저 Prim 알고리즘에서 선택된 간선을 e라고 함- T가 e를 선택하기 직전에 이미 선택된 정점 집합을 V라고 함o U에는 e의 두 정점을 연결하는 (e가 아닌)다른 경로가 반드시 존재함- 그 경로를 따라가다보면, V와 V외부를 연결하는 간선 f가 반드시 존재함 (애초에 e의 두 정점 중 하나는 V, 하나는 외부이므로)o T 생성 시 f가 아닌 e가 선택되었으므로, w(e) ≤ w(f)가 성립o V = U + {e} - {f}라고 하면, V도 신장 트리임- w(e) < w(f)라면 U가 MST이므로 모순이고,- w(e) ≤ w(f)가 성립하므로, 결론적으로 w(e) = w(f)가 됨=> 따라서 T의 비용과 U의 비용은 같음 => T는 MSTDynamic Programmingo Dynamic Programming: 복잡한 문제를 좀 더 단순한 부분문제(subproblem)로 나누어서 해결하는 방법- “Overlapping Subproblems"와 ”Optimal Substructure"의 성질을 가지는 문제들에 적용 가능함. Overlapping Subproblems: 부분문제를 푸는데 필요한 부분문제들이 서로 중첩되어서, 결국에 풀어야 할 모든 부분문제의 수의 합이 크지 않아야 함 (ex: Fi = Fi-1 + Fi-2). Optimal Substructure: 주어진 문제에 대한 최적의 솔루션이, 문제의n)

기타| 2023.03.26| 40페이지| 20,000원| 조회(759)

행정고시, 자료구조, 기술고시, 전산직, 전산개발, 5급공채

미리보기

닫기
행정고시(5급공채) 전산직 합격자 정리노트 - DS 코드

2장 배열과 구조2.1 배열 [4]2.1.1 추상 데이타 타입2.1.2 C언어에서의 배열o int list2[5]로 선언되었을 때- list2 는 list2[0] 을 가리키는 포인터- list2 + i 는 list2[i]를 가리키는 포인터※ i에 int의 크기를 곱하지 않음- (list2 + i)와 (&list2[i])는 항상 같음- *(list2 + i)와 list2[i]도 같음o 배열 매개변수의 경우, list[i]가 기호 ‘=’의 왼편에 나타난다면 오른편에서 생성된 값은 위치 (list+i)에 저장된다 => call by value 임에도 불구하고 배열 매개변수가 실제로 값을 변경하게 만든다.2.2 동적으로 할당된 배열 [4]2.2.1 1차원 배열o MAX_SIZE라는 상수를 사용하지 않고 MALLOC을 사용하여 동적으로 배열 크기를 할당함2.2.2 2차원 배열2.3 구조와 유니언 [6]2.3.1 구조(Struct)구조체(Struct)p63struct {char name[10];int age;float salary;} person;구조체 데이터 타입 선언p64typedef struct humanBeing{char name[10];int age;float salary;};(Errata에 보면 바꾸라고 나옴)typedef struct {char name[10];int age;float salary;} humanBeing;2.3.2 유니언(Union)유니언(Union) 선언p66typedef struct {enum tagField {female, male} sex;union {int childred, int beard;} u;// 둘 중 하나만 활성화} sextype;typedef struct {char name[10]; int age; float salary; date dob;sexType sexinfo;} humanBeing;humanBeing person1, person2;2.3.3 구조의 내부 구현2.3.4 자기 참조 구조(Self-Referentialloat coef[MAX_DEGREE];} polynomial;// a.coef[i] = an-i, a.coef[0] = ano 많은 저장공간을 낭비함: 다항식의 차수가 MAX_DEGREE라는 상수보다 훨씬 적거나, 다항식에서 계수가 0인 차수가 많은 경우다항식 (구조체 배열 2)p73typedef struct{float coef;int expon;} polynomial;polynomial terms[MAX_TERMS];int avail = 0;// terms 배열 내의 다음 가용 공간// startA, finishA가 각각 시작 인덱스, 종료 인덱스를 위해 필요함o 다항식 표현방법1과의 비교- 계수가 0인 항이 많은 경우: 방법1보다 많은 기억 공간 절약- 모든 항이 0이 아닌 경우: 방법1보다 거의 2배의 기억 공간 필요o avail이 MAX_TERMS까지만 증가할 수 있고, 이를 넘어서면 표현이 불가능하다. 불필요한 다항식을 제거하고 압축하는 방법도 있지만, 데이터 이동에 많은 시간이 걸린다. (p76)다항식 :: 덧셈p74o padd()- 표현방법2로 된 다항식 A, B를 받아서 더한 결과를 D에 저장- attach(): 새로운 항을 다항식에 추가함- 전역변수 terms[], avail- 시간: O(n+m)int padd(int startA, int finishA, int startB, int finishB,int *startD, int *finishD){float coefficient;*startD = avail;while (startA rightchild = NULL;if (*node)// 공백 트리가 아닐 때if (k < temp->data.key) temp->leftChild = ptr;else temp->rightChild = ptr;else *node = ptr;// 공백 트리일 때}}이진 탐색 트리 :: 삭제p249o delete()- 시간: O(h)o 이진 탐색 트리 삭제의 3가지 경우1) 단말 노드: 부모의 자식 필드를 NULL로2) 자시할 때 O(h)와 같은 방식으로 해야 함. 함부로 O(log N) 이런거 쓰지 말 것!이진 탐색 트리 :: 조인p250o threeWayJoin(small, mid, big)- 트리 small, 노드 mid, 트리 big을 합하여 하나의 이진 탐색 트리를 생성- small < mid < big 으로 가정, 연산 종료 후에는 small, big은 공백{...}이진 탐색 트리 :: 조인p251o twoWayJoin(small, big)- 트리 small, 트리 big을 합하여 하나의 이진 탐색 트리를 생성- small < big으로 가정, 연산 종료 후에는 small, big은 공백{...}이진 탐색 트리 :: 분할p252o split()- theTree가 가리키는 이진 탐색 트리를 세 부분으로 분할하여- small: k보다 작은 키를 가지는 이진 탐색 트리- mid: theTree에 k가 있을 경우 그 element, (없으면 NULL)- big: k보다 큰 키를 가지는 이진 탐색 트리void split(nodePointer *theTree, int k, nodePointer *small,element *mid, nodePointer *big){if (!theTree) {*small = *big = 0;(*mid).key = -1;return;}nodePointer sHead, bHead, s, b, currentNode;MALLOC(sHead, sizeof(*sHead));MALLOC(bHead, sizeof(*bHead));s = sHead;b = bHead;currentNode = *theTree;while (currentNode)if (k < currentNode→data.key) {b→leftChild = currentNode;b = currentNode;currentNode = currentNode→leftChild;}else if (k < currentNode→data.key) {s→rightChild = currentNode;s = currenthild;free(bHead);(*mid).item = currentNode→data.item;(*mid).key = currentNode→data.key;free(currentNode);return;}s→rightChild = b→leftChild = 0;*small = sHead→rightChild;free(sHead);*big = bHead→leftChild;free(bHead);(*mid).key = -1;return;}5.8 선택 트리 [4]o5.9 포리스트 [3]o5.10 분리 집합 [12]분리 집합(Disjoint Set) - 배열 표현p264int parent[MAX_ELEMENTS];i[0][1][2][3][4][5][6][7][8][9]parent-14-12-120004분리 집합 :: 탐색p264o simpleFind()- 노드 i가 속하는 집합(루트의 인덱스)을 리턴int simplefind(int i){for ( ; parent[i] >= 0; i = parent[i] );return i;}분리 집합 :: 합집합p264o simpleUnion()- 두 집합 i, j를 합집합 (i를 j의 서브트리로)void simpleUnion(int i, int j){parent[i] = j;}o 변질 트리(degenerate tree) 문제가 발생분리 집합(Disjoint Set) - 카운트 추가p264int parent[MAX_ELEMENTS];o 트리의 노드 수(count)를 루트의 parent 필드에 음수로 저장함i[0][1][2][3][4][5][6][7][8][9]parent-44-32-320004o 카운트를 사용할 경우, m개의 원소를 가진 트리에서 한 번의 탐색 연산에 걸리는 시간은 O(log m)분리 집합 :: 합집합(Weighted)p267o weightedUnion()- j의 카운트가 더 크면 j를 루트로, 아니면 i를 루트로 하여 합집합void weightedUnion(int i, int j){int temp = parent[ i ]붕괴p269o collapsingFind()- i부터 루트까지의 경로에 있는 모든 노드들의 parent를 루트로 변경o 붕괴 규칙: 만일 j가 i에서 루트로 가는 경로상에 있으며parent[i] ≠ root(i)이면 parent[j]를 root(i)로 지정한다.- 붕괴 규칙은 개별적인 탐색 시간을 거의 2배 걸리게 하지만 연속적인 탐색에 대하여는 최악의 시간을 감소시킴o 분리 집합 표현은 4.6절의 동치 부류(Equivalence Relation)를 처리하는 문제에도 적용될 수 있음int collapsingFind(int i){int root, trail, lead;// 1. 일단 루트를 찾음for (root = i; parent[root] >= 0; root = parent[root]);// 2. i부터 루트로 가는 길에 있는 노드의 parent[]를 전부 수정for (trail = i; trail != root; trail = lead) {lead = parent[trail];parent[trail] = root;}return root;}5.11 이진 트리의 개수 계산 [6]이진 트리의 개수 계산o 다음 세 개의 문제에 대한 답이 동일(1) n개의 노드를 가진 서로 다른 이진 트리의 개수(2) 1~n까지의 수를 스택으로 만들 수 있는 상이한 순열의 수(3) n개의 행렬을 곱하는 방법의 수b_n = sum _{i=0} ^{n-1} b_i b_n-i-1 ``````````(n geq1,`` b_0 = 1)= b_0 b_n-1 + b_1 b_n-2 + b_2 b_n-3 + ... + b_n-2 b_1 + b_n-1 b_0=` _{2n} C _{n} `/`(n+1)=O(4 ^{n} /n ^{3/2} )6장 그래프6.2 그래프의 기본 연산 [13]그래프 :: DFSp296o dfs()- 그래프의 깊이 우선 탐색 (인접 리스트 사용)- 전역변수 graph[], visited[]- 인접리스트: O(e) ⇒ 각 노드를 많아야 1번씩 조사※ 인접 행렬: O(n^2) ⇒ 인

기타| 2023.03.26| 34페이지| 10,000원| 조회(297)

행정고시, 기술고시, 서브노트, 전산직, 전산개발, 5급공채

미리보기

닫기
행정고시(5급공채) 전산직(정보보호) 서브노트

<썸네일을 참조해주세요>

기타| 2023.03.26| 48페이지| 20,000원| 조회(1,530)

행정고시, 기술고시, 전산직, 5급공채, 정보보호직

미리보기

닫기