dh_0e

UCPC 예선에서 발상을 잘못해서 다 구현해놓고 실수로 분리 집합을 빼먹어서 시간 내에 풀지 못했던 문제.대회 끝나고 처음부터 다시 풀어보는데 union-find를 함수 없이 구현해보려다 몇 번 틀렸다. 풀이 과정 오염 영역의 최댓값은 n이 200,000까지이고 격자의 크기가 $10^9$x$10^9$이기 때문에 n값을 그대로 출력해주면 되며, 오염 영역의 최솟값만 구하면 되는 문제이다. 최솟값을 구하는 로직을 greedy하게 생각하면, d[i]가 d[i-1]보다 크다면 다음 줄로 넘기지 않고, d[i-1]보다 작거나 같을 때만 다음 줄로 넘기게끔 하면 항상 오염 영역을 가장 많이 줄일 수 있다. prevQue: 이전 줄의 index들 저장하는 QueuerecQue: 현재 줄의 index들 저장하는 De..

Bad Schemacourse 테이블과 department 테이블이 합성된 아주 나쁜 스키마deptName을 기준으로 자연 조인 연산을 한 테이블이 나옴Three anomalies (이상현상)Update anomalydept의 정보를 고치려면 n번 고쳐야 함ex) 'CS' 학과의 chairman이 바뀌었다면 3번 고쳐야 함Delete anomaly수업을 없앴을 때 dept 정보가 모두 날아갈 수 있음ex) 222, 223 수업을 삭제하면 'Media' 과의 정보가 날아감Insert anomaly새로운 dept 신설 시 과목이 없으면 삽입 불가능ex) 'CE' 과가 신설돼도 과목이 없어서 데이터 삽입 불가능course 테이블과 room 테이블이 합성된 아주 나쁜 스키마course 정보와 room 정보는 전..

Congestion ControlCongetsion Window (cwnd)송신자의 윈도우 크기를 결정하는 요소로 두 가지 요인에 의해 결정됨수신자가 광고한 윈도우 크기(rwnd)수신자의 버퍼 공간에 따라 결정됨네트워크 혼잡 상태(cwnd)작은 값을 쓰다가 점점 키워감, segment가 loss가 나면 cwnd를 줄여서 설정 네트워크가 데이터를 처리할 수 있는 속도보다 송신 속도가 빠를 경우, 네트워크가 송신자에게 속도를 줄이라고 알림실제 송신 윈도우 크기 = min(rwnd, cwnd) / 대부분 rwnd > cwndCongestion PolicySlow Start (느린 시작)전송 속도를 느리게 시작하지만, treshold에 도달할 때까지 점점 빠르게 증가시킴Exponential Increase (지..

State Transition Diagram (상태 전이 다이어그램)일종의 설계 도면으로 TCP 상태 전이 다이어그램은 두 문자열을 슬래시(/)로 구분해 표기함첫 번째 문자열 = 입력(input): TCP가 받는 이벤트두 번째 문자열 = 출력(output): TCP가 보내는 반응Part I.에서 한 부분은 검은색 실선만 따라가면 됨ESTABLISHED 상태는 두 종류가 있음클라이언트용 ESTABLISHED: 일정한 순서로 요청 전송 중심서버용 ESTABLISHED: 수신 버퍼를 준비, 응답 중심흐름 제어와 오류 제어 측면에서 서로 역할이 다르므로 구분됨 A Common ScenarioClient StatesActive open: 클라이언트 프로세스가 TCP에게 특정 서버 주소와 포트로 연결 요청함 (co..

Process-to-Process Communication Stream Delivery Service메시지 단위가 아닌 byte 흐름 단위로 데이터를 전송나눠서 혹은 합쳐서 받을 수 있음Segment: TCP의 data unit으로, Application에서 받은 바이트 스트림을 TCP가 적절히 나눠서 만든 패킷 Numbering System (번호 체계)TCP는 두 가지 번호 필드를 사용함Sequence NumberAcknowledgment Number이 번호들은 세그먼트 번호가 아니라 바이트 번호를 기준으로 함 Byte NumberTCP는 보통 0부터 시작하지 않음임의의 시작 번호(ISN)를 선택함 (0 ~ $2^{32}-1$ 사이에서 임의로 고름)ex) ISN(Initial Sequence Numb..

User Datagram FormatUDP 패킷의 헤더 구조는 총 8바이트로 고정이며 4개의 필드로 구성됨Source Port Number(16bit): 송신 측 포트 번호, 범위 0~65,535Destination Port Number(16bit): 수신 측 포트 번호, 범위 0~65,535Length(16bit): 헤더(항상 8바이트) + 데이터의 전체 길이, 단위: 바이트Checksum(16bit): 오류 검출용 필드 (선택적 사용 가능) Process-to-Process CommunicationUDP도 TCP처럼 포트 번호를 이용해서 응용 프로그램 단위로 통신을 연결해줌여러 프로세스가 UDP를 사용할 수 있도록 UDP는 여러 포트 번호를 지원같은 컴퓨터 내부에서 UDP 통신을 하면 루프백 인터페이..