일반적으로 외부로부터 내부로 오는 요청에 대한 처리를 할 경우, 포트 포워딩을 실시할 수도 있겠지만, 현실적으로 모든 사용자가 이런 설정을 하지는 않습니다.
때문에 P2P(온라인 게임, 화상 채팅 등) 같은 프로그램들은 자동으로 NAT을 뚫어주는 방식을 활용하는데, 여기에 대표적인 기술로 홀 펀칭(Hole Punching)이 있습니다.
[홀 펀칭(Hole Punching) 이란]
홀 펀칭(Hole Punching)은 NAT/공유기 뒤에 있는 두 클라이언트가 서로 직접 연결할 수 있게 NAT에 구멍을 만들어주는 기술입니다. UDP 기반 통신에서 많이 활용하는데(TCP도 가능은 한데 UDP보다 어려움) P2P 기반으로 통신을 진행하는 경우 많이 활용됩니다.
포트 포워딩의 경우에는 사용자가 직접 공유기 설정을 통해 포트를 개방하는 것이지만, 홀 펀칭의 경우엔 서버(프로그램)이 자동으로 NAT에 구멍을 만들어서 외부와 연결할 수 있도록 해주는 것입니다.
[홀 펀칭 동작 원리(UDP 통신)]
A(192.168.0.2)와 B(192.168.0.3)이 사설망 뒤에 존재한다고 가정해보겠습니다. 공인 IP는 있지만 NAT 때문에 외부에서 직접 접근이 불가능한 상황입니다. 단순 접속 시도는 공유기가 "어떤 PC에 접근해야하는지"를 모르기 때문에 접속 실패가 발생합니다. 이를 위해 홀 펀칭을 통해 통신을 시도하는 경우를 알아보도록 하겠습니다.
1. 중앙 서버(시그널링 서버)가 준비 : A와 B의 공인 IP와 포트 넘버를 알아냄
1-1. A의 공인 IP와 포트 넘버 = 220.x.x.x:50001
1-2. B의 공인 IP와 포트 넘버 = 121.x.x.x:60002
2. 서버가 A와 B에게 서로의 주소(공인 IP와 포트 넘버)를 알려줌
3. A와 B가 동시에 접속 시도
3-1. A는 B의 공인IP:포트넘버로 UDP 패킷 전송
3-2. B는 A의 공인IP:포트넘버로 UDP 패킷 전송
4. NAT은 "내부에서 특정 외부 주소로 나간 연결"이 있으면 그 주소에서 오는 응답을 허용, 그래서 두 쪽이 동시에 패킷을 보낼 경우, NAT이 각각 구멍을 열고 서로 패킷을 수신할 수 있게 됨
5. 이제 A와 B는 중앙 서버를 거치지 않고 통신 가능해짐
그래도 이 또한 NAT 종류에 따라 다를 수 있습니다. 방화벽 정책이 다르거나 대칭형 NAT의 경우엔 홀 펀칭이 이뤄지지 않을 수 있기 때문입니다. 이 경우에는 또 대안으로 STUN/TURN 서버를 활용할 수 있습니다.
기본적으로 NAT은 내부에서 외부로 요청하는 경우에만 자동으로 응답을 돌려주고, 반대의 경우에는 응답을 돌려주지 않습니다. 때문에 외부에서 내부로 연결 요청이 들어올 때는 공유기가 포트를 열어둔 PC를 알지 못하는 상태가 되는데, 이 문제를 해결하기 위하여 포트 포워딩을 활용합니다.
포트 포워딩이란 특정 공인 IP의 특정 포트에서 내부 특정 IP와 특정 포트로 연결 가능하도록 해주는 기능입니다. 즉, 외부에서 들어오는 연결을 공유기가 특정 내부 PC(or 서버)로 넘겨주도록 설정하는 것입니다.
[필요 이유]
집에서 게임 서버(192.168.0.10:7777)를 구축했고, 여기에 친구가 접속하고자 합니다. 소지중인 공유기의 IP는 220.x.x.x로 가정하겠습니다. 이 경우 기본 NAT 상태라면 외부에서 220.x.x.x:7777로 접속을 시도해도 공유기는 "어느 내부 PC에 연결하는 것인지?"를 모릅니다(연결 실패).
이에 대한 해결책으로 공유기 설정에서 포트 포워딩을 실시합니다. 7777 포트에 대한 접속은 192.168.0.10:7777로 접속하도록 설정하는 것입니다. 이렇게 해주면 외부에서 220.x.x.x:7777로 연결을 시도할 경우, 공유기가 연결을 192.168.0.10:7777로 유도해줍니다(트래픽을 해당 위치로 전달).
CPU는 크게 ALU, CU(컨트롤 유닛), 레지스터로 구성되어 있습니다. CU는 명령어를 해독하여 어떤 부품이 어떤 작업을 실행해야 하는지, 어떤 연산을 실행해야 하는지 등을 결정짓는 역할을 합니다. ALU는 CU로부터 명령받은 산술, 논리 연산을 진행하게 됩니다. 레지스터는 ALU에서 실행된 연산의 결과값이나 연산에 사용될 데이터를 저장하는 역할을 합니다.
[CPU]
> ALU (Arithmetic Logic Unit)
: CPU 내부에서 연산을 담당하는 블록으로, 덧셈과 뺏셈과 같은 산술 연산과 AND와 OR같은 논리 연산을 수행합니다.
> 컨트롤 유닛 (Control Unit)
: 명령어 해독을 위해 존재하는 블록으로, 어떤 부품이 어떤 작업을 실행해야 하는지, 어떤 연산을 실행해야하는지를 결정해줍니다.
예를들어 ALU에게 1과 0으로 이루어진 명령어가 전송되었다고 가정해보겠습니다. ALU는 이 "명령어"라는 것이 명령어인지 아닌지, 무엇을 하는지 알 수가 없습니다. 이 명령어에 대한 해석을 컨트롤 유닛이 실시해주는 것입니다.
> 레지스터 (Register)
: CPU 내부에 존재하는 아주 작은 메모리로, ALU의 연산 결과나 연산을 위해 필요한 데이터들을 저장하는 공간입니다. 데이터는 2진 데이터(Binary Data) 형태로 저장됩니다.
> 버스 인터페이스 (Bus Interface)
: 그렇다면 명령어는 어디서 전송되는 것일까요? 컴퓨터는 여러 하드웨어로 구성되어 있으며, 이들은 독립적으로 존재하지 않고 데이터를 주고받을 수 있도록 설계되어 있습니다. 이 주고 받기 위한 매개체로써 입출력 버스(I/O Bus)가 존재하는데, 이것만 존재해서는 원할한 통신이 불가능합니다.
그렇다면 통신 해석을 위한 별도의 장치가 필요한데, 그것이 바로 버스 인터페이스입니다. 버스 인터페이스는 어떻게 데이터를 전송하는지, 어떻게 수신해야하는지 등의 프로토콜 또는 통신 방식을 해석할 수 있는 장치로써 역할을 수행하는 것입니다.
> 클럭 신호 (Clock Pulse)
: 클럭 신호는 구성요소까진 아니지만, 타이밍 기능을 위해 존재합니다. 1.6Mhz의 클럭 속도를 갖는 CPU는 초당 1,600,000(160만)번의 클럭을 발생시킨다는 것입니다. 이것은 초당 160만번의 작업(연산)을 수행할 수 있다는 뜻이 되는데, 어째서 이런 기능이 필요한 것일까요?
바로 동기화를 위해 존재합니다. 예를들어 다음과 같은 연산 과정이 있다고 가정해보겠습니다.
input 1과 input 2를 통해 데이터가 계속 들어오는 상황에서 + 연산 장치는 '+' 연산을 실시하고 출력 장치는 BUFFER에 존재하는 데이터를 가져가 출력하는 작업을 수행합니다. 만약 둘의 작업 속도가 다르다면 다음과 같은 문제가 발생할 수 있습니다.
1. 출력 장치 작업 속도가 빠를 경우 : 한 번 가져간 데이터를 다시 가져가 출력
2. 연산 장치 작업 속도가 빠를 경우 : 버퍼를 덮어써서 결과 일부가 출력되지 않을 수 있음
이 문제를 해결하는 방법이 바로 동기화입니다. 보통 가장 느린 작업에 다른 장치들의 속도를 동기화 시킵니다.
2차원에서는 강체 회전에 대해 어느 방향으로 회전해도 한 개의 좌표 θ로 나타낼 수 있지만, 3차원에서는 이게 불가능합니다. 아래 그림을 통해 알아보겠습니다.
1) x축 기준으로 +90º, y축 기준으로 +90º 회전2) y축 기준으로 +90º, x축 기준으로 +90º 회전
각 축을 기준으로 회전 양은 90º으로 같지만, 순서의 차이로 인해 좌표 축이 가리키는 방향이 기존과 아예 달라지는 것을 확인할 수 있습니다. 이처럼 3차원에서는 회전하는 방향의 순서에 따라 강체의 자세(가리키는 방향)가 달라지기 때문에, 회전하는 세 개의 각도 순서를 정하여 강체의 자세를 나타내는 오일러 각도를 사용합니다.
오일러 각(Euler angle)은 강체(Rigid body)가 놓은 방향(위치, 회전 포함)을 3차원 공간에 표시하기 위해 레온하르트 오일러가 고안한 세 개의 각도 표기법입니다.
포트 넘버(Port Number)는 인터넷 프로토콜인 TCP/IP를 통해 네트워크 상 컴퓨터 간 특정 프로세스를 지정하는 수단으로 사용됩니다.
다른 네트워크 상 통신은 IP Address, 같은 네트워크 상 통신은 MAC Address를 통해 실시되지만, 지정된 컴퓨터 내에도 여러 종류의 프로세스가 존재합니다. 막상 컴퓨터에 도착해도 해당 데이터가 어떤 프로세스에 가야할 지 모르기 때문에, 이를 위해 포트 넘버가 필요한 것입니다.
해당 번호는 0~65535번까지 존재하며 크게 세 종류로 구분됩니다.
> Well-Known Port(0 ~ 1023)
0번부터 1023번까지는 특정 프로토콜의 애플리케이션이 사용할 지 정해져 있습니다.
> Registered Port(1024 ~ 49151)
기관이나 사업자들을 위해 지정된 포트 넘버들 입니다. MySQL(3306), HTTP 대체(8080), MongoDB(27017) 등이 있습니다.
> Dynamic Port(49152 ~ 65535)
사용자가 자유롭게, 임의로 지정할 수 있는 포트 넘버들입니다. 언제든지 활용 가능한 영역이기 때문에 특별히 정해진 것은 없습니다.
멀티 프로세싱은 하나의 프로그램을 여러 개의 프로세스로 나누어 각각의 프로세스가 하나의 작업을 병렬적으로 처리하도록 하는 방법입니다. 하지만 멀티 스레딩과 다르게 멀티 프로세싱의 경우, 각 프로세스는 고유한 메모리 영역을 가지고 있기 때문에 일반적으로는 서로간 데이터 공유, 전달이 않고 문제가 생기더라도 다른 프로세스에 영향을 미치지 않습니다.
여기서 서로간 데이터를 주고받기(통신하기) 위한 기능을 활용할 수 있는데, 이를 IPC(Inter Process Communication)라고 합니다. 여기에는 여러 가지 방법들이 존재합니다.
- Pipe
- Message Queue
- Shared Memory
- Socket
- Semaphore
- File Mapping
[Pipe]
통신을 위한 메모리 공간(버퍼)를 할당하여, 데이터를 주고받을 수 있도록 하는 방법입니다. 단방향 통신에 주로 활용되며 하나의 프로세스는 데이터를 쓰기만, 다른 프로세스는 데이터를 읽기만 합니다. 만약 하나의 프로세스가 읽기/쓰기 작업을 모두 해야한다면 새로운 파이프를 추가하여 양방향 통신을 실시하면 됩니다.
하지만 파이프는 애초에 간단한 구현 및 활용을 위해 설계된 방법이기 때문에 양방향 통신을 위해 활용하는 것은 실용적이지 않은 방법입니다(구현의 복잡도 증가). 파이프는 보통 부모-자식 프로세스 간 통신을 위해 활용되며, Anonymous Pipe와 Named Pipe가 있습니다.
> Anonymous Pipe
부모-자식 관계에 있는 프로세스간 파이프 통신은 Anonymous Pipe를 활용합니다. Unnamed Pipe라고도 불리우며 명확하게 어떤 프로세스에 데이터를 전송할 지 정해져 있을 경우 활용하는 것입니다. 보통 PPID(부모 프로세스 ID)를 통해 파이프에 접근할 수 있습니다.
- Pipe 함수를 통해 Pipe 생성
- 부모-자식 관계의 프로세스 통신 시 활용(아닐 시 통신 불가)
- 파이프를 위한 메모리 공간 할당
- 단방향 통신(한쪽은 쓰기, 한쪽은 읽기만 가능)
> Named Pipe
프로세스 간 연관관계가 없는, 즉 독립적인 프로세스간 통신 시 Named Pipe를 활용합니다. Anonymous Pipe과는 다르게 버퍼를 할당하지 않고 파일을 통해 통신합니다. 파일을 사용할 때는 읽기/쓰기 둘 중 하나만 사용할 수 있으므로 결국 반이중 통신이라고 볼 수 있습니다. 다수의 클라이언트를 처리하기에는 비효율적인 방법입니다.
- mkfifo 함수를 통해 파이프로 사용할 파일을 생성
- 독립적인 프로세스 간 통신을 위해 사용
- 반이중 방식(읽기, 쓰기 모두 가능하지만, 한 번에 하나씩만 가능)
[Message Queue]
메시지 큐(Message Queue)는 다중 프로세스 간 통신을 위해 사용되는 방법으로, 큐의 FIFO(First In First Out) 형태를 가집니다. Named Pipe와는 다르게 메모리 공간에서 통신이 이루어지며(버퍼가 할당됨), 비동기 통신기 가능하고 식별자에 의해 데이터들이 식별되어 여러 프로세스가 동시에 원하는 데이터로의 접근이 가능해집니다. 다만 구현이 복잡하고 메시지 크기에 제한이 있을 수 있습니다.
[Shared Memory]
여러 프로세스가 메모리 영역을 공유하여 데이터를 주고받는 Shared Memory(공유 메모리)는 중개자 없이 메모리에 접근하기 때문에 빠른 속도로 데이터를 공유할 수 있게 됩니다. 하지만 동시에 여러 프로세스가 접근하여 동기화 문제가 발생할 수 있어 관리에 주의가 필요합니다.
[Memory Map]
메모리 매핑(Memory Map)은 디스크에 있는 파일의 일부분 또는 전체 파일을 응용 프로그램 주소 공간 내 특정 범위의 주소로 매핑하는 메커니즘입니다. 공유 메모리와 유사하게 메모리 공간을 공유한다는 공통점이 있지만, 해당 메모리 공간을 파일과 매핑하여 공유합니다.
메모리 매핑도 공유 메모리와 같이 빠른 속도를 자랑하나, 파일 I/O와 같은 기능을 수행할 경우에는 낮은 성능을 보일 수 있습니다. 파일을 바로 연결하기 때문에 버퍼를 사용하지 않고 페이지(Page)를 활용하여 데이터 처리가 가능해집니다.
[Socket]
소켓(Socket)은 네트워크를 통해 프로세스 간 통신을 실시할 때 사용되는 방법입니다. 파이프 개념을 네트워크로 확장시킨 것으로 볼 수 있으며, 주로 Client-Server 모델이나, Peer-to-Peer 모델에서 사용합니다.
동일한 시스템 내에서는 UDS(Unix Domain Socket)로 IPC를 지원할 수 있고, 다른 네트워크 상에서는 Network Socket을 사용하게 됩니다.
- 클라이언트와 서버가 특정 포트를 통해 양방향 통신하는 방법
- 데이터 전달 후 연결이 끊어지지 않고 계속적으로 통신
- 클라이언트와 서버가 실시간으로 데이터를 주고받는 경우 활용
- 실시간 동영상 스트리밍, 온라인 게임 등에서 주로 활용
> TCP(Transmission Control Protocol)
클라이언트와 서버가 연결을 맺고, 안전하게 데이터를 주고받는 방법입니다. 연결 지향 통신 방법이라고도 하며, 헤더에 패킷에 대한 신뢰성 검사와 흐름제어 등을 실시합니다. 때문에 데이터 전송과 순서가 보장됩니다.
클라이언트와 서버는 socket()으로 소켓을 생성하고, connect()와 accept()로 연결을 실시한 뒤, 데이터를 send()와 recv()를 활용하여 스트림을 통해 주고받습니다.
> UDP(User Domain Protocol)
비연결 지향적인 통신 방법으로, 클라이언트와 서버가 연결을 맺지 않고 데이터를 주고 받아 TCP와 다르게 신뢰성 검사나 흐름 제어등을 실시하지 않습니다. 덕분에 TCP보다 빠르게 데이터 전송이 가능합니다.
클라이언트와 서버는 socket()으로 소켓을 생성하고, 바인딩 후 sendto()와 recvfrom()을 활용하여 데이터를 주고받습니다.
IP Address(Internet Protocol Address; IP 주소)는 컴퓨터들이 서로를 인식하고 통신하기 위해 사용하는 고유하고 특수한 번호입니다. 해당 번호를 활용하여 발신자로부터 수신자라는 목적지를 향해 메시지가 전송됩니다.
해당 번호는 통신기기마다 고유하게 할당되어 있는 것이 아니라, 네트워크 관리자나 인터넷 서비스 공급자로부터 제공받기 때문에 경우에 따라 변경될 수 있으며, 번호가 겹칠 수도 있습니다.
보통 IPv4로 숫자가 표현되는데(ex : 127.0.0.1), 번호를 외우기는 어렵기 때문에 숫자가 아닌 도메인으로 변환하여 사용하는 경우가 있습니다(ex : naver.com). 이렇게 IP 주소와 도메인을 매핑하고 변환시켜주는 작업은 DNS(Domain Name System)가 해줍니다.
서브넷 마스크라는 단어를 들어본 적이 있을 수 있습니다. 이는 IP 주소에서 네트워크 주소와 호스트 주소를 나눠주는 역할을 수행합니다. 호스트들 간의 네트워크 통신은 같은 네트워크 주소나 네트워크 대역 내에서만 이뤄지는데, 다른 네트워크 대역의 호스트들과 연결하는 방법은 라우팅(Routing)과 연관되어 있습니다. 똑같은 IP 주소라 할지라도, 서브넷 마스크가 다르면 IP 주소가 의미하는 바가 완전히 달라집니다.
[MAC Address]
MAC Address(Media Access Control Address; MAC 주소)는 48bit로 표현되는 숫자(ex : 00:C0:4F:48:E1:28)로, LAN 내에서 장비를 식별하는데 사용됩니다. TCP/IP 4계층의 Data Link Layer에서 사용되고, 디바이스마다 고유하게 할당됩니다(이더넷 하드웨어 주소라고도 불림). 같은 네트워크 안에서 통신할 경우에는 MAC 주소만 있어도 통신이 가능합니다.
+) 이더넷(Ethernet)은 같은 네트워크 간 존재하는 장치들 사이를 뜻하고, 다른 네트워크 간 장치들 간의 통신은 인터넷(Internet)이라고 함
주소 형태는 MM:MM:MM:SS:SS:SS 형태로 MM:MM:MM은 제조업체의 3byte주소, SS:SS:SS는 NIC 카드 일련번호 입니다. MAC 주소를 알아보기 위한 프로토콜로 ARP(Address Resolution Protocol)가 존재합니다.
해당 주소는 외부에서 내부의 사설 IP로 통신을 요청할 때 중요한 역할을 수행합니다. 사설 IP는 외부에서 볼 수 없기 때문에 외부에서는 어떤 사설 IP가 최종 목적지인지 알 수 없는데, 이 최종 목적지를 MAC 주소가 알고 있습니다.
[네트워크 통신에 둘 다 필요한 이유]
Data Link Layer(2계층)에서 MAC 주소만 활용하는 이유는 해당 계층이 같은 네트워크 내에서 데이터를 전달할 때 물리 주소를 사용하여 목적지의 기기를 찾기만 하면 되기 때문입니다.
Network Layer에서 IP 주소를 활용하는 이유는 해당 계층이 서로 다른 네트워크 간의 패킷 전송에 있어 논리적 주소를 이용하여 경로를 찾고 데이터가 전달되기 때문입니다(라우팅).
만약 2계층에서도 IP 주소만을 사용한다면, 물리적 주소인 MAC 주소가 없기 때문에 같은 네트워크 내에서 고유한 기기를 구별하여 데이터를 전달하는데에 한계가 발생합니다. 반대로 3계층에서 MAC 주소만을 활용한다면, 글로벌 네트워크 환경에서 효과적인 라우팅과 데이터 전송을 위한 충분한 데이터를 제공받을 수 없게 됩니다.
따라서 MAC 주소와 IP 주소 모두 네트워크 통신을 위해 필요합니다.
[IPv4와 IPv6]
IPv4는 IP를 32bit로 표현하는 방법입니다. 12개의 숫자가 3개의 숫자마다 점(.)으로 구분되며, 각 그룹(4그룹)은 0~255의 범위를 갖습니다. 고로 0.0.0.0부터 255.255.255.255로 표현될 수 있습니다.
IPv6는 IP를 128bit로 표현하는 방법입니다. 32개의 숫자가 4개의 숫자마다 콜론(:)으로 구분되며, 각 그룹(8그룹)은 16진수로 표현됩니다(ex : 2001:0BD8:85A3:0000:0000:8A2E:0370:7334).
IPv4로는 약 49억개의 숫자를 표현할 수 있는데, 사실 현대에 컴퓨터 갯수는 이를 아득히 넘어섭니다. 따라서 모든 장치에 고유한 IP 주소를 부여해주기 위하여 IPv6 방식이 탄생하게 되었습니다. 그래도 현재까지 IPv4 통신을 활용하기 위한 다른 체계도 있고(서브넷 마스크의 활용) 모든 컴퓨터 기기 주소를 IPv6 체계로 바꾸기에는 상당한 비용이 발생하기 떄문에 IPv4를 계속해서 사용중에 있습니다.
맨허튼 거리(Manhattan Distance), 혹은 택시 거리, 시가지 거리라 불리우는 거리 공간은 다음의 이미지를 통해 살펴보도록 하겠습니다.
출처 : https://needjarvis.tistory.com/455
초록색 선은 두 점 사이의 유클리드 거리값을 나타냅니다. 하지만 단위 이름과 같이, 맨허튼이라는 "도시"를 대상으로 격자 내 두 점 사이의 거리값을 구하는 공식이기 때문에 실제로는 초록색 선이 길이값이 될 수 없습니다(하얀색 부분은 건물이 존재하기 때문). 따라서 다른색 선과 같이 길이를 구해야합니다.
그렇다면 빨간색, 파란색, 노란색 선 중 어떤 선이 가장 최소 단위의 거리값이 될 수 있을까요? 파란색 선이 초록색 선과 가장 가깝기 때문에 파란색이라고 할 수도 있지만, 실제로는 빨간색, 파란색, 노란색 선 모두 같은 길이값을 가지게 됩니다. 이것이 바로 맨허튼 거리입니다.
위 그림에서 왼쪽 아래 점P(x1, y1), 오른쪽 위 점Q(x2, y2)가 존재할 때, 맨허튼 거리 d를 구하는 공식은 다음과 같습니다.
2차원 좌표계의 맨허튼 거리
단순하게 x값과 y값의 차이를 절대값으로 바꿔서 더하는 방식을 취합니다. 3차원 좌표계의 맨허튼 거리는 다음과 같습니다.
주어진 네 종류의 물건에 대해, 7kg 내에서 최대 가치합을 만들어내야 하는데, 해당 문제에서는 DFS를 활용하면 시간 초과가 발생합니다. 따라서 DP를 활용해야하는데 이를 위한 접근 방식은 다음과 같습니다.
테이블은 어떤 식으로 물건을 넣어야지 최대 가치합이 발생하는지 판별하기 위한 테이블입니다. 행은 순서대로 1번부터 4번까지 있으며 다음과 같은 의미를 가지고 있습니다.
- 1번 : 1번 물건만 고려한 경우
- 2번 : 1번, 2번 물건을 고려한 경우
- 3번 : 1번, 2번, 3번 물건을 고려한 경우
- 4번 : 1번, 2번, 3번, 4번 물건을 고려한 경우
> 1번 물건만 고려한 경우
1번 물건만 넣을 수 있는 경우를 고려하면, 무게가 6이기 때문에 제한이 6 이상일 때 넣을 수 있게 됩니다. 따라서 Limit 6과 7에 1번 물건의 가치인 13을 기록해줍니다.
> 1번, 2번 물건을 고려한 경우
여기서부터는 1번, 2번 물건 두 개가 주어진 상황입니다. 두 물건 모두 무게가 4 이상이기 때문에, Limit 3까지는 넣을 수 없어 0으로 기록해줍니다. Limit 4부터는 2번 물건을 넣을 수 있게 됩니다. Limit 4와 5까지 2번 물건의 가치인 8을 기록해줍니다.
Limit 5부터는 경우의 수가 생깁니다. 바로 1번 물건도 넣을 수 있게 되기 때문입니다. 이 경우에는 당연히 가치가 더 높은 1번 물건을 넣어주는게 좋기 때문에 Limit 6부터 1번 무게의 가치인 13을 기록해줍니다.
> 1번, 2번, 3번 물건을 고려한 경우
이제 3번 물건까지 넣을 경우를 고려해야 합니다. 3번 물건은 무게 3에 가치 6을 갖습니다. 따라서 Limit 3 이상으로 6을 기록해줍니다. 이후 Limit 4에서는 2번 물건도 담을 수 있게 됩니다. 이 경우에는 3번 물건보다 2번 물건이 가치가 더 높기 때문에 8을 기록해줍니다.
이런 식으로 Limit 5는 또 2번 물건, Limit 6번은 1번이 가치가 제일 높아 13을 기록해주지만, Limit 7에서 한 가지 경우의 수가 또 발생합니다. 바로 무게 6짜리인 1번 물건 하나를 넣는 것보다, 무게 4와 무게 3을 갖는 2번, 3번 물건의 가치 합이 14로 더 크기 때문입니다. 따라서 1번 물건의 가치를 지워주고 2, 3번 물건을 넣은 경우의 가치인 14를 기록해줍니다.
> 1번, 2번, 3번, 4번 물건을 고려한 경우
4번 물건까지 고려할 경우, 기존의 방식대로 기록하면 Limit 3은 3번 물건만, Limit 4는 2번 물건만 넣지만 Limit 5의 경우 새로 넣을 수 있는 4번 물건(무게5, 가치 12)을 넣는 경우가 가치합이 가장 큽니다. 이를 위해 Limit 5는 4번 물건의 가치를 기록해줍니다.
다음으로 Limit 6은 동일하게 1번 물건의 가치를 기록하고, Limit 7은 14를 기록해줍니다. 문제는 이런 식으로 값을 기록하여 마지막에 기록된 값인 14를 리턴해주면 됩니다.
[점화식 세워보기 / 풀이]
위의 테이블을 직접 채우는 과정을 봤다면, 어느정도 일반화된 점화식이 보일 것입니다. 물건을 i번째까지 고려했을 때, 배낭의 허용 무게가 j일 경우 얻을 수 있는 최대 가치를 DP[i][j]라고 정의하겠습니다. 이때 두 가지 경우의 수를 나눌 수 있습니다.
1. i번째 물건을 넣지 않는 경우
: 이때 최대 가치는 이전까지 고려한 상태와 동일함
DP[i - 1][j]
2. i번째 물건을 넣는 경우
: 하지만 i번째 물건의 무게가 현재 허용 무게 j이하일 경우에만 가능함, 이 경우의 가치는 i번째 물건의 가치 + (남은 무게에서 얻을 수 있는 최대 가치)가 됨
DP[i - 1][j - Weight] + Value
> 여기서 DP[i - 1][j - Weight]라는 식은 현재 i번째 물건을 넣었을 때, 남는 무게 공간을 뜻합니다(이 상태에서의 최대 가치는 DP[i - 1][j]). 이 가치와 현재 선택해서 넣은 물건의 가치를 넣어줍니다.
이를 점화식으로 표현하면 다음과 같습니다.
즉, 칸을 채워 넣는 과정은 "현재 물건을 넣느냐, 안 넣느냐"의 두 경우를 비교하여 더 큰 값을 선택하는 과정입니다. 이를 코드로 표현하면 다음과 같습니다.
// 백준 12865 평범한 배낭
// 골드5
// 1 ≤ N ≤ 1,000,000(10^6)
#include <iostream>
#include <vector>
using namespace std;
// N개의 물건이 W무게와 V가치를 가짐
// 최대 K만큼의 무게 제한에 대해, V(가치) 합을 최대로 만들기
struct Goods
{
int Weight = 0;
int Value = 0;
};
int main()
{
int N, K;
cin >> N >> K; // N : 물건 갯수, K : 최대 무게 제한
vector<Goods> GoodsTable(N, { 0, 0 });
for (int i = 0; i < N; i++)
{
cin >> GoodsTable[i].Weight >> GoodsTable[i].Value;
}
int DP[101][100001];
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= K; j++)
{
int CurWeight = GoodsTable[i - 1].Weight;
int CurValue = GoodsTable[i - 1].Value;
// 검토 과정
if (CurWeight <= j) // 현재의 짐을 담을 수 있음
{
// 1. 현재 짐을 넣지 않는 경우, 바로 윗 칸의 값 // DP[i - 1][j]
// 2. 현재 짐을 넣는다. // DP[i - 1][j - CurWeight] + CurValue
DP[i][j] = max(DP[i - 1][j - CurWeight] + CurValue, DP[i - 1][j]);
}
else // 현재의 짐을 담을 수 없음
{
// 바로 윗 칸의 값 // DP[i - 1][j]
DP[i][j] = DP[i - 1][j];
}
}
}
cout << DP[N][K];
return 0;
}
