컴퓨터 네트워크란?

컴퓨터와 컴퓨터를 통신망으로 연결한 것

 

컴퓨터 네트워크를 배울 때는 OSI모형(Open Systems Interconnection Reference Model)을 기반으로 공부한다.

OSI 7계층으로 알고 있는데, 각 계층은 하위 계층의 서비스를 받으면서 상위 계층에게 서비스를 제공한다.

 

먼저 OSI 1계층(물리) 부터 4계층(전송) 계층까지 살펴본 뒤, 리눅스 환경에서 5 세션 계층~ 7 응용 계층 까지 알아보자.

 

OSI 7계층

 

목표

컴퓨터 네트워크의 목표는 간단하다. 컴퓨터로부터 다른 컴퓨터로 데이터를 전송하는 것, 목표는 간단하지만 실제로는 매우 복잡한 과정을 거친다. 전송 계층에서 신뢰성 있는 전송 서비스를 제공하는 것, 네트워크 계층에서 네트워크 노드 간의 라우팅 서비스를 제공하는 것, 데이터 링크 계층에서 물리적으로 연결된 노드에게 데이터를 전송하는 서비스를 제공하는 것, 물리 계층에서 실제로 신호를 비트로 전송하는 서비스를 제공하는 것이 잘 이루어져야 비로소 Host에게 데이터가 전송된다. 이 글에서는 물리 계층과 데이터 링크 계층은 간략하게 언급하고, 네트워크 계층, 전송 계층 그리고 그 상위 계층에 대해서 자세하게 알아보자.

 

먼저 별도의 용어를 정리해보자.

 

- 컴퓨터 네트워크(Computer Network) : 컴퓨터와 컴퓨터를 통신망으로 연결한 것

- 노드(Node) : 컴퓨터 네트워크상에 연결된 장치

- 호스트(Host) : 고유 IP 주소를 가진 노드

- 링크(Link) : 물리적으로 노드와 노드를 연결하는 통로

- 홉(Hop) : 거리의 단위, 보통 한 링크를 이동하면 한 홉이라고 한다.

- 경로(Path) : 네트워크 상의 두 노드 간의 이동 경로

- 프로토콜(Protocol) 데이터 통신을 원활하게 하기 위해 필요한 통신 규약

 

