https://www.acmicpc.net/problem/10546 문제마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명만 빼고!모두가 참가하고 싶어서 안달인데 이런 백준 마라톤 대회에 참가해 놓고 완주하지 못한 배부른 참가자 한 명은 누굴까? 입력첫째 줄에는 참가자 수 N이 주어진다. (1 ≤ N ≤ 105)N개의 줄에는 참가자의 이름이 주어진다.추가적으로 주어지는 N-1개의 줄에는 완주한 참가자의 이름이 쓰여져 있다. 참가자들의 이름은 길이가 1보다 크거나 같고, 20보다 작거나 같은 문자열이고, 알파벳 소문자로만 이루어져 있다.참가자들 중엔 동명이인이 있을..

https://www.acmicpc.net/problem/11758문제2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오. 입력첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. 출력P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다. 코드def ccw(x1, y1, x2, y2, x3, y3): return ..

본 내용은 컴퓨터 네트워크 - 하향식 접근 책을 바탕으로 정리하였습니다. connectionless transport: UDP1. UDP(User Datagram Protocol)비연결형 전송 계층 프로토콜주요 특징단순성 - "no frills", "bare bones" => 불필요한 기능 없이 간단한 구조신뢰성 X - Best-effort delivery => 손실, 순서 변경 가능연결 X - Connectionless => TCP처럼 handshake(3-way) 없음독립 처리 - 각 세그먼트는 독립적으로 처리됨 어떤 일이 발생할 수 있을까?세그먼트가 유실될 수 있음세그먼트의 순서가 뒤바뀔 수 있음수신자가 도착 여부를 알 수 없음왜 UDP를 쓸까?스트리밍 앱 -> 약간의 손실은 괜찮지만 지연이 생기..

본 내용은 컴퓨터 네트워크 - 하향식 접근 책을 바탕으로 정리하였습니다. Transport Layer1. 트랜스포트 계층 서비스와 프로토콜트랜스포트 계층 프로토콜은 서로 다른 호스트에서 동작하는 애플리케이션 프로세스들 간의 논리적 통신(logical communication)을 제공한다. 논리적 통신이란 애플리케이션의 관점에서 보면 프로세스들이 동작하는 호스트들이 직접 연결된 것처럼 보인다는 것을 의미한다. (실제 호스트들은 수많은 라우터와 다양한 형태의 링크를 통해 연결되어 지구상의 서로 다른 지역에 있음)트랜스포트 계층 프로토콜은 네트워크 라우터가 아닌! end system에서 구현된다. 송신 측의 트랜스포트 계층은 송신 애플리케이션 프로세스로부터 수신한 메시지를 세그먼트(segment)인 트랜스포..

본 내용은 컴퓨터 네트워크 - 하향식 접근 책을 바탕으로 정리하였습니다. video streaming1. 인터넷 비디오Video = 이미지들의 연속영상은 짧은 시간 간격으로 여러 이미지(프레임)를 보여주는 것영화는 보통 1초에 24장(프레임)의 이미지를 보여줌 -> 24 fps디지털 이미지디지털 영상 속의 각 프레임은 픽셀(pixel)로 이루어져 있음.true color: RGB 각각 8비트씩 해서 24비트로 색깔을 표현함.Coding (압축/인코딩)Spatical Redundancy (공간적 중복)한 이미지 내에서 비슷한 부분이 많을 경우비슷한 픽셀들을 압축해서 저장Temporal Redundancy (시간적 중복)연속된 이미지(프레임)들 사이에 비슷한 부분이 있을 경우 (ex. 움직이지 않는 배경)..

본 내용은 컴퓨터 네트워크 - 하향식 접근 책을 바탕으로 정리하였습니다.  P2P applications1. Pure P2P architectureP2P 구조: 피어(peer)라는 간헐적으로 연결된 호스트 쌍이 서로 직접 통신하는 방식.피어는 서비스 제공자가 소유하지 않고, 사용자들이 제어하는 데스크톱과 랩톰임. 한 피어가 서버 역할을 하기도 하고, 클라이언트 역할을 하기도 함. 2. File distribution: client-server vs P2Pu_s: 서버의 접속 링크 업로드 속도u_i: i번째 피어의 접속 링크 업로드 속도d_i: i번째 피어의 접속 링크 다운로드 속도F: 분배되는 파일의 크기N​: 파일의 복사본을 얻고자 하는 피어들의 수클라이언트-서버 N개의 피어에게 업로드 속도 u_s로 ..

https://www.acmicpc.net/problem/2015 문제A[1], A[2], ..., A[N]의 N개의 정수가 저장되어 있는 배열이 있다. 이 배열 A의 부분합이란 1 ≤ i ≤ j ≤ N인 정수 i와 j에 대해 A[i]부터 A[j]까지의 합을 말한다.N과 A[1], A[2], ..., A[N]이 주어졌을 때, 이러한 N×(N+1)/2개의 부분합 중 합이 K인 것이 몇 개나 있는지를 구하는 프로그램을 작성하시오. 입력첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 주어진다. 주어지는..

운영체제는 다양한 활동을 관리함!관리대상사용자 프로그램 (User programs)시스템 프로그램 (System programs) -> 프린터 스풀러, 이름 서버, 파일 서버 등 프로세스 관리(Process Management)프로세스란?각 활동은 하나의 프로세스로 캡슐화됨.실행 중인 프로그램의 한 "실행 인스턴스(instance) -> 하나의 프로그램이 여러 개의 프로세스로 동시에 실행될 수 있음. OS가 해야할 일: 프로세스 관리(Process Management)프로세스 생성(create), 삭제(delete)일시 중지(suspend), 다시 시작(resume)스케줄링(scheduling)프로세스 간 통신(IPC)과 동기화(synchronization)교착 상태(deadlock) 처리 메모리 관리 ..

What is an Operating System?운영체제 -> 사용자와 하드웨어 사이의 인터페이스 제공하는 서비스프로세스CPU 스케줄링메모리 관리파일 시스템네트워킹개발 목표 - machine을 더 편리하고 효율적으로 사용할 수 있도록 하는 것. (소프트웨어 엔지니어링 문제) Why study Operating System?Abstraction (추상화)사용자에게 무한한 자원(CPU 시간, 메모리, 파일 공간)에 대한 환상을 어떻게 제공하는지?System Design (시스템 설계)이 추상화들의 성능과 편리성OS의 성능과 단순성하트웨어 / 소프트웨어의 기능Primaty intersection point (주요 교차점)하드웨어, 소프트웨어, 프로그래밍 언어, 데이터 구조 및 알고리즘이 모두 합쳐지는 지점C..

본 내용은 컴퓨터 네트워크 - 하향식 접근 책을 바탕으로 정리하였습니다.  DNS1. DNS: domain name system인터넷 호스트에 대한 식별자호스트 네임(hostname) IP 주소  DNS (domain name system)DNS 서버들의 계층구조로 구현된 분산 데이터베이스 (세계 곳곳에 분산해서 갖고 있음)호스트가 분산 데이터베이스로 질의하도록 허락하는 애플리케이션 계층 프로토콜 2. DNS가 제공하는 서비스host name을 IP 주소로 변환호스트 엘리어싱(host aliasing)복잡한 호스트 네임(정식 호스트 네임)을 가진 호스트는 하나 이상의 별명을 가질 수 있음. DNS는 호스트의 IP 주소뿐만 아니라 제시한 별칭 호스트 네임에 대한 정식 호스트 네임을 얻기 위해 이용됨.메일 ..