난너무슬프다

[CPU 간략 요약]

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차원 공간에 표시하기 위해 레온하르트 오일러가 고안한 세 개의 각도 표기법입니다.

- 알파 : z축(파란색)을 회전축으로 하는 xy 좌표축의 각도

- 베타 : 알파 회전 후, x축(녹색)을 회전축으로 하는 zy 좌표축의 각도

- 감마 : 베타 회전 후, z축(빨간색)을 회전축으로 하는 xy 좌표축의 각도

[짐벌락]

오일러 각도 구조를 활용하여 아래와 같이 짐벌(gimbal)이라는 구조를 만들 수 있습니다.

짐벌은 각 축을 Roll, Pitch, Yaw로 표현합니다.

- Roll : 좌우 회전

- Pitch : 앞뒤 회전

- Yaw : 상하 회전

각 고리는 자신이 가진 축을 기준으로 회전하지만, 서로 연결되어 있기 때문에 전체적으로는 모든 방향으로 회전이 가능합니다. 하지만 짐벌 구조에서는 커다란 결함이 있는데, 바로 짐벌락(Gimbal Lcok)입니다.

짐벌의 고리가 모두 겹치는 경우에는 첫 번째 회전과 세 번째 회전의 축이 거의 일치하는 상태가 되기 때문에, 회전 자유도가 3개에서 2개로 줄어드는 것입니다.

[사원수(Quaternions)]

해당 문제를 해결하기 위하여, 사원수(Quaternions)를 활용하는 방법이 있습니다. 4원수는 4차원 복소수 체계로, 다음의 형태를 가집니다.

q = a + bi + cj + dk (a, b, c, d는 실수, i, j, k는 복소수)

사원수의 보다 자세한 내용은 다음에 따로 다뤄보도록 하겠습니다.

[Port Number]

포트 넘버(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)

사용자가 자유롭게, 임의로 지정할 수 있는 포트 넘버들입니다. 언제든지 활용 가능한 영역이기 때문에 특별히 정해진 것은 없습니다.

[출처]

https://mysterlee.tistory.com/104

[IPC]

멀티 프로세싱은 하나의 프로그램을 여러 개의 프로세스로 나누어 각각의 프로세스가 하나의 작업을 병렬적으로 처리하도록 하는 방법입니다. 하지만 멀티 스레딩과 다르게 멀티 프로세싱의 경우, 각 프로세스는 고유한 메모리 영역을 가지고 있기 때문에 일반적으로는 서로간 데이터 공유, 전달이 않고 문제가 생기더라도 다른 프로세스에 영향을 미치지 않습니다.

여기서 서로간 데이터를 주고받기(통신하기) 위한 기능을 활용할 수 있는데, 이를 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]

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를 계속해서 사용중에 있습니다.

[유클리드 거리]

유클리드 거리, 혹은 유클리디안 거리(Euclidean Distance)는 두 점 사이의 거리를 계산할 때 흔히 쓰이는 방법이며, 이를 통해 유클리드 공간을 정의할 수 있습니다.

데카르트 좌표계로 나타낸 점 P(x1, y1), 점 Q(x2, y2)가 있을 때, 두 점의 사이 거리 d는 다음과 같습니다.

그렇습니다, 피타고라스 정리를 활용하면 유클리드 거리를 구할 수 있게 됩니다.

차원이 증가해도, 값만 추가해주면 바로 사용이 가능합니다.

C++에서는 다음과 같이 활용할 수 있습니다.

#include <iostream>

double Distance2D(double _X1, double _Y1, double _X2, double _Y2)
{
    const double dx = _X2 - _X1;
    const double dy = _Y2 - _Y1;
    return dx * dx + dy * dy;
}

double Distance3D(double _X1, double _Y1, double _Z1,
                         double _X2, double _Y2, double _Z2)
{
    const double dx = _X2 - _X1;
    const double dy = _Y2 - _Y1;
    const double dz = _Z2 - _Z1;
    return dx * dx + dy * dy + dz * dz;
}

