고정된 크기의 배열에 대해, 배열에 접근할 수 있는 포인터 두 가지(Left, Right)를 활용하여 탐색하는 방법이다. 보통 정렬된 상태의 연속 수열의 부분 합을 구할 때 많이 활용한다.
int TwoPointer(vector<int> _Arr, int _Value)
{
int Result = 0;
int Left = 0, Right = 0;
int Sum = _Arr[0];
int Size = _Arr.size();
vector<int> answer;
while (Left < Size && Right < Size)
{
if (Sum < _Value)
{
++Right;
if (Right < Size)
Sum += _Arr[Right];
}
else if (Sum > _Value)
{
Sum -= _Arr[Left];
++Left;
}
else // Sum == _Value
{
if (/*특정 동작을 위한 if문*/)
{
// TODO
++Result;
}
// Sum == _Value인 경우에도 줄여서 다음 가능성 탐색
// 없으면 그냥 break;
Sum -= _Arr[Left];
++Left;
}
}
return Result;
}
[슬라이딩 윈도우]
두 개의 포인터가 유동적으로 변하는 투 포인터와 달리, 슬라이딩 윈도우는 고정된 크기의 공간에 대한 탐색을 실시한다.
int SlidingWindow(vector<int> _Arr, int _Value, int _WindowSize)
{
int Result = 0;
int Sum = 0;
// 초기 윈도우 계산
for (int i = 0; i < _WindowSize; ++i)
{
Sum += _Arr[i];
}
if (Sum == _Value)
{
++Result;
}
// 오른쪽으로 윈도우 이동
for (int i = _WindowSize; i < _Arr.size(); ++i)
{
Sum -= _Arr[i - _WindowSize]; // 왼쪽 끝 제거
Sum += _Arr[i]; // 오른쪽 새 값 추가
if (Sum == _Value)
{
++Result;
}
}
return Result;
}
투 포인터를 활용하면 쉽게 풀 수 있다. 0번 인덱스부터 시작하여, 현재의 sum이 k보다 작으면 Right를 옮기면서 sum에 합해주고, sum이 k보다 크면 Left를 옮기면서 sum에서 빼준다.
같은 경우를 찾아도 계속 탐색을 진행해야하기 때문에 이때는 두 인덱스간 차를 먼저 검사하여 저장된 인덱스 차보다 현재 Right, Left의 차가 더 작으면 answer를 갱신해준다. 이후 Left를 한 칸 오른쪽으로 옮기면서 sum에서 Left 옮긴 값 만큼 빼주고 계속 탐색을 진행하는 것이다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(vector<int> sequence, int k)
{
int Left = 0, Right = 0;
int sum = sequence[0];
int n = sequence.size();
int minLength = INT_MAX;
vector<int> answer;
while (Left < n && Right < n)
{
if (sum < k)
{
++Right;
if (Right < n)
sum += sequence[Right];
}
else if (sum > k)
{
sum -= sequence[Left];
++Left;
}
else // sum == k
{
if ((Right - Left) < minLength)
{
minLength = Right - Left;
answer = { Left, Right };
}
// sum == k인 경우에도 줄여서 다음 가능성 탐색
sum -= sequence[Left];
++Left;
}
}
return answer;
}
처음에는 규칙성을 찾고 인덱스를 하나씩 선형 탐색하면서 push_back을 하려다가(좀 오래 고민함), 이건 아닌거 같아서 다른 방법을 생각했다. 먼저 2차원 배열을 준비한 다음 아래, 오른쪽, 위-왼쪽(대각선) 방향으로 채워나가는 방식이다.
1. 2차원 테이블 생성
2. 각 인덱스 값에 접근할 요소들 선언
3. 탐색 시작, max값이 되면 종료한다.
3-1. 방문한 테이블 좌표값에 대해 num을 입력하고, 1 증가시켜준다.
3-2. 현재 방향에 대해 먼저 y를 1 증가, x는 그대로 탐색 시도, 이 값이 경계를 벗어났는지 확인함
3-2-1. 경계를 벗어난 경우(사이즈를 벗어나거나 값이 채워진 인덱스인 경우), 방향 전환을 시도
3-2-2. 시도 방식은 dir(방향 인덱스)를 재설정하고, 해당 방향 인덱스를 기준으로 탐색할 좌표값을 덮어써줌
3-3. 경계가 벗어나지 않았으면 좌표를 재설정
4. 3의 방식을 반복하여 값을 채워넣은 뒤, 2차원 배열을 answer에 담고 return
규칙성을 찾지 않고 그냥 채워넣었으면 금방 풀었을 것이다(아쉬운 부분). 아래는 구현 코드이다.
#include <vector>
using namespace std;
int dy[3] = { 1, 0, -1 };
int dx[3] = { 0, 1, -1 };
vector<int> solution(int n)
{
// 삼각형 구조를 표현할 2차원 벡터
vector<vector<int>> triangle(n, vector<int>(n, 0));
// 방향 벡터: 아래, 오른쪽, 왼쪽 위 대각선
int dy[3] = { 1, 0, -1 };
int dx[3] = { 0, 1, -1 };
int y = 0;
int x = 0;
int num = 1;
int dir = 0; // 방향 인덱스
int maxNum = n * (n + 1) / 2;
while (num <= maxNum)
{
triangle[y][x] = num++;
int ny = y + dy[dir];
int nx = x + dx[dir];
// 경계를 벗어나거나 이미 숫자가 채워져 있으면 방향 전환
if (ny >= n || nx >= n || ny < 0 || nx < 0 || triangle[ny][nx] != 0)
{
dir = (dir + 1) % 3;
ny = y + dy[dir];
nx = x + dx[dir];
}
y = ny;
x = nx;
}
// 결과를 1차원 벡터로 변환
vector<int> answer;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
answer.push_back(triangle[i][j]);
}
}
return answer;
}
입력 값이 크기 때문에 단순한 이중 반복문으로는 풀 수 없다. 풀이 방식은 오큰수 개념을 활용했다.여기서의 동작은 뒤의 숫자가 클 때 앞의 숫자를 제거하는 방식으로 구현되어있다.
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
// 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 수
// ex) 1924에서 두 개 제거하면 19, 12, 14, 92, 94, 24가 만들어지는데, 이 중 가장 큰 수는 94
// number : 2자리 이상, 1'000'000 이하
// k : 1 이상 number 자릿수 미만 자연수
string solution(string number, int k)
{
string answer = "";
stack<char> Stk;
// 오큰수 전략(앞큰수로 k개 제거하기)
for (char digit : number)
{
// 뒤의 숫자가 클 때 앞의 숫자를 제거
while (!Stk.empty() && k > 0 && Stk.top() < digit)
{
Stk.pop();
k--;
}
Stk.push(digit);
}
// 아직 k가 남아있다면 뒤에서 제거
while (k-- > 0)
{
Stk.pop();
}
// 스택 → 문자열로 변환
while (!Stk.empty())
{
answer += Stk.top();
Stk.pop();
}
reverse(answer.begin(), answer.end());
return answer;
}
Direct3D 관련 인터페이스는 IUnKnown 클래스를 상속받는 COM(Component Object Model) 객체입니다. 이들은 내부에서 자체적으로 스마트 포인터와 같이 RAII 패턴과 더불어 Refernce Counting, Release를 통해 수명을 관리하기 때문에 스마트 포인터(std::shared_ptr)로 받지 못하게 막아놨습니다.
이 COM 객체들을 원시 포인터에 저장하여 활용할 수 있지만, 이럴 경우에는 프로세스 종료 시점에 명시적으로 Release를 호출해줘야 합니다. 그렇지 않으면 메모리 누수 위험이 존재할 수 있는데, 앞서 D3D11CreateDevice() 함수를 통해 반환되는 값을 [ID3D11Device*Device]에 저장했다고 가정해봅시다. 사용을 다 했으면 Release를 해줘야하지만, 하지 않았을 경우 아래와 같은 출력 창을 확인할 수 있습니다.
오류 내용은 프로그램이 종료되었지만 해제되지 않은 Direct3D 객체가 있다는 경고입니다. 참조 카운트는 0이지만 객체는 여전히 GPU 메모리에 남아있다는 뜻이 됩니다.
물론 이 모든 상황을 컨트롤 할 수 있다면 상관없지만, 여간 번거로운 작업이 아닐 수 없습니다. 이를 위해서 Direct3D의 COM 객체들을 받아볼 수 있고, 스마트 포인터처럼 사용이 끝나면 자동으로 메모리를 해제해주는 포인터가 있는데, 그것이 바로 Microsoft::WRL::ComPtr<T>입니다.
[주요 동작 방식]
스마트 포인터와 동작 방식이 동일합니다.
1. 선언
: 아래와 같이 선언해서 사용하면 됩니다.
Microsoft::WRL::ComPtr<ID3D11Device> Device;
2. 참조 카운트 관리
: 스마트 포인터와 같이 생성 시 AddRef(), 소멸 시 Release() 함수를 호출하여 자동으로 객체 생명 주기를 관리해줍니다.
3. 스마트 포인터처럼 사용 가능
: operator->, Get(), Reset() 등의 함수를 제공해주기 때문에 스마트 포인터처럼 사용이 가능합니다.
4. 안전한 대입과 복사
: Comptr 간 복사 시 내부적으로 참조를 관리하기 때문에 생성된 값을 저장하는 용도로(D3D11CreateDevice() 반환값) 사용해도 안전하게 이용할 수 있습니다. 또한 대입 연산자로 다른 Comptr 변수에 값을 대입해도 Reference Counting 관리로 인해 메모리 누수 문제에 자유로워질 수 있습니다.
5. QueryInterface
: As(&out) 함수로 인터페이스를 제공해주는데, 해당 프로젝트에서는 크게 쓸 일은 없을 것으로 생각됩니다.
[프로젝트에 사용하기 위한 설정]
모든 COM 객체에 대해 선언마다 Microsoft::WRL::ComPtr<>를 선언하기도, using namespace를 선언하기도 여간 번거로운 작업이 아닐 수 없습니다. 때문에 래핑 구조체를 하나 선언했습니다.
answer size는 2로 초기화한다. [0]은 0의 갯수, [1]은 1의 갯수를 담을 것이다.isCompressible() 함수로는 해당 영역이 모두 같은지 확인하는 함수로, arr과 시작위치 y, x, 검사할 정사각형 한 변의 길이 size를 전달한다. 예를들어
arr = {1, 1}. {1, 1};
이 입력이라면, isCompressible(arr, 0, 0, 2)를 전달하고 true를 반환받는다.
QuadTree() 함수는 재귀 형식이다. 해당 구역이 압축 가능한 경우는 그 숫자 하나만 카운트하고 리턴하고, 압축이 불가능한 경우는 네 개로 나눠서 다시 QuadTree 재귀 호출을 실시한다.
#include <vector>
using namespace std;
vector<int> answer(2); // 0의 개수, 1의 개수
bool isCompressible(const vector<vector<int>>& arr, int y, int x, int size)
{
int first = arr[y][x];
for (int i = y; i < y + size; ++i)
{
for (int j = x; j < x + size; ++j)
{
if (arr[i][j] != first)
return false;
}
}
return true;
}
void QuadTree(const vector<vector<int>>& arr, int y, int x, int size)
{
if (isCompressible(arr, y, x, size))
{
answer[arr[y][x]]++;
return;
}
int half = size / 2;
QuadTree(arr, y, x, half); // 왼쪽 위
QuadTree(arr, y, x + half, half); // 오른쪽 위
QuadTree(arr, y + half, x, half); // 왼쪽 아래
QuadTree(arr, y + half, x + half, half); // 오른쪽 아래
}
vector<int> solution(vector<vector<int>> arr)
{
QuadTree(arr, 0, 0, arr.size());
return answer;
}
2. 다리에 트럭을 올리는 작업을 실시한다. 세 조건을 만족해야만 다리에 트럭을 올릴 수 있다.
2-1. 현재 다리에 존재하는 트럭 무게의 합이 견딜 수 있는 무게보다 작은 경우
2-2. 다리 길이보다 현재 트럭 갯수가 적을 경우
2-3. 아직 올라가지 못한 트럭이 있을 경우
3. 모든 트럭이 다리에 올라갈 경우, 시뮬레이션 종료 준비를 하기 위해 bool값을 활용했다.
4. 모든 트럭이 다리를 지난 경우, 반복문을 탈출하면서 시뮬레이션 1회당 1씩 증가시켜줬던 answer를 리턴한다.
#include <string>
#include <vector>
#include <queue>
using namespace std;
struct Bridge
{
int Weight = 0;
int Time = 0;
};
// 모든 트럭이 다리를 건너려면 몇 초기 필요한지 알아내기
// bridge_length : 트럭이 올라갈 수 있는 최대 갯수
// weight : 견딜 수 있는 무게, 이하로 트럭이 있어야함
int solution(int bridge_length, int weight, vector<int> truck_weights)
{
int answer = 0;
int Time = 0;
int CurWeight = 0;
vector<Bridge> Bridges;
queue<int> Trucks;
for (int Value : truck_weights)
{
Trucks.push(Value);
}
bool IsAll = false;
bool IsBreak = false;
while (true)
{
++answer;
for (int i = 0; i < Bridges.size(); i++)
{
Bridges[i].Time += 1;
// 시간 다됐으면 꺼내기
if (Bridges[i].Time > bridge_length)
{
CurWeight -= Bridges[i].Weight;
Bridges.erase(Bridges.begin());
i--;
if (IsAll && 0 == Bridges.size())
{
IsBreak = true;
break;
}
}
}
if (IsBreak) break;
if (!Trucks.empty() && CurWeight + Trucks.front() <= weight && Bridges.size() < bridge_length) // 현재 다리에 존재하는 트럭 무게 합이 견딜 수 있는 무게보다 적을 때, 다리 길이보다 현재 트럭 갯수 적을 때, 올리기 가능
{
int Weight = Trucks.front();
Trucks.pop();
CurWeight += Weight;
Bridges.push_back({ Weight, 1 });
}
if (Trucks.empty())
{
IsAll = true;
}
}
return answer;
}
먼저 두 입력값에 대해 각 Sum을 구하고 원소를 queue에 push 했다. 이후 루프문을 도는데, 조건은 각 queue의 size 합만큼 돌고, 이 횟수 내로 판단이 안될 시 실패로 간주하는 방식을 택했다. 두 큐의 자료들을 pop하고 push하는 과정을 모두 수행해도 결과를 만들어낼 수 없다면 실패한 것이기 때문이다. 그래도 그냥 제한이 넉넉해서 size 합의 * 2를 돌 수 있도록 했다.
이제 각 큐의 합에 대해 크고 작음을 판단하면서, 큐를 팝하고 푸쉬하는 과정과 그에 대한 합의 변동을 기록한다. 도중에 바로 합이 같아지면 break를 실시하고 값을 리턴한다. 합이 같지 않아도 반복문은 종료되기 때문에, 반복문으로 축적된 answer 값을 그대로 리턴할 염려가 있어, bool값을 통해 예외 처리를 추가로 실시했다.
#include <string>
#include <vector>
#include <queue>
using namespace std;
// 하나의 큐에서 다른 큐로 넣으면서 두 큐의 합이 같도록 만듬
// pop -> insert를 1회 작업 수행으로 간주
// queue1,2[i] = 1 이상, 1'000'000'000
int solution(vector<int> queue1, vector<int> queue2)
{
int answer = -1;
long Sum1 = 0;
long Sum2 = 0;
queue<long> Que1;
queue<long> Que2;
for (int Value : queue1)
{
Sum1 += Value;
Que1.push(Value);
}
for (int Value : queue2)
{
Sum2 += Value;
Que2.push(Value);
}
if (Sum1 == Sum2)
{
return answer = 0;
}
int Que1Size = queue1.size();
int Que2Size = queue2.size();
int Try = (Que1Size * 2) + (Que2Size * 2);
bool IsTry = false;
while (Try--)
{
++answer;
if (Sum1 < Sum2)
{
long Value2 = Que2.front();
Que2.pop();
Sum1 += Value2;
Sum2 -= Value2;
Que1.push(Value2);
}
else if (Sum1 > Sum2)
{
long Value1 = Que1.front();
Que1.pop();
Sum1 -= Value1;
Sum2 += Value1;
Que2.push(Value1);
}
else
{
IsTry = true;
break;
}
}
if (false == IsTry)
{
answer = -1;
}
return answer;
}
국제 표준화 기구인 ISO(International Standardization Organization)에서 개발한 컴퓨터 네트워크 프로토콜 디자인과 통신을 계층으로 나누어 설명한 개방형 시스템 상호 연결 모델이다. 각 계층은 서로 독립적으로 구성되어 있고, 하위 계층의 기능을 이용하여 상위 계층에 기능을 제공한다. 1계층인 물리 계층부터 7계층인 애플리케이션 계층으로 정의되어있다.
계층을 지날 때마다 (Header)가 붙는데, 이것은 해당 계층의 기능과 관련된 제어 정보가 포함되어있다. 제어 정보들은 모두 운영체제가 제공하는 프로토콜에 의해 송신 측에서는 계층을 지날 때마다 덧붙여서 추가되고, 수신 측에서는 계층을 지날 때마다 제거된다.
1. 물리 계층(Physical Layer)
: 0과 1의 비트 정보를 회선에 보내기 위해 전기적 신호로 변환하는 작업을 수행한다.
: 통신 케이블, 리피터, 허브 활용
2. 데이터 링크 계층(Data Link Layer)
: 물리 계층을 통해 송수신되는 정보의 오류와 흐름을 관리하고, 프레임에 물리적 주소(MAC Address)를 부여하여 에러 검출, 재전송, 흐름제어를 실시한다.
