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;
}
수식이 여러 개 주어지면 어려울 수 있겠지만, 지문에서는 최대 [ *, +, - ]만 주어졌기 때문에 충분히 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;
}
딱히 어떤 알고리즘이 필요한 문제는 아닌 것 같아 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;
}
결국 이 방식으로 파고 들어가면, k번째에 생성되는 조합은 어떤 경우를 갖는지 알아낼 수 있습니다. { 1, 2, 3 } 수열에서 5번째로 오는 값을 찾는 과정을 아래의 함수로 살펴보겠습니다.
long long factorial(int _Num)
{
long long Result = 1;
for (int i = 1; i <= _Num; ++i)
{
Result = Result * i;
}
return Result;
}
// ...
--k;
for (int i = 0; i < n; ++i)
{
long long Value = factorial(n - 1 - i);
long long Index = k / Value;
k %= Value;
if (Index >= Numbers.size())
{
Index = Numbers.size() - 1;
}
answer.push_back(Numbers[Index]);
Numbers.erase(Numbers.begin() + Index);
}
1. --k : 인덱스는 0부터 계산하기 때문에, 1을 빼서 활용
2. n = 3일 때, 가능한 순열 수는 3! = 6 입니다.
3. i = 0 일 경우
- Value는 (3-1-0)! = 2! = 2
- Index는 4 / 2 = 2
- k %= Value는 0
- 이로써 3이 선택되고, 1. 2가 남습니다.
4. i = 1 일 경우
- Value는 (3-1-1)! = 1! = 1
- Index는 0 / 1 = 0
- k %= Value는 0
- 이로써 1이 선택되고, 2가 남습니다.
4. i = 2 일 경우
- Value는 (3-1-2)! = 0! = 1
- Index는 0 / 1 = 0
- k %= Value는 0
- 이로써 2가 선택되고, 종료됩니다.
결론은 전체 경우의 수 중 5번째의 경우로 3을 선택하고, 그 안에서 다시 첫 번째로 와야하는 경우로 1을 선택하고, 이 과정을 반복하는 것입니다.
#include <string>
#include <vector>
using namespace std;
long long factorial(int _Num)
{
long long Result = 1;
for (int i = 1; i <= _Num; ++i)
{
Result = Result * i;
}
return Result;
}
vector<int> solution(int n, long long k)
{
vector<int> answer;
vector<long long> Numbers;
for (int i = 1; i <= n; ++i)
{
Numbers.push_back(i);
}
--k;
for (int i = 0; i < n; ++i)
{
long long Value = factorial(n - 1 - i);
long long Index = k / Value;
k %= Value;
if (Index >= Numbers.size())
{
Index = Numbers.size() - 1;
}
answer.push_back(Numbers[Index]);
Numbers.erase(Numbers.begin() + Index);
}
return answer;
}