전송 계층에서 제공하는 서비스는 신뢰성 있는 통신인 TCP(Transmission Control Protocol)와 신뢰성 없는 통신인 UDP(User Datagram Protocol)로 나뉜다. 응용 프로그램이 소켓을 통해 보내는 데 데이터 단위는 메시지(Message, TCP 통신에서 데이터 단위는 세그먼트(Segment), UDP 통신에서 데이터 단위는 데이터그램(Datagram)이라고 한다. 네트워크 계층에서는 패킷(Packet)이라는 데이터 단위를 사용하고, 데이터 링크 계층에서는 프레임(Frame), 마지막으로 물리 계층에서는 비트(Bit) 단위로 전송한다. 이 단위는 프로토콜 데이터 단위(Protocol Data Unit)로 알려진 것인데, OSI 모델에서 단위이다. 인터넷 프로토콜 수트(Inter Protocol Suite) 에서는 전송 계층에서의 단위를 세그먼트, 네트워크 계층에서의 단위를 데이터그램, 네트워크 접근 계층에서의 단위를 프레임으로 부른다.

각 계층에서는 하위 계층으로 문제없이 서비스를 잘 받고, 실제로 어떻게 작동하는지 알 필요가 없다는 가정 하에 진행된다. 실제로 어떻게 작동하는지는 알 필요가 없다는 가정 하에 진행된다. 예를 들어 전송 계층에서는 목적지까지 데이터를 잘 전송하는 서비스를 제공하는 것이 목표인데, 하위 계층의 역할인 패킷 경로 제어에 대해서는 관심을 두지 않는다. 이러한 원칙은 투명성(Transparent)으로 널리 알려져 있다. (안보이게 하는 것)

 

연결 지향(Connection Oriented) 프로토콜과 비연결(Connectionless) 프로토콜

통신 연결이 유지되는 것을 지향하는 프로토콜을 연결 지향 프로토콜, 연결을 유지하지 않는 프로토콜을 비연결 프로토콜이라고 한다. 연결 지향 프로토콜은 연결을 계속 유지하기 위한 비용이 들기 때문에 더 비싼 반면 비연결 프로토콜은 연결 유지 비용이 들지 않기 때문에 저렴하다. 예를 들어 전화 연결은 연결된 상태를 유지하기 때문에 연결 지향 프로토콜이라고 볼 수 있다. 비싸다고 무조건 나쁜 것이 아니고, 싸다고 무조건 좋은 것이 아니기 때문에 적절한 선택을 해야한다.

IIP 프로토콜은 비연결 프로토콜이지만 IP 프로토콜을 이용하는 TCP프로토콜은 연결 지향 프로토콜이다. 또 다시 TCP 프로토콜을 이용하는 HTTP 프로토콜은 비연결 프로토콜이다. 이렇든 프로토콜을 어떻게 활용하느냐에 따라 연결지향과 비연결 프로토콜로 바뀔 수 있다.

연결 지향 프로토콜에서는 이미 연결되어 있기 떄문에 어떤 사람이 질의를 보냈는지 연결을 이용하여 알 수 있다. 위에서 예를 든 전화 통화는 이미 통화 연결이 성립될 때 서로 누군지 알기 때문에 연결이 유지되어 있기만 하면 시간이 지난 뒤 다시 말을 해도 누군지 알 수 있다. 하지만 비연결 프토로콜은 매번 새롭게 연결이 성립되기 떄문에 필요한 경우 매 연결 시 자신이 누구인지 알려줘야 한다. 예를 들어 HTTP 프로토콜을 이용한 웹 환경의 경우 쿠키나 세션을 통해 매 번 자신을 식별할 수 있는 정보를 함께 전송한다.

 

전송 계층(Transport Layer)

전송 계층의 역할은 목적지까지 데이터를 잘 도착하도록 하는 것이다. 연결 지향 데이터 스트림 지원, 신뢰성 있는 데이터 전송, 흐름 제어, 그리고 다중화와 같은 편리한 서비스를 제공한다. 전송 계층에서 가장 널리 알려진 프로토콜이 바로 TCP, UDP 프로토콜이다. 앞서 나열한 편리한 서비스들은 거의 다 TCP 프로토콜로 제공되는 것이다. 이러한 편리한 서비스들을 제공하기 위해서는 복잡한 처리를 요구하고, 이는 TCP 프로토콜을 이용하는 비용이 크다는 것을 뜻한다. 때로는 이러한 서비스들이 필요 없는 경우도 있다. 그런 때에는 UDP 프로토콜을 이용하여 저비용으로 통신할 수도 있다.

TCP 프로토콜은 호스트에서만 작동하고, 중간 라우터 노드들에서는 작동하지 않는다. 앞서 언급했듯이 TCP 프로토콜은 복잡한 처리를 요구하기 때문에 모든 중간 라우터 노드들에서까지 TCP 프로토콜을 작동하게 한다면 지금처럼 많은 데이터 전송을 처리할 수가 없기 때문이다.

 

TCP 프로토콜

TCP 프로토콜의 기능은 신뢰성 있는 데이터 전송(Reliable Data Transfer, RDT), 연결 제어(Connection Control), 흐름 제어(Flow Control), 혼잡 제어 (Congestion Control)가 있다. 만약 은행 서비스를 이용하는데 금액에 대한 데이터 전송이 잘 못되어 1억원을 보낸 것이 1만원을 보냈다고 처리되면 끔찍할 것이다. TCP 프로토콜의 신뢰성 있는 전송 기능이 있기 때문에 TCP 프로토콜 기반의 통신은 전송자가 보낸 데이터를 수신자가 그대로 전송받는다고 믿을 수 있다. TCP 프로토로 전송을 시작하는 것부터 각 기능을 제공하기 위한 자세한 방법을 알아보자.

 

 

Multiplexing / Demultiplexing

응용 프로그램이 소켓을 통해 데이터를 전송하는 것부터 TCP 프로토콜이 시작된다. 한 컴퓨터에서 여러 개의 소켓과 프로세스가 존재할 수 있기 때문에 OS에서는 소켓과 프로세스를 식별하기 위해 포트(port) 번호를 따로 둔다. 한 서버에서 여러 소켓과의 연결을 유지하는 것을 생각해보면 왜 이러한 기능이 필요한지 알 수 있을것이다. 그러나 보통 컴퓨터에 연결된 통신 링크는 하나이기 때문에 하나의 링크를 통해 여러 소켓의 데이터를 주고받아야 한다. 이를 위해 OS에서는 전송하려는 데이터를 TCP/UDP 세그먼트로 만들 때 헤더를 추가하여 공통적으로 출발지 포트 번호와 목적지 포트 번호를 둔다. 이러한 작업을 Multiplexing 이라 하고, 목적지에 도착한 세그먼트는 헤더를 확인하여 Demultiplexing 된 뒤 대상 소켓에게 데이터를 전달한다. 편지를 보낼 때 주소뿐만 아니라 그 주소의 누구에게 보내는 것인지도 함께 명시하는 것을 생각하면 이해가 쉬울 것이다. 

 

 

 

 

 

신뢰성 있는 통신

신뢰성 없는 통신을 기반으로 신뢰성 있는(오류 없는) 통신을 지원하기 위해 단계적으로 가정을 줄이고 상황을 일반화시켜나간다. 신뢰성 있는 통신을 한다는 것은 잘못된 데이터를 전송받지 않고, 데어터의 순서 또한 유지되는 통신을 보장한다는 뜻이다. 이 항목에서 설명하는 내용은 이곳을 요약하였다. 아래 그림은 신뢰성 있는 통신 서비스를 어떻게 제공하는지 보여주는 그림이다. 신뢰성 있는 데이터 전송 함수인 rdt_send 함수는 내부적으로 신뢰성 없는 채널을 이용하여 udt_send 함수를 이용하여 구현된다. 

 

 

첫 시작인 rdt1.0 에서는 신뢰성 있는 채널을 통해 데이터 전송이 이뤄진다고 가정한다. 데이터 전송에 에러가 발생하지 않는다는 가정 하의 전송이기 떄문에 rdt_send 함수는 받은 데이터를 패킷으로 만들고 udt_send 함수로 패킷을 전송하기만 해도 신뢰성 있는 통신이 된다. 물론 수신자 측은 받은 패킷을 합쳐 데이터로 돌리면 된다.

 

 

rdt2.0에서는 비트 에러가 존재할 수 있는 상황까지 수용한다. 전화 통화에서 받아쓰기를 한다고 생각해보자. 아마 상대방이 한 문장씩 말할 때마다 잘들었다는 응답(syn) 혹은 다시 말해달라는 응답(Please repeat that)을 통해 받아쓰기를 잘 하고 있는지 확인할 수 있을 것이다. rdt2.0에서는 이 방식을 모티브로 삼아 작동하며, 이러한 응답을 통한 통신조절을 (ARQ(Automatic Repeat request)라고 한다.

rdt2.0에서는 여기에 두 가지 추가적인 기능이 요구된다. 첫 번째로 신뢰성 없는 채널을 통한 통신이 이뤄지기 때문에 비트 에러가 있는지 감지할 수 있어야 한다. 이 감지를 위한 방법으로는 checksum이라는 훌륭한 방법이 있다. 두 번째로 수신자로부터 피드백을 받을 수 있어야 한다. 송신자는 수신자의 어떠한 피드백 없이는 전송이 어떻게 이뤄졌는지 알 수 없다. 이 피드백을 위해 수신자는 송신자로부터 데이터를 성공적으로 받았을 때 ACK, 잘못 받았을 때 NAK을 보낸다. 아래 사진을 보면 수신자 측에서 패킷을 성공적으로 받았을 때 Ack, 잘못 받았을 때 Nak을 보낸다. 아래 사진을 보면 수신자 측에서 패킷을 성공적으로 받았을 때 패킷이 손상되었다면(corrupt) Nak 을 보내고, 패킷이 손상되지 않았다면 Ack(Not Corrupt) 를 봅내는 것을 확인 할 수 있다. 이런 식으로 송신 후 기다리기 때문에 rdt2.0은 stop-and-wait 프로토콜로 알려져 있다. 

 

 

그러나 Ack와 Nak 응답도 에러가 발생할 수 있다. Ack도 Nak도 오지 않으면 송신자 측에서는 무한정 기다리게 된다. 송신 측에서는 에러가 났는지 알 수가 없다. 또한, 중복 송신을 하게 되면 중복수신을 하게 된다.

rdt2.1에서는 순서 번호(Sequence number)를 추가함으로써 중복 수신을 방지한다. 순서 번호만 확인하면 중복된 데이터를 받았는지 알 수 있으므로 중복 수신을 방지할 수 있다. stop-and-wait 프로토콜 상으로는 방금 전송한 패킷이 잘 전송되었는지만 알면 되기 때문에 순서 번호가 0 혹은 1만 있으면 된다. 아래 그림은 rdt2.1을 나타낸 그림이다. 0에 대한 패킷 전송 완료 후에는 1에 대한 패킷 전송을 하고, 그 후에는 다시 0에 대한 패킷을 전송한다. rdt2.0의 가정상 아직 패킷이 유실될 수 있는 상황은 아니기 떄문에 이 방법은 문제가 없다.

 

 

여기서 잘못된 수신에 대한 Nak 응답이 아닌 Ack을 이용한 방법이 가능하다. rdt2.2는 Nak을 사용하지 않는 방법이다. Ack에 순서 번호를 추가함으로써 잘못된 데이터를 받은 것을 다시 송신하게 할 수 있다.

 

 

ㅇ이제는 심지어 패킷이 사라질 수도 있는 채널을 통해 통신한다고 가정하자. 이 경우엔 패킷 손실을 어떻게 감지할 지, 그리고 패킷 손실이 발생하면 어떻게 해야 할 지 생각해봐야 한다. 패킷 손실이 됐을 때 대응방법은 이미 rdt2.2까지의 고민을 통해 알 수 있다. 다시 보내는 것, 쉽고 간단한 방법으로 해결된다. rdt3.0에서는 송신자가 Ack을 받는 것에 대한 타임 아웃 타이머를 둬서 이를 해결한다. 시간 내에 데이터를 성공적으로 수신했다는 응답을 받지 못하면 데이터를 다시 보내는 것이다. 중복된 데이터 수신에 대해서는 이미 rdt2.2 상에서 처리된다.

 

 

rdt3.0까지 발전시켜나감으로써 이제 신뢰성 있는 통신을 할 수 있게 됐다. 하지만 이 방법은 한 번에 한 패킷씩 밖에 보내지 못하기 때문에 성능상으로 만족스럽지 못하다. 매우 먼 거리에 패킷을 보내려 한다면 패킷이 왔다 갔다(Round trip)하는 것을 기다리는 시간 때문에 전송 속도가 매우 떨어질 것이다. 이제는 여러 패킷을 보낼 방법을 고민해야 한다. Ack 을 받기 전에 다수의 패킷을 전송하는 방법을 통틀어 파이프라인 프로토콜이라고 하며, 세부적으로 GBN(Go-Back-N), SR(Selective Repeat) 프로토콜이 있다.

 

Go-Back-N 프로토콜은 수신자 측에서 지금까지 성공적으로 받은 패킷 순서 번호에 대한 Ack을 전송하며, 순서에 맞지 않는 패킷은 성공적으로 수신한 것으로 간주하지 않는다. 따라서, 송신자는 Ack를 받지 못한 가장 오래된 패킷부터 모두 재전송하게 된다. Selective Repeat 프로토콜은 잘못된 순서의 패킷을 받았더라도 버퍼에 저장해둔다. 중간에 수신 실패한 패킷만 다시 전송하게끔 수신자 측은 개별적으로 Ack를 전송하며, 송신자 역시 패킷마다 타임 아웃 타이머를 가진다. Selective Repeat 프로토콜상으로는 상위 계층에게 현재 성공적으로 수신한 패킷까지만 제공함으로써 해당 패킷까지 신뢰성 있게 통신되었음을 보장한다. 아래 사진은 GBN 프로토콜과 SR 프로토콜을 요약한 사진이다.

 

이로써 신뢰성 없는 채널을 통한 신뢰성 있는 통신을 구현하는 방법에 대해 알아보았다. 실제 TCP에서는 Go-Back-N 프로토콜과 Selective Repeat 프로토콜을 하이브리드하여 사용된다고 한다.

 

적절한 타임 아웃 시간 예측

여기서 의문이 생길 수 있는 부분은 타임 아웃 시간은 어떻게 결정할까?

타임 아웃 시간을 너무 짧은 시간으로 두면 재전송 요청을 많이하게 되고, 너무 긴 시간으로 두면 기다리는 시간이 길어진다. 적절한 타임 아웃 시간을 설정하기 위한 방법으로 그떄 그때 확인 된 RTT(Round Trip Time, 패킷이 갔다 오는데 걸린 시간) 인 SampleRtt를 이용하여 다음 RTT인 EstimateRTT를 예측한다. 원리는 이전까지의 RTT와 다음 RTT는 비슷할 것이고, 변화가 생기면 소폭 반영하는 것이다. 식을 살펴보자

 

nextEstimatedRTT = (1-a)*previousEstimatedRTT+a*sampleRTT

적절한 a, 예를들면 0.125 정도를 설정하면 과거의 데이터에 더 비중을 둬서 변화를 수용하게 된다.

 

 

연결 제어

TCP 프로토콜은 연결 지향 프로토콜이고, 신뢰성 있는 통신을 제공하기 위하여 순서 번호를 사용한다고 하였다. TCP 프로토콜에서 통신이 이뤄지기 위해서는 먼저 서로 연결이 되어야 하고, 서로 임의의 시작 순서 번호를 알려줘야 한다. 그 과정을 3-way handshaking 이라고 한다. 다음 박스의 내용은 연결 시작을 위한 3-way handshaking 과정을 보여준다.

 

다음 박스의 내용은 연결 시작을 위한 3-way handshaking 과정을 보여준다.

 

person1 --> person2 SYNchronize with my Initial Sequence Number of X

person1 <-- person2 I received your syn, I ACKnowledge that i am ready for [X+1]

person1 <-- person2 SYNchronize with my Initial Sequence Number of Y

person1 --> person2 I received your syn, I ACKnowledge that i am ready for [Y+1]

 

TCP 프로토콜에서는 연결하자는 뜻으로 SYN 패킷을 보낸다. SYN은 SyNchronize의 약자로 person1은 SYN 패킷과 함께 초기 순서 번호 (Initial Sequence Number, ISN)을 person2에게 보낸다. person2 는 Person1의 초기 순서 번호가 X 인것을 알게 되고, Person1에게 SYN, ACK 가 합쳐진 패킷을 보내면서 자신의 초기 순서 번호가 Y임을 알려준다. 마지막으로 Person1 은 Person2로부터 초기 순서 번호를 잘 받았다는 의미로 ACK을 보낸다. 이 과정을 통해 두 호스트는 신뢰성 있는 통신을 할 수 있는 준비를 마치게 된다.

 

실제로는 3-way handshaking 과정에서 초기 순서 번호 외에도 수신 기본 윈도우 크기(rwnd), 여러 가지 추가적인 옵션 등을 교환하게 된다. 왜 2-way handshaking으로는 안 되는 걸까? 아래 사진은 2-way handshaking의 실패 시나리오다. 호스트 A가 호스트 B에게 연결 요청을 한 것이 딜레이가 많이 되어서 다시 연결 요청을 하는 상황이 발생할 수 있다. 그 경우 호스트 B는 과거의 연결 요청에 대한 순서 번호로 응답을 하게 되고, 호스트 A는 잘못된 순서 번호의 패킷이 왔기 때문에 그 패킷을 버리게 된다. 따라서 성공적으로 통신을 할 수 없게 된다.

 

 

 

 

 

 

대부분 기본적으로 포인터가 무엇인지

포인터를 어떻게 사용해야 하는지 알고 있습니다.

 

int a = 3;

int* p = &a;

int** pp = &p;

 

다음과 같이 어떤 변수의 주소를 나타낸다는 것.

여기까지는 쉽게 알 수 있는 내용입니다.

 

그런데 잘 알고 있다고 생각한 포인터를

사용할 때 가끔 헷갈리는 경우가 있습니다.

 

뭐 문법 이것저것 Visual Studio에서 써보면 알 수 있겠지만

이렇게 시도해보는 것 자체가 시간을 잡아먹는 요인이 됩니다.

 

따라서 이번 포스팅에서는 헷갈릴 수 있을만한

포인터 문법에 대하여 알아보도록 하겠습니다.

 

 

1. 다차원 배열의 등장

 

int arr[4][5];

 

다음과 같은 배열을 선언했을 때 포인터로 어떻게 가리킬까요?

생소하실 수도 있겠지만 문법은 다음과 같습니다.

 

int (*ptr)[5];

 

아! 참고로 이것과 다릅니다 -> int* arr[4];

 

1) int (*ptr)[5] : 열이 5개인 int형 2차원 배열을 가리키는 포인터 변수입니다.

2) int* arr[4] : int형 포인터로 이루어진 배열

 

