알고리즘 그리디 알고리즘 풀이 0번째 스위치를 누르는 경우와 0번째 스위치를 누르지 않는 경우를 나누어 생각한다. 1~n-1번째 스위치를 누를지 말지 여부를 결정하기 위해 for문을 돌린다. i번째 스위치를 누를지 말지를 결정하기 위해 i-1번째 전구의 상태와 목표로 하는 i-1번째 전구의 상태를 비교한다. 같으면 누르고 cnt++ 다르면 누르지 않는다. 현재 전구의 상태와 목표로 하는 전구의 상태가 같으면 cnt를 리턴하고 그렇지 않으면 2147000000을 리턴한다. 0번째 스위치를 누르는 경우와 0번째 스위치를 누르지 않는 경우 중 최소값을 골라 출력한다. 만약에 두 경우 모두 답이 나오지 않아 리턴값이 2147000000인 경우 -1을 출력한다. 전체 코드 #include #include usin..
[Computer Network] 4.1 네트워크 계층 개요, 4.2 라우터 내부에는 무엇이 있을까?
4.1 네트워크 계층 개요 각 라우터의 데이터 영역 역할은 입력 링크에서 출력 링크로 데이터그램을 전달하는 것이다. 네트워크 제어 영역의 근본적 역할은 데이터그램이 송신 호스트에서 목적지 호스트까지 잘 전달되게끔 local 포워딩, pre-router 포워딩을 대응시키게 만드는 것이다. 4.1.1 포워딩과 라우팅: 데이터 영역과 제어 영역 네트워크 계층의 근본적 역할은 송신 호스트에서 수신 호스트로 패킷을 전달하는 것 포워딩(전달) 네트워크 계층 데이터 영역에 의해 실행되는 매우 중요한 기능이다. 패킷이 라우터의 입력 링크에 도달했을 때 라우터는 그 패킷을 적절한 출력 링크로 이동시켜야 한다. 매우 짧은 시간(보통 몇 나노초) 단위를 갖기에, 대표적으로 하드웨어 실행된다. 라우팅 네트워크 전반에 걸쳐 출..
[Computer Network] 3. 트랜스포트 계층
3.1 트랜스포트 계층 서비스 및 개요 트랜스포트 계층 프로토콜 서로 다른 호스트에서 동작하는 애플리케이션 프로세스들 간의 논리적 통신을 제공한다. 네트워크 라우터가 아닌 종단 시스템에서 구현된다. 세그먼트(segment) 송신 측의 트랜스포트 계층은 송신 애플리케이션 프로세스로부터 수신한 메시지를 트랜스포트 계층 패킷으로 변환한다. 이를 세그먼트라고 부른다. 이러한 변환은 애플리케이션 메시지를 트랜스포트 계층 세그먼트로 만들기 위해 작은 조각으로 분할하고, 각각의 조각에 트랜스포트 계층 헤더를 추가함으로써 수행된다. 3.1.1 트랜스포트 계층과 네트워크 계층 사이의 관계 트랜스포트 계층 프로토콜 서로 다른 호스트에서 동작하는 프로세스들 사이의 논리적 통신을 제공 네트워크 계층 프로토콜 호스트들 사이의 ..
[Computer Network] 2.7 소켓 프로그래밍: 네트워크 애플리케이션 생성
다음의 간단한 클라이언트-서버 애플리케이션을 UDP와 TCP로 구현해보자. 클라이언트는 키보드로부터 한 줄의 문자(데이터)를 읽고 그 데이터를 서버로 보낸다. 서버는 그 데이터를 수신하고 문자를 대문자로 변환한다. 서버는 수정된 데이터를 클라이언트에게 보낸다. 클라이언트는 수정된 데이터를 수니하고 그 줄을 화면에 나타낸다. 2.7.1 UDP를 이용한 소켓 프로그래밍 송신 프로세스가 데이터의 패킷을 소켓 문 밖으로 밀어내기 전에, UDP를 사용할 때 먼저 패킷에 목적지 주소를 붙여 넣어야 한다. 이 패킷이 송신자의 소켓을 통과한 후 인터넷은 이 목적지 주소를 이용하여 그 패킷을 인터넷을 통해 수신 프로세스에 있는 소켓으로 라우트할 것이다. 패킷이 수신 소켓에 도착하면 수신 프로세스는 소켓을 통해 그 패킷을..
[Computer Network] 2.5 P2P 파일 분배
2.5 P2P 파일 분배 클라이언트-서버 파일 분배에서 서버는 파일 복사본을 각 피어들에게 보내야 한다. 서버에서 커다란 부하를 주고 많은 양의 서버 대역폭을 소비한다. P2P 파일 분배에서 각 피어는 수신한 파일의 임의의 부분을 다른 피어들에게 재분배할 수 있어서 서버의 분배 프로세스를 도울 수 있다. P2P 파일 분배 프로토콜 중 유명한 것으로 비트토렌트가 있다. P2P의 핵심은 데이터가 어디있는지 알아내는 것이다! 1. P2P 구조의 확장성 분배 시간(distribution time) 모든 N개의 피어들이 파일의 복사본을 얻는 데 걸리는 시간이다. 클라이언트-서버 피어의 수가 증가함에 따라 분배 시간이 선형적으로 그리고 한계 없이 증가하는 것을 알 수 있다. P2P 구조 최소 분배 시간이 클라이언트..
[Computer Network] 2.4 DNS - 인터넷 디렉터리 서비스
2.4 DNS - 인터넷 디렉터리 서비스 사람을 이름, 주민번호 등으로 식별하는 것과 마찬가지로 인터넷 호스트에 대한 하나의 식별자를 호스트 네임(hostname)이라고 한다. 예) www.facebook.com, www.google.com, gaia.cs.umass.edu 호스트 네임 호스트 위치에 대한 정보를 거의 제공하지 않는다. 가변 길이의 알파뉴메릭 문자로 구성되므로 라우터가 처리하는 데 어려움이 있다. 호스트는 흔히 말하는 IP 주소로도 식별된다. IP 주소 4바이트로 구성되고 계층구조를 갖는다. 0~255의 십진수로 표현하는 각 바이트는 점으로 구분한다. IP주소는 계층구조여서 주소를 왼쪽에서 오른쪽으로 조사함으로써, 그 호스트가 인터넷의어디에 위치하는지에 대한 자세한 정보를 얻을 수 있다...