int main()
{
    double d2 = Distance2D(0.0, 0.0, 3.0, 4.0);        // 5.0
    double d3 = Distance3D(0.0, 0.0, 0.0, 1.0, 2.0, 2.0); // 3.0
}

[맨허튼 거리]

맨허튼 거리(Manhattan Distance), 혹은 택시 거리, 시가지 거리라 불리우는 거리 공간은 다음의 이미지를 통해 살펴보도록 하겠습니다.

초록색 선은 두 점 사이의 유클리드 거리값을 나타냅니다. 하지만 단위 이름과 같이, 맨허튼이라는 "도시"를 대상으로 격자 내 두 점 사이의 거리값을 구하는 공식이기 때문에 실제로는 초록색 선이 길이값이 될 수 없습니다(하얀색 부분은 건물이 존재하기 때문). 따라서 다른색 선과 같이 길이를 구해야합니다.

그렇다면 빨간색, 파란색, 노란색 선 중 어떤 선이 가장 최소 단위의 거리값이 될 수 있을까요? 파란색 선이 초록색 선과 가장 가깝기 때문에 파란색이라고 할 수도 있지만, 실제로는 빨간색, 파란색, 노란색 선 모두 같은 길이값을 가지게 됩니다. 이것이 바로 맨허튼 거리입니다.

위 그림에서 왼쪽 아래 점P(x1, y1),  오른쪽 위 점Q(x2, y2)가 존재할 때, 맨허튼 거리 d를 구하는 공식은 다음과 같습니다.

단순하게 x값과  y값의 차이를 절대값으로 바꿔서 더하는 방식을 취합니다. 3차원 좌표계의 맨허튼 거리는 다음과 같습니다.

C++에서는 다음과 같이 활용할 수 있습니다.

#include <iostream>
#include <cmath>   // std::abs

double ManhattanDistance2D(double _X1, double _Y1, double _X2, double _Y2)
{
    return std::abs(_X2 - _X1) + std::abs(_Y2 - _Y1);
}

double ManhattanDistance3D(double _X1, double _Y1, double _Z1,
                           double _X2, double _Y2, double _Z2)
{
    return std::abs(_X2 - _X1) + std::abs(_Y2 - _Y1) + std::abs(_Z2 - _Z1);
}

int main()
{
    std::cout << ManhattanDistance2D(1.0, 2.0, 4.0, 6.0) << std::endl; // 7.0
    std::cout << ManhattanDistance3D(1.0, 2.0, 3.0, 4.0, 6.0, 9.0) << std::endl; // 13.0
}

[위키피디아]

https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

[배낭 문제란]

배낭 문제는 Dynamic Programming에 있어 가장 대표적인 문제 중 하나입니다. 문제의 핵심은 최대 무게가 정해져 있는 배낭에 대해 여러 종류의 무게와 가치를 지닌 물건들을 배낭에 넣을 경우, 가장 가치 합이 높은 경우의 수(조합)를 찾아내는 것입니다.

[예제를 통해 문제 접근해보기]

백준의 [12865번 - 평범한 배낭] 문제를 통해 배낭 문제 알고리즘 풀이를 알아보도록 하겠습니다.

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

예제의 입력은 다음과 같이 주어집니다.

주어진 네 종류의 물건에 대해, 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;
}

빌드 과정은 크게 전처리기, 컴파일, 어셈블러, 링커 순으로 실행됩니다.

[전처리기]

유저가 작성한 코드를 저수준 언어로 변환하기 위한 준비를 실시합니다. 주석, 공백 등 불필요한 요소를 제거하고 매크로 구문을 치환하며, 헤더 파일의 코드 전체를 소스파일 내에 추가하게 됩니다.

[컴파일]

전처리 과정을 거친 코드를 저수준의 어셈블리어로 번역하는 동시에 문법상의 오류를 검출하기도 합니다.

[어셈블러]