따라서 위 내용을 헷갈리시면 안 됩니다.

2차원 배열의 주소를 함수로 전달할 때는?

 

void func(int arr[5]);

void func(int (*arr)[5]);

 

좀 더 응용해서 3차원 배열이라면 어떻게 표현할까요?

int arr[3][4][5];

 

이 경우는 다음과 같이 표현합니다.

int (*ptr)[4][5];

 

다음 4차원, 5차원 등은 위 내용을 응용하실 수 있겠죠?

Parallel Binary Search




연습문제로는 8217) 유성 이 있다.



SCPC 2018을 마치고 수원으로 돌아오는 길, 허기가 진 배를 달래기위해 식당을 찾아다녔습니다.


ㄹㅇ녹아버릴것 같아서 시원한걸 먹지않으면 안되었습니다.


양재역에 도착해서 맛집을 찾던 중 북촌손만두로 발걸음을 옮겼습니다,,


1층은 만두찌는 곳, 2층은 테이블이 있었습니다.


1층은 너무 더워서,, 숨을 쉴 수없었지만 2층은 시원하고 좋았습니다~


바로 ~! 모듬만두 하나와 떡갈비냉면 4개를 시켰습니다!






이것은 냉면입니다.


면발이 쫄깃쫄깃하였고, 둥둥 떠다니는 얼음이 정말 좋았습니다.


