231101_promise_future
lock_guard
lock() unlock()을 스코프 베이스로 관리한다.
atomic
lock add DWORD PTR [rdi], l
std::promise / std::future
future에 스레드 T가 원하는 데이터를 돌려주겠다는 promise
231104_Client Side Prediction
Client Side Prediction
클라에서 보여주는 것만 처리 한다
검증은 서버에서 한다
데미지 -100띄워도 실제 깎이는 것은 -10
231106_빅 리틀 엔디언
Winsock 라이브러리
윈도우에서 소켓 쓸 때 쓰는 API
브로드캐스팅
전부 다 전달하기
라우팅
패킷 길찾기
TCP UDP 차이
SOCK_STREAM : 받는 쪽에서 남은 버퍼만큼 주는 쪽에서 보내준다. 신뢰성 보장을 위해 전송을 확인한다.
SOCK_DGRAM : 패킷 잃어버려도 괜찮다.
TCP
순서를 보장한다
데이터를 패킷으로 잘라준다
파일 읽기 쓰기랑 비슷하다
UDP
연결 안해서 연결 처리를 위한 코드 없다
직접 데이터를 패킷으로 자른다
빅 리틀 엔디언
리틀 엔디언 쓰는 이유 : 캐스팅 할 때 숫자 자르기 편하다
#include <iostream>
#include <winsock2.h>
#pragma comment(lib, "ws2_32.lib")
using namespace std;
int main()
{
unsigned short hostPort = 0x6789;
unsigned short networkPort = htons(hostPort);
cout << "호스트 순서 Port : " << hex << hostPort << endl;
cout << "네트워크 순서 Port : " << hex << networkPort << endl;
cout << endl;
unsigned long hostIpAddress = 0x12345678;
unsigned long networkIpAddress = htonl(hostIpAddress);
cout << "호스트 순서 IP : " << hex << hostIpAddress << endl;
cout << "네트워크 순서 IP : " << hex << networkIpAddress << endl;
cout << "\n*Host Byte Ordering 확인*" << endl;
unsigned char* p = (unsigned char*)&hostIpAddress;
for (int i = 0; i < sizeof(hostIpAddress); i++)
printf("0x%x = 0x%02x\n", (p + i), *(p + i));
cout << "\n*Network Byte Ordering 확인*" << endl;
byte numbers[4];
memcpy(numbers, &networkIpAddress, 4);
for (int i = 0; i < 4; i++)
printf("0x%x = 0x%02x\n", (numbers + i), *(numbers + i));
return 0;
}NAT
라우터에서 구현된다
사설 IP주소를 공용 IP 주소로 변환한다
231107_플로이드 워셜
/* 경로 찾기
// a - b && b - c이면 a - c 있다고 업데이트 하기 (X)
// middle을 거쳐 from to로 가는 길 있는지 체크 (O)
중간 경로를 기준으로 돌아야 경로 업데이트 체크가 제대로 된다.
*//*
1107번 리모컨
이 문제 당연히 bfs로 카운트 세보면서 가능한 뎁스 늘리면서 큐 넣고 빼고 하는 줄 알았다. 그런데 숫자 전부 돌려가며 버튼으로 가능한지 체크하면서 minRes 업데이트 해주는 것이다. 흠… 이 방법도 나쁜 방법은 아닌 것 같다. 그냥 차이점이 브루트 포스 안 쓰고 가능한 숫자를 큐에 넣으면서 체크하는 것이다. 그런데 돌려보니 큐가 터졌다… 하….
0 ~ 9 모든 가능성 큐에다가 넣고 하나씩 빼보면서 체크한다 min 값 업데이트 하기
현재 depth + (+ - 절댓값) 계산한다
depth가 7 이상이면 min 값을 리턴한다
이 방법으로 하니까 큐에 너무 많은 숫자가 들어가서 터졌다
*/231108_플로이드 워셜
// 케빈 베이컨의 6단계 법칙
/*
전부 INF두고 minRes 업데이트 한다
플로이드 워셜로 전체 최단거리 구해놓는다
결과에서 가장 작은 사람 인덱스 리턴하기
INT_MAX에서 +1 하면 오버플로우여서 - 1
*/231109바이너리문자열
// 23. 바이너리 데이터를 문자열로 변환하기
#include <string>
#include <sstream>
#include <iomanip>
#include <vector>
#include <array>
#include <assert.h>
#include <iostream>
// Iter로 돌면서 16진수 문자열로 변환
template <typename Iter>
std::string bytes_to_hexstr(Iter begin, Iter end, bool const uppercase = false)
{
std::ostringstream oss;
if (uppercase)
{
// 대문자로 출력
oss.setf(std::ios_base::uppercase);
}
for (; begin != end; ++begin)
{
// 출력 hex로 설정, 2자리로 출력, 빈자리는 0으로 채움, begin 데이터 int로 변환
oss << std::hex << std::setw(2) << std::setfill('0') << static_cast<int>(*begin);
}
// oss에 있는 문자열을 반환
return oss.str();
}
// 컨테이너 C로 넣어서 실제 컨테이너의 begin(), end()를 호출
template <typename C>
std::string bytes_to_hexstr(C const& c, bool const uppercase = false)
{
return bytes_to_hexstr(std::cbegin(c), std::cend(c), uppercase);
}
int main()
{
// 테스트용 데이터
std::vector<unsigned char> v{ 0xBA, 0xAD, 0xF0, 0x0D };
std::array<unsigned char, 6> a{ { 1,2,3,4,5,6 } };
unsigned char buf[5] = { 0x11, 0x22, 0x33, 0x44, 0x55 };
// 대문자 결과 확인
assert(bytes_to_hexstr(v, true) == "BAADF00D");
assert(bytes_to_hexstr(a, true) == "010203040506");
assert(bytes_to_hexstr(buf, true) == "1122334455");
std::cout << bytes_to_hexstr(v, true) << std::endl;
std::cout << bytes_to_hexstr(a, true) << std::endl;
std::cout << bytes_to_hexstr(buf, true) << std::endl;
assert(bytes_to_hexstr(v) == "baadf00d");
assert(bytes_to_hexstr(a) == "010203040506");
assert(bytes_to_hexstr(buf) == "1122334455");
std::cout << bytes_to_hexstr(v) << std::endl;
std::cout << bytes_to_hexstr(a) << std::endl;
std::cout << bytes_to_hexstr(buf) << std::endl;
}// 24. 문자열을 바이너리 데이터로 변환하기
#include <string>
#include <sstream>
#include <iomanip>
#include <vector>
#include <array>
#include <assert.h>
#include <iostream>
#include <string_view>
unsigned char hexchar_to_int(char const ch)
{
// char를 unsigned char 숫자 데이터로 변환
if (ch >= '0' && ch <= '9')
{
return ch - '0';
}
if (ch >= 'A' && ch <= 'F')
{
return ch - 'A' + 10;
}
if (ch >= 'a' && ch <= 'f')
{
return ch - 'a' + 10;
}
// 0~F 사이의 문자가 아닌 경우 예외
throw std::invalid_argument("Invalid hexadecimal character");
}
// const string& -> string_view: substring 처리할 때 시간 빠르다
std::vector<unsigned char> hexstr_to_bytes(std::string_view str)
{
std::vector<unsigned char> result;
// 문자2개 -> (XXXX 0000 | XXXX) 로 변환
for (size_t i = 0; i < str.size(); i += 2)
{
result.push_back(
(hexchar_to_int(str[i]) << 4) | hexchar_to_int(str[i + 1]));
}
return result;
}
int main()
{
std::vector<unsigned char> expected{ 0xBA, 0xAD, 0xF0, 0x0D, 0x42 };
assert(hexstr_to_bytes("BAADF00D42") == expected);
assert(hexstr_to_bytes("BaaDf00d42") == expected);
}// 2. 최대공약수 프로그램 구현하기
#include <iostream>
// 나머지 0 -> 배수 관계, 나눈 수 % 나머지 -> 자를 수 있는 공통 크기의 조각 찾기
unsigned int gcd_recursive(unsigned int const a, unsigned int const b)
{
return b == 0 ? a : gcd_recursive(b, a % b);
}
unsigned int gcd_iterative(unsigned int a, unsigned int b)
{
while (b != 0)
{
unsigned int r = a % b;
a = b;
b = r;
}
return a;
}
int main()
{
unsigned int a, b;
std::cin >> a >> b;
std::cout << "gcd recursive: " << gcd_recursive(a, b) << std::endl;
std::cout << "gcd iterative: " << gcd_iterative(a, b) << std::endl;
}231110_문자열 token 처리
string_view
문자열에 대한 포인터 + 길이만 가져서 가볍다
const char*처럼 포인터 받기 + const std::string& string 기능 하기
// 25. 문자열을 제목 형식으로 바꾸기
#include <string>
#include <cassert>
#include <sstream>
#include <cctype>
// std::string == std::basic_string<char>, std::wstring == std::basic_string<wchar_t>
template <class Elem>
using tstring = std::basic_string<Elem, std::char_traits<Elem>, std::allocator<Elem>>;
template <class Elem>
using tstringstream = std::basic_stringstream<Elem, std::char_traits<Elem>, std::allocator<Elem>>;
template <class Elem>
tstring<Elem> capitalize(tstring<Elem> const& text)
{
tstringstream<Elem> result;
bool newWord = true;
for (auto const ch : text)
{
// 첫번째 -> 대문자 / 특수문자 || 스페이스면 다음 글자 대문자
newWord = newWord || std::ispunct(ch) || std::isspace(ch);
if (std::isalpha(ch) && newWord)
{
result << static_cast<Elem>(std::toupper(ch));
newWord = false;
}
else if (std::isalpha(ch) && newWord == false)
{
result << static_cast<Elem>(std::tolower(ch));
}
else if(std::isalpha(ch) == false)
{
result << ch;
}
}
return result.str();
}
int main()
{
using namespace std::string_literals;
std::string text = "cOnvert To UPPERS only first letter";
std::string expected = "Convert To Uppers Only First Letter";
assert(capitalize(text) == expected);
assert(
L"The C++ Challenger"s ==
capitalize(L"the c++ challenger"s));
assert(
L"This Is An Example, Should Work!"s ==
capitalize(L"THIS IS an ExamplE, should wORk!"s));
}// 26. 구획 문자로 나누어진 문자열 합치기
#include <string>
#include <cassert>
#include <sstream>
#include <cctype>
#include <vector>
#include <array>
template <typename Iter>
std::string join_strings(Iter begin, Iter end, char const* const separator)
{
// output string stream
std::ostringstream os;
// copy: Iter begin, end -> os Iter로 copy
// ostream_iterator: os에 대한 Iter를 만들어줌 separator로 분리
// 마지막 문자열을 제외하고 모두 separator를 붙여줌
std::copy(begin, end - 1, std::ostream_iterator<std::string>(os, separator));
// 마지막 문자열은 separator를 붙이지 않음
os << *(end - 1);
return os.str();
}
// 컨테이너 넘겨서 해당하는 컨테이너의 begin end로 넘겨줌
template <typename C>
std::string join_strings(C const& c, char const* const separator)
{
if (c.size() == 0)
{
return std::string{};
}
return join_strings(std::begin(c), std::end(c), separator);
}
int main()
{
using namespace std::string_literals;
std::vector<std::string> v1{ "this","is","an","example" };
std::vector<std::string> v2{ "example" };
std::vector<std::string> v3{ };
assert(
join_strings(v1, " ") == "this is an example"s);
assert(
join_strings(v2, " ") == "example"s);
assert(
join_strings(v3, " ") == ""s);
std::array<std::string, 4> a1{ {"this","is","an","example"} };
std::array<std::string, 1> a2{ {"example"} };
std::array<std::string, 0> a3{};
assert(
join_strings(a1, " ") == "this is an example"s);
assert(
join_strings(a2, " ") == "example"s);
assert(
join_strings(a3, " ") == ""s);
}// 27. 구획 문자 리스트를 바탕으로 문자열을 토큰으로 분리하기
#include <string>
#include <cassert>
#include <sstream>
#include <cctype>
#include <vector>
template <class Elem>
using tstring = std::basic_string<Elem, std::char_traits<Elem>, std::allocator<Elem>>;
// stringstream: string 객체를 stream처럼 사용할 수 있게 해준다
// stream: 데이터를 입출력하는데 사용되는 객체 InputStream, OutputStream
template <class Elem>
using tstringstream = std::basic_stringstream<Elem, std::char_traits<Elem>, std::allocator<Elem>>;
// delimiter 하나
template<typename Elem>
inline std::vector<tstring<Elem>> split(tstring<Elem> text, Elem const delimiter)
{
auto sstr = tstringstream<Elem>{ text };
auto tokens = std::vector<tstring<Elem>>{};
auto token = tstring<Elem>{};
// getline: stringstream에 있는 내용을 delimiter를 기준으로 token으로 나눈다
while (std::getline(sstr, token, delimiter))
{
if (!token.empty())
{
tokens.push_back(token);
}
}
return tokens;
}
// delimiter 여러개
template<typename Elem>
inline std::vector<tstring<Elem>> split(tstring<Elem> text, tstring<Elem> const& delimiters)
{
auto tokens = std::vector<tstring<Elem>>{};
size_t pos, prev_pos = 0;
// find_first_of: delimiters에 있는 문자가 text에서 처음으로 나오는 위치를 반환
// prev_pos
// string::npos: 문자열의 끝을 의미하는 상수 size_t max값 -1
// prev_pos 이상부터 delimiters에 있는 문자가 처음으로 나오는 위치를 찾는다
while ((pos = text.find_first_of(delimiters, prev_pos)) != std::string::npos)
{
// prev_pos부터 pos - prev_pos 길이만큼의 문자열을 tokens에 추가
if (pos > prev_pos)
{
tokens.push_back(text.substr(prev_pos, pos - prev_pos));
}
// pos + 1로 다음 문자로 넘어가기
prev_pos = pos + 1;
}
// 마지막 token 처리
if (prev_pos < text.length())
{
tokens.push_back(text.substr(prev_pos, std::string::npos));
}
return tokens;
}
int main()
{
// string_literals: ""s 쓸 수 있게 한다
using namespace std::string_literals;
std::vector<std::string> expected{ "this", "is", "a", "sample" };
assert(expected == split("this is a sample"s, ' '));
assert(expected == split("this,is a.sample!!"s, ",.! "s));
}// 이중 우선순위 큐
/*
priority queue 2개 쓰기
Min max
I 둘 다 넣기 size++
빼기 min 빼고 mincnt—
빼기 size - mincnt -maxcnt > 0이면 가능
출력
size - mincnt -maxcnt > 0
min max front
*/231111_priority_queue
std::less std:: greater
pq에 greater 넣으면 오름차순 정렬이다
// 이중 우선순위 큐
/*
priority queue 2개 쓰기
Min max
I 둘 다 넣기 size++
빼기 min 빼고 mincnt—
빼기 size - mincnt -maxcnt > 0이면 가능
출력
size - mincnt -maxcnt > 0
min max front
0이면 힙 둘 다 비워야 한다.
*/231112_bfs
// 쉬운 최단거리
/*
bfs로 입력 지점부터 모든 곳 방문하기
res에 cnt 넣기
*/231113_bfs
// 헌내기는 친구가 필요해
/*
bfs로 가능한 위치 큐에 넣기
P이면 res++하기
*/231114_호스트의 IP 주소 찾기
// 95. 호스트의 IP 주소 찾기
/*
io_context: asio 오브젝트
resolver: TCP endpoint에서 IP 주소를 얻기 위해 사용
resolve: IP 주소를 얻도록 요청
(boost::asio::ip::tcp::endpoint)*endpoint: endpoint를 TCP endpoint로 캐스팅
address: IP 주소를 얻기 위해 사용
cerr: standard error stream
what: 예외 메시지를 얻기 위해 사용
*/231115_regex
// 29. 차량 번호판 검증하기
/*
regex_match: 문자열 전체가 정규 표현식과 일치하는지 확인
sregex_iterator: 정규 표현식과 일치하는 문자열을 찾아주는 반복자
cbegin: const한 value를 사용하기 위한 iter
*/// 30. URL 추출하기
/*
smatch: string match한 결과를 저장하는 객체
optional: 값이 존재하지 않을 수도 있는 경우, nullptr(X)
*/// 31. 날짜를 문자열로 변환하기
/*
regex_replace: 문자열에서 정규 표현식과 일치하는 부분을 그룹을 캡처하고 다른 문자열로 바꾼다
*/// 가장 가까운 세 사람의 심리적 거리
/*
32*32*4
벡터에 넣고 다른 str끼리 비교
str i 자리 다르면 ++
결과 pq에 넣고 3개만 꺼내기
16 1 1 1
17 1 1 0
18 - 32
33 0 0 0
2명씩 가장 가까운 값만 얻었었다
-> 문제가 1-2 2-3 3-1 사이의 최소값의 합이었다
getDis에 문자열 3개 넘겨주고 res 값 넣어놓기
*/231119_브루트포스
// 리모컨
/*
누르는 것이 가능한 10개 배열 만들기
0 500000 체크 하면서 숫자 가능하면 GetCount하기
체크해서 min 값 구하기
가능한 조합 아니면 안 구하기
테케 100일 때
숫자 이상하게 들어간다
*/231120_multiset
// 리모컨
/*
누르는 것이 가능한 10개 배열 만들기
0 500000 체크 하면서 숫자 가능하면 GetCount하기
체크해서 min 값 구하기
가능한 조합 아니면 안 구하기
100에서 시작하는 경우 처리 추가
숫자 입력 안하고 +-만 하는 경우 추가
50만까지만 범위 -> 99만까지 체크
*/// 이중 우선순위 큐
/*
pq 두 개로 풀려고 했는데 순서 섞인다
-> multiset으로 begin, end 쓴다
*/**최단경로**
타겟에서 모든 노드 inf로 값 만들어두기
노드 2만개라 엣지 다 못만들어둔다
Mst만들어도 타겟에서 i노드까지 값은 또 구해야한다
타겟 노드에서 입력이면 값 업데이트
아니면 입력 받으면서 벡터 from 인덱스에 to value 넣기231125_하드웨어성능향상
스패닝
모든 노드 연결
set
유니온 파인드
Monotone stack
ECS
캐시 히트: 여러 오브젝트 같은 컴포넌트 계속 돌리기 떄문 → OOP를 꺤다
Matrix Transpose
64byte 캐시 히트 올리간다
SIMD
레지스터 용량 커져서 가능
반복된 계산 줄인다
CUDA GPGPU
렌더링이 아니라 계산용으로 사용
SIMD 자동으로 지원
shared memory
ram에다가 안 내릴 수 있게 된다
GPU에서 L1캐시
각 스레드들이 연산한 결과 합친다
231129_다익스트라
// 1753번 최단경로
/*
입력 엣지 수만큼 vector<pair<int, int>> 에 node[from][{to, weight}] 넣기
pq에 시작 노드 방문 넣기 {weight, from}
pq 돌면서 하나씩 빼기
weight, from 가져오기
node 연결 상태에서 from-to 체크해서 더 짧으면
값 업데이트 하고 pq에 넣어서 그 점 기준으로 다시 계산할 수 있게 하기
*/