어셈블러 과정에서는 어셈블리어를 0과 1로 이루어진 바이너리 코드로 변환합니다. 변환된 바이너리 코드는 여러 개의 오브젝트 파일(.obj)로 저장됩니다.

[링커]

위에서 여러 개로 저장된 오브젝트 파일을 해당 단계에서 하나의 프로그램에서 작동하도록 연결해줍니다. 이 과정에서 정적 라이브러리가 프로그램과 함께 묶이게 됩니다. 하나로 묶인 프로그램은 exe 파일로 저장되며 빌드가 완료됩니다.

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/67257

[풀이]

수식이 여러 개 주어지면 어려울 수 있겠지만, 지문에서는 최대 [ *, +, - ]만 주어졌기 때문에 충분히 next_permutation을 활용할 수 있을 것이라 판단했습니다. 이를 위해 처음 받는 expression을 파싱해줍니다.

1. Numbers : 파싱된 숫자들

2. Formulas : 파싱된 연산자들

3. FormulaSet : 연산자가 어떤 것들이 있는지

3번을 따로 사용한 이유는 중복을 제거하여 expression 내에 무슨 종류의 연산자가 존재하는지 판단하기 위함입니다. 이제 이 3종류의 컨테이너에 파싱된 값들을 넣어주고, next_permutation을 실행합니다.

순회 도중 중간에 요소를 삭제하기 위하여 for문보다는 while문을 활용했으며, 순회를 실시하여 현재 지정된 Operator와 Fomula가 동일하다면, Formula에 해당하는 index와 index+1의 값을 서로 연산해주고 erase를 실시하여 컨테이너를 갱신하는 작업을 실시했습니다. 이렇게 계속 수를 줄여나가다보면 최종적으로 현재 순열에 의해 조합된 연산자 순서대로 값을 알아낼 수 있게 됩니다.

#include <string>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <iostream>

using namespace std;