떡갈비와의 조화도 나쁘지 않았습니다.






다음은 맨두입니다.



육즙이 나오는 만두는 정말 오랜만에 먹었습니다.


육즙을 가두는 법을 아시는 것 같습니다.


튀김만두는 바삭하기까지 했습니다.



SCPC 는 망했지만 밥은 1등으로 잘먹은 것 같습니다!

다음번엔 대회 오답노트로 찾아오겠습니다!




'자기계발과 잠재력개발' 카테고리의 다른 글

맛집탐방 북촌손만두  (3) 2018.08.01
면접 준비  (0) 2018.04.24
  1. 자손9319 2018.08.02 16:12 신고

    돼지냐

  2. ㅎㅎㅎㅎ 2018.08.02 23:09

    맨두 여수로 배달 좀...ㅜㅅㅜ 여긴 북촌손만두 없음..🤤

  3. 꿀귀랑 2018.08.06 21:53

    ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ맨두래ㅋㅋㅋㅋ 근데 냉면 너무 맛있겠다

안녕하세요? ryul입니다.


오늘은 이항계수를 빠르게 구하는 알고리즘에 대해서 공부해보겠습니다.


알고나면 매우 쉽습니다.


먼저 이항계수란?


고등학교 때 배웠던 조합이랑 같은 거라고 생각하시면 됩니다. 

N개의 공 에서 K개의 공을 뽑는 경우의수 를 의미하죠~


기호로는 어떻게 표시할까요?


nCk 

이렇게~


자! 먼저 가장 나이브한 방법으로 nCk 를 구한다면?




Phase 1 나이브



nCk = n! / (k!(n-k)!) 을 직접 계산으로 구하게 됩니다.


이 때 n이 커지게되면 nCk의 값은 분명 기하급수적으로 커지게 되므로 n이 클 경우 분명 문제에서 값을 p로 나눈 나머지를 구하라는 요구를 할 것입니다.




따라서 nCk mod p 의 값을 구해야 하는 것인데, 

단순히 (분모 mod p) / (분자 mod p) 의 값은 우리가 구하고자 하는 값이 아닙니다.



왜냐하면 우리는 나누어 떨어지는 경우 분자와 분모를 약분해야 하는데 단순히 n! mod p 를 구한 후에 하는 계산은 의미가 없습니다.




따라서 일일히 나누어 떨어지는 것부터 계산하게 될 경우 시간이 많이 걸리게 됩니다.




Phase 2 DP




n+1Ck+1 = nCk + nCk+1 이라는 식이 성립하는 것을 알 수 있습니다.

(직접 계산해보면 납득하실 거에요!)




따라서 메모이제이션을 이용하여 dp[n][k] 의 배열을 잡고 동적으로 계산해나간다면 O(n^2)의 시간복잡도로 이항계수를 구할 수 있습니다!




하지만 n이 너무커서 dp로도 되지 않는다면??




phase 3 페르마의 소정리




페르마의 소정리를 이용하겠습니다.


페르마는 말했습니다.

" p를 소수라고할 때 a^(p-1) = 1 (mod p) 이다."




따라서 a * a^(p-2) = 1 (mod p) 라는 것을 알 수 있기 떄문에 우리는 a의 역원이 a^(p-2)라는 것을 알 수 있게됩니다!




즉, 1/a mod p == a^(p-2) 가 되는 것이죠.




따라서 우리가 구하고자 했던 nCk = n! /(k! * (n-k)!) 에서 1 / (k! * (n-k)!) mod p 은 (k! * (n-k)!)^(p-2) mod p 라는 것을 알 수 있죠!!




자! 그렇다면 nCk mod p = ( n! mod p) * ( (k! * (n-k)!)^(p-2) mod p )  입니다.





식이 너무 더러우신가요? 자세히보면 충분히 이해할 수 있습니다.




Phase 4 전처리 후 O(1) 에 사용




n * inverse(n!) = inverse((n-1)!) 라는 식이 성립합니다. 

( 왜 성립하는 지는 식을 계산해보시면 알 수 있습니다!)



따라서 n! 의 inverse 만 분할정복을 통하여 O(log p) 의 시간에 한 번 구해준다면?

메모이제이션을 통하여 n!의 inverse 를 O(n) 의 구할 수 있습니다!





따라서 O(n + logp) 시간 복잡도로 이항 계수 전처리가 수행됩니다.

그 후에는 O(1)의 시간복잡도로 모든 nCk 를 구할 수 있게됩니다.





Phase4 까지 완료한 코드는 다음과 같습니다.


#include <cstdio>
#include <algorithm>
#define P 1000000007LL
typedef long long ll;
using namespace std;
ll fac[4000001], n, k, inv[4000001];//inv[x]의 정의는 x의inverse가 아닌 x!의 inverse
ll power(ll x, ll y) { //분할 정복을 이용하여 x^y 구하기
ll ret = 1;
while (y > 0) {
if (y % 2) {
ret *= x;
ret %= P;
}
x *= x;
x %= P;
y /= 2;
}
return ret;
}
int main() {
fac[1] = 1;
for (int i = 1; i <= 4000000; i++)
fac[i] = (fac[i - 1] * i) % P; //factorial 전처리
inv[4000000] = power(fac[4000000], P - 2); //페르마의 소정리를 이용하여 fac(400만)의 inverse를 구함(이때 분할 정복을 이용하여 logP의 시간에 처리)
for (int i = 4000000 - 1; i >= 0; i--)
inv[i] = (inv[i + 1] * (i + 1)) % P; //inverse(fac(i))=inverse(fac(i+1))*(i+1)이라는 수식을 이용하여 전처리
//총 O(N+logP)시간에 전처리를 끝냄
//전처리가 끝났기 때문에 어떤 쿼리가 들어와도 상수시간에 이항 계수를 계산 가능
scanf("%lld%lld", &n, &k);
if (n == k || !k) {
puts("1");
return 0;
}
ll r = (fac[n] * inv[n - k]) % P;
r = (r*inv[k]) % P;
printf("%lld\n", r);
return 0;
}
출처:[ACM-ICPC 상 탈 사람]