long long solution(string expression)
{
    long long answer = 0;

    vector<long long> Numbers;
    vector<char> Formulas;
    unordered_set<char> FormulaSet;

    string CurNumber;
    for (size_t i = 0; i < expression.size(); ++i)
    {
        char c = expression[i];
        if ('0' <= c && c <= '9')
        {
            CurNumber += c;
        }
        else
        {
            Numbers.push_back(stoll(CurNumber));
            CurNumber.clear();

            Formulas.push_back(c);
            FormulaSet.insert(c);
        }
    }
    // 마지막 숫자
    if (!CurNumber.empty())
    {
        Numbers.push_back(stoll(CurNumber));
    }

    vector<char> Arr;
    Arr.reserve(FormulaSet.size());
    for (char Operator : FormulaSet)
    {
        Arr.push_back(Operator);
    }
    sort(Arr.begin(), Arr.end());

    // 3) 모든 우선순위 순열 시도
    do
    {
        vector<long long> NTemp = Numbers;
        vector<char> FTemp = Formulas;

        for (char Operator : Arr)
        {
            size_t j = 0;
            while (j < FTemp.size())
            {
                if (FTemp[j] == Operator)
                {
                    long long L = NTemp[j];
                    long long R = NTemp[j + 1];
                    long long Result = 0;

                    if (Operator == '*')      Result = L * R;
                    else if (Operator == '+') Result = L + R;
                    else                Result = L - R;

                    NTemp[j] = Result;
                    NTemp.erase(NTemp.begin() + (j + 1));
                    FTemp.erase(FTemp.begin() + j);
                }
                else
                {
                    ++j;
                }
            }
        }

        long long value = llabs(NTemp[0]);
        if (value > answer) answer = value;

    } while (next_permutation(Arr.begin(), Arr.end()));

    return answer;
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/77485

[풀이]

딱히 어떤 알고리즘이 필요한 문제는 아닌 것 같아 algorithm의 rotate() 함수를 활용하여 풀었습니다. 구역을 총 네 개로 나눈 뒤, 각 구역의 값을 vector로 받아와 rotate()를 실시합니다. 저의 풀이에서는 1, 2 단계의 rotate()의 경우 오른쪽으로 회전, 3, 4 단계의 rotate()의 경우 왼쪽으로 회전시키고 값을 저장(CashMap)해둔 뒤, 최종적으로 원본 데이터에 적용(Map)하는 방식으로 진행했습니다. 추가로 각 요소를 Temp vector에 담을 때마다 min()을 활용하여 보다 낮은 값을 각 단계마다 실시하여 저장해두고 마지막에 answer에 담아주면 됩니다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// 주어진 쿼리로 회전시키고(y, x, y, x), 회전시킨 수중에 가장 낮은 수를 answer에 입력해둔 뒤 리턴
vector<int> solution(int rows, int columns, vector<vector<int>> queries)
{
    vector<int> answer;
    vector<vector<int>> Map(rows);
    int Count = 1;
    for (int y = 0; y < rows; y++)
    {
        for (int x = 0; x < columns; x++)
        {
            Map[y].push_back(Count++);
        }
    }
    vector<vector<int>> CashMap = Map;

    int Size = queries.size();
    int QueryIndex = 0;

    while (Size--)
    {
        int Y1 = queries[QueryIndex][0] - 1;
        int X1 = queries[QueryIndex][1] - 1;
        int Y2 = queries[QueryIndex][2] - 1;
        int X2 = queries[QueryIndex][3] - 1;
        ++QueryIndex;
        int Min = INT32_MAX;

        // [1]
        vector<int> Temp1;
        int Index = 1;
        {
            // Map[Y1][X1]; ~ Map[Y1][X2];
            // 맨 처음 버림
            for (int i = X1; i <= X2; ++i)
            {
                Min = min(Min, Map[Y1][i]);
                Temp1.push_back(Map[Y1][i]);
            }

            rotate(Temp1.begin(), Temp1.end() - 1, Temp1.end());

            for (int i = X1 + 1; i <= X2; ++i)
            {
                CashMap[Y1][i] = Temp1[Index++];
            }
        }

        // [2]
        vector<int> Temp2;
        Index = 1;
        {
            // Map[Y1][X2]; ~ Map[Y2][X2];
            // 맨 처음 버림
            for (int i = Y1; i <= Y2; ++i)
            {
                Min = min(Min, Map[i][X2]);
                Temp2.push_back(Map[i][X2]);
            }

            rotate(Temp2.begin(), Temp2.end() - 1, Temp2.end());

            for (int i = Y1 + 1; i <= Y2; ++i)
            {
                CashMap[i][X2] = Temp2[Index++];
            }
        }

        // [3]
        vector<int> Temp3;
        Index = 0;
        {
            // Map[Y2][X2]; ~ Map[Y2][X1];
            // 맨 마지막 버림
            for (int i = X1; i <= X2; ++i)
            {
                Min = min(Min, Map[Y2][i]);
                Temp3.push_back(Map[Y2][i]);
            }

            rotate(Temp3.begin(), Temp3.begin() + 1, Temp3.end());

            for (int i = X1; i <= X2 - 1; ++i)
            {
                CashMap[Y2][i] = Temp3[Index++];
            }
        }

        // [4]
        vector<int> Temp4;
        Index = 0;
        {
            // Map[Y2][X1]; ~ Map[Y1][X1];
            // 맨 마지막 버림
            for (int i = Y1; i <= Y2; ++i)
            {
                Min = min(Min, Map[i][X1]);
                Temp4.push_back(Map[i][X1]);
            }

            rotate(Temp4.begin(), Temp4.begin() + 1, Temp4.end());

            for (int i = Y1; i <= Y2 - 1; ++i)
            {
                CashMap[i][X1] = Temp4[Index++];
            }
        }

        answer.push_back(Min);
        Map = CashMap;

        //for (size_t i = 0; i < Map.size(); i++)
        //{
        //    for (size_t j = 0; j < Map[i].size(); j++)
        //    {
        //        cout << Map[i][j] << ' ';
        //    }
        //    cout << endl;
        //}
    }

    return answer;
}