이상 이항계수를 빨리 구하는 법에 대해서 알아봤습니다.


이제 경우의수 식을 잘 세우는 테크닉만 키우면 이 코드를 잘 이용해서 문제를 해결할 수 있습니다!


이상~




'알고리즘' 카테고리의 다른 글

Parallel Binary Search  (0) 2018.08.15
boj2319)사수아탕  (0) 2018.08.15
이항계수를 빠르게 구하는 알고리즘  (3) 2018.07.05
Usaco Gold) Fair Photography  (0) 2018.06.03
[기하] 다각형의 내부 외부 판별  (0) 2018.05.13
BOJ 6171) 땅따먹기  (0) 2018.05.13
  1. 자손9319 2018.07.05 01:57 신고

    아니 이 분 허락도 없이 불펌하시네

Problem


1부터 10억까지 좌표중에, N개의 값을 넣는다. 해당 값은 1~8사이 이다.

이 중 두가지 조건을 만족하는 가장 긴 길이의 범위는?

- 서로다른 K개의 이상의 값이 존재해야한다.

- 각 값들의 갯수는 같아야 한다.



논리 과정


T(b,p) 를 p보다 왼쪽에있는 b의 갯수라고 하자.

- T(b,R) = T(b,L) + c 만약 이 사이에 b 가 존재한다면.

- T(b,R) = T(b,L) 이다 만약 b가 존재하지 않는다면.



따라서 집합 A 와 기준점 p 가 주어지면 우리는 signature S(A,p) 를 만들 수 있다.

- T(b,p) - T(b0,p)  이 때  b0 는 A 안에 첫번쨰 원소이다.

- T(b,p) 는 존재하지 않는것에 대하여.


만약 S(A,L) = S(A,R) 이고 L<R이라면 L-R 은 유효하다.

S는 각 원소들의 차이값이다.


모든 S(A,L) 값을 전처리 한 후 A,R을 고정시키고, 그 와 매칭하는 가장 작은 L을 구해주면 된다.

이 과정에서 MAP 을 이용한다.


K개의 이상의 원소를 포함하는 조건을 만족시키기 위해서 인덱스를 추가한것.


따라서 차이값을 이용해서 map(vector, int) 로 문제를 해결한다. 벡터해쉬


'알고리즘' 카테고리의 다른 글

boj2319)사수아탕  (0) 2018.08.15
이항계수를 빠르게 구하는 알고리즘  (3) 2018.07.05
Usaco Gold) Fair Photography  (0) 2018.06.03
[기하] 다각형의 내부 외부 판별  (0) 2018.05.13
BOJ 6171) 땅따먹기  (0) 2018.05.13
DP최적화 - Convex Hull Trick  (0) 2018.05.06

다각형의 내부 외부 판별이란?



그림1 에는 다각형과 두개의 점 A,B 가 있습니다. 이 그림에서 눈으로 확인했을 때 각 점이 다각형 내부에 있는지, 외부에 있는 지 판별하는 것은 쉽습니다.

이렇게 주어진 점이 다각형 내부에 있는 지 외부에 있는 지 판별하는 것을 다각형의 내부 외부 판이라고 합니다.





아이디어


다각형의 내부에 위치하는 점의 특성


컴퓨터가 특정 점이 다각형 내부에 있는지 어떻게 판별할까요? 

오른쪽으로 반 직선을 그었을 때 다각형과 만나는 점의 개수가 홀수 개라면 내부에 있는 점입니다.



그림2를 보고 이 특징이 맞는지 확인해봅시다. 다각형 외부에 있는점  A는 다각형과의 교점 개수가 2개 즉 짝수개 입니다.

다각형 내부에 있는점 B는 오른쪽으로 그은 반직선과 다각형과의 교점 개수가 3개 즉 홀수 개 입니다. 


이 원칙은 눈으로 도저히 확인할 수 없을 만큼 복잡한 꼭지점이 백만 개 다각형에서도 내부 외부를 판별하는데 적용할 수 있는 강력한 규칙입니다.





구현


어떻게 반 직선과 다각형의 교점 개수를 구하지?


다각형의 내부 외부 판별 규칙은 간단하지만 반직선과 다각형의 교점의 개수를 구하는 것은 쉽지않아보입니다.


반직선과 다각형의 선분과의 교차점을 구한 후에 이 교차점이 선분 위에 있는지 조사하는 방법을 사용해야 할까요?

다행히 반직선은 x축에 항상 평행한 수평선이기 떄문에 비교적 간단하게 다각형의 선분과의 교차점을 구할 수 있습니다.


다각형의 모든 선분들에 대해 반직선과 교점이 존재하는지를 검사합니다. 

반직선과 선분 사이에 교점이 존재하기 위한 조건은 2가지 입니다.


- 점  B 의 y좌표가 두 선분 꼭지점의 y좌표 사이에 있다.

- 점  B를 지나는 수평선과 선분 사이의 교점의 x좌표가 점B의 x좌표보다 크다.




조건1을 만족하는 점B를 지나는 수평 직선과 선분 사이에 반드시 교점이 존재한다.

이 때 오른쪽 반직선과의 교점만 세야하므로 조건2를 추가로 만족해야 반직선과 선분 사이의 교점 존재여부를 올바르게 판별할 수 있습니다.





이제 그림 3과 같은 다각형이 주어졌을 때 점 B의 반직선과 다각형의 교점의 개수를 찾는 과정을 진행해봅시다.

다각형의 10개의 꼭지점은 p[0], p[1] ... p[9] 으로 주어졌습니다.





먼저 그림4처럼 꼭지점 p[0], p[1]을 연결하는 선분과 반직선과의 교차여부를 생각합시다.

 점 B는 선분 (p[0],p[1] ) 의 y좌표 사이에 있고 교점의 x좌표가 점 B보다 크기 떄문에 교차한다고 판단할 수 있습니다.






그림 5와같은 경우에는 조건2를 만족하지 않기 때문에, 교차하지 않는다고 판단해야합니다.



그림 6처럼 꼭지점 p[3],[4] 를 연결하는 선분과의 교차여부를 생각해봅시다. 

선분 (p[3],p[4])의 y좌표 사이에 있지 않기 때문에 교차하지 않는다고 판단합니다.





소스코드


1
2
3
4
5
6
7
/* 점을 구조체로 정의 함 */
strcut vector2{
int x, y;
}
/* STL vector를 이용해서 다각형 자료형을 정의 함 */
typedef vector<vector2> polygon;
 


cs

이제 점 B가 다각형 p 내부에 있는지를 반환하는 함수 isinside 를 정의합니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isInside(vector2 B, const polygon& p){
//crosses는 점q와 오른쪽 반직선과 다각형과의 교점의 개수
int crosses = 0;
for(int i = 0 ; i < p.size() ; i++){
int j = (i+1)%p.size();
//점 B가 선분 (p[i], p[j])의 y좌표 사이에 있음
if((p[i].y > B.y) != (p[j].y > B.y) ){
//atX는 점 B를 지나는 수평선과 선분 (p[i], p[j])의 교점
double atX = (p[j].x- p[i].x)*(B.y-p[i].y)/(p[j].y-p[i].y)+p[i].x;
//atX가 오른쪽 반직선과의 교점이 맞으면 교점의 개수를 증가시킨다.
if(B.x < atX)
crosses++;
}
}
return crosses % 2 > 0;
}
cs


어떤 땅의 i 의 너비 Wi 와 Hi 가 주어진다.

이 때 가격은 Wi * Hi 이다.


- 한번에 여러개  된다면, (해당 땅 중 Wi의 최댓값 ) * (해당 땅 중 Hi의 최댓값)  으로 가격을 매긴다.


따라서 땅을 최소 비용으로 묶어서 살 경우 최소 비용은 ?


일단 무조건 wi를 기준으로 정렬을 시킨다.

이 때 만약 Wi 와 Hi 가 Wj , Hj보다 더 크다면 무조건 묶는게 이득이다. 

따라서 O(n) 시간으로 탐색하면서 더 큰 애들을 지워나간다.


그렇게 되면 현재 Wi 는 오름차순, Hi 는 내림차순으로 정렬된다.

 

그러고 DP를 생각해보자!


DP[i] = min (DP[j-1] + b[j] * a[i]) 의 식이 성립한다. ( b 는 내림차순)


그러므로 Convex Hull Trick 을 사용하면 된다.


이 때 순차적으로 DP[i] 값을 모두 구해나가야 한다.

따라서 O(n* logn) 의 시간복잡도를 지닌다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
typedef long long ll;
 
struct convex{
    vector<ll> M;//기울기을 의미한다.
    vector<ll> B;//y절편의 값들
    //결국 조심해야될것은 이게 getval이나 bad가 long long 범위를 넘어서는지에 대한 거다
    bool bad(int l1,int l2,int l3){
        return (B[l3]-B[l1]*(M[l1]-M[l2]) < (B[l2]-B[l1])*(M[l1]-M[l3]));
    }
 
    double Cross(int a, int b) {
        return (double)(B[b] - B[a]) / (M[a] - M[b]);
    }
 
    void add(ll m,ll b){
        if(M.size()>0){
            if(M[M.size()-1]== m){
                B[M.size()-1]= min(B[M.size()-1],b);
            }
            else{
                M.push_back(m);
                B.push_back(b);
            }
        }
        else{
            M.push_back(m);
            B.push_back(b);
        }
 
        while(M.size()>=3 && Cross(M.size()-3,M.size()-2)> Cross(M.size()-2,M.size()-1) )
        {
            M.erase(M.end()-2);
            B.erase(B.end()-2);
        }
    }
 
    ll getval(ll x,int id){
        return B[id] + x*M[id];
    }
    ll query(ll x){
        int l = 0,r = M.size()-1,mid;
 
        while(l<r){
            mid = (l+r)/2;
            if(Cross(mid,mid+1)>=x)
                r = mid;
            else
                l = mid+1;
        }
        return getval(x,l);
    }
};
 
 
 
 
ll n;
pair<ll,ll> arr[50500];
 
 
int main(){
 
freopen("input.txt","r",stdin);
 
scanf("%lld",&n);
 
for(int i = 0 ; i < n ; i++){
    scanf("%lld %lld",&arr[i].first,&arr[i].second);
}
 
convex cv;
 
sort(arr,arr+n);
reverse(arr,arr+n);
 
ll now = -1;
ll prev = 0;
 
for(int i =0 ; i < n ; i++){
    if(now >= arr[i].second)    
        continue;
    now = arr[i].second;
    cv.add(arr[i].first,prev);
    prev = cv.query(arr[i].second);
}
 
 
printf("%lld",prev);
 
 
}
cs


'알고리즘' 카테고리의 다른 글

Usaco Gold) Fair Photography  (0) 2018.06.03
[기하] 다각형의 내부 외부 판별  (0) 2018.05.13
BOJ 6171) 땅따먹기  (0) 2018.05.13
DP최적화 - Convex Hull Trick  (0) 2018.05.06
Sqrt Decompositon(평방분할) & Mo's Algorithm  (0) 2018.04.05
문자열 해싱  (0) 2018.03.31

* 필요한 상황 

dp[i] = min( dp[j] + b[j]*a[i] ) 를 찾는건데 여기서 b[i] > b[i+1] ( b는 내림차순) 을 반드시 만족한다. (j < i 인 정수)


만약 오름차순이라면 굳이 계산할 필요가 없고, 내림차순이라면 binary search 로 찾을 수 있다.



이런 식이 나온다면 바로 CHT 를 쓸 수 있다.


여기서 문제가 되는 것은 바로 조건에 맞지 않는 직선들을 제거해주는 것이다.



* 업데이트

현재 line1이 새로 추가될 것이라고 생각하자.

그렇다면 line3 , line2 를 현재 저장된 라인들 중 가장 뒤에 있는 라인이라고 하자.


intersect - x(line3,line1) = x1

intersect - x(line3,line2) = x2 라고 해보자.


만약 x1 < x2 라고 한다면 이 직선은 이제 필요없다.


왜냐하면 이미 line3 다음에 line2가 그 다음으로 작아지기 시작하는건데

line3 다음에 이미 line1 이 더 작아졌으므로 애초에 line2는 들어올 필요가 없다.



그리고 라인 업데이트 같은 경우는 사실 이진탐색을 통해서 어디를 없애야하는 지 바로 알 수 있는 방법도 있다.

어차피 식을 보면 binary search를 통해서 충분히 찾을 수 있을 것으로 해석된다.

그런데 보통의 경우는 그렇게 사용되지 않고 O(1) amortized 시간복잡도를 갖게 된다.


* 쿼리 구하기


이제 직선들의 모임에서 x좌표가 어떤 직선에서 가장 최소값이 되는 지를 알아야 한다.


mid, mid+1 의 교점보다 x좌표가 더 작다면 mid 이하의 직선에서 최소값이 등장할 것이고

아니라면 mid+1 이상의 직선에서 최소값이 등장할 것이다.


line 별로 자기만의 최소값 구간이 있다고 보면 조금 편하다.

그렇다면 교점보다 x좌표가 더 작다면 최소값은 mid 이하의 점에서 나올것이 분명하다.


왜냐하면 이 친구의 mid+1 최소값 범위에는 x가 들어오지 않기 때문이다.


굉장히 쉽게 문제를 풀 수 있다.



* 예시문제 


https://www.acmicpc.net/problem/5498


https://www.acmicpc.net/problem/3319


http://www.spoj.com/problems/NKLEAVES/


http://codeforces.com/contest/311/problem/B


https://www.acmicpc.net/problem/4008


https://www.acmicpc.net/problem/2192


http://codeforces.com/contest/311/problem/B


http://codeforces.com/problemset/problem/377/E



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
어떤 경우에서도 항상 통하는 방법.
#define ll long long
 
struct convex{
    vector<ll> M;//기울기을 의미한다.
    vector<ll> B;//y절편의 값들
    //결국 조심해야될것은 이게 getval이나 bad가 long long 범위를 넘어서는지에 대한 거다
    bool bad(int l1,int l2,int l3){
        return (B[l3]-B[l1]*(M[l1]-M[l2]) < (B[l2]-B[l1])*(M[l1]-M[l3]));
    }
 
    double Cross(int a, int b) {
        return (double)(B[b] - B[a]) / (M[a] - M[b]);
    }
 
    void add(ll m,ll b){
        if(M.size()>0){
            if(M[M.size()-1]== m){
                B[M.size()-1]= min(B[M.size()-1],b);
            }
            else{
                M.push_back(m);
                B.push_back(b);
            }
        }
        else{
            M.push_back(m);
            B.push_back(b);
        }
 
        while(M.size()>=3 && Cross(M.size()-3,M.size()-2)> Cross(M.size()-2,M.size()-1) )
        {
            M.erase(M.end()-2);
            B.erase(B.end()-2);
        }
    }
 
    ll getval(ll x,int id){
        return B[id] + x*M[id];
    }
    ll query(ll x){
        int l = 0,r = M.size()-1,mid;
 
        while(l<r){
 
            mid = (l+r)/2;
            if(Cross(mid,mid+1)>=x)
                r = mid;
            else
                l = mid+1;
        }
        return getval(x,l);
    }
};
 
 
 
2. X가 증가형태로 주어지는 경우. O(1)으로 해결하는 방법.
 
struct convex{
    ll M[N],B[N];
    int sz,pos;
    double Cross(int a, int b) {
        return (double)(B[b] - B[a]) / (M[a] - M[b]);
    }
 
    void add(ll m,ll b){    
        M[sz] = m;
        B[sz++]= b;
 
        while(sz-pos>2&& Cross(sz-3,sz-2)> Cross(sz-2,sz-1) ){
            M[sz-2]= M[sz-1];
            B[sz-2]= B[sz-1];
            —sz;
        }
    }
 
    ll getval(ll x,int id){
        return B[id] + x*M[id];
    }
    ll query(ll x){
 
        while(pos+1<sz){
            if(Cross(pos,pos+1)<=x)++pos;
            else
                break;
        }
        return getval(x,pos);
    }
};
cs


'알고리즘' 카테고리의 다른 글

[기하] 다각형의 내부 외부 판별  (0) 2018.05.13
BOJ 6171) 땅따먹기  (0) 2018.05.13
DP최적화 - Convex Hull Trick  (0) 2018.05.06
Sqrt Decompositon(평방분할) & Mo's Algorithm  (0) 2018.04.05
문자열 해싱  (0) 2018.03.31
Min Path Cover in DAG  (0) 2018.03.31

+ Recent posts