[BOJ] 1463 1로 만들기 - 메모이제이션
[BOJ] 1463 1로 만들기 - 메모이제이션
2022.01.13매우 간단한 문제이다. 나눗셈을 하는것이 무조건 이득이다. 75를 예로 들어보자 75 는 2^3 * 3 ^ 2 + 3 이다. 결국 몇으로 나눌지가 문제이다 이것을 재귀적으로 분기 할 수 있도록 식을 구성한다. 반복되는것이 있을 수 있으므로 메모리에 저장해둔다. #include #include #include int Memoization[1000001] = { 0 , }; int RecCalc(int Number) { if (Number < 2) return 0; int Select2 = 0; int Select3 = 0; if (0 != Memoization[Number]) return Memoization[Number]; if (0 != Memoization[Number / 3]) Select3 = M..
[BOJ] 2579 계단 오르기 - 동적계획법
[BOJ] 2579 계단 오르기 - 동적계획법
2022.01.13어떠한 인덱스 N에 도착하기 위한 경우의 수는 두가지 밖에 없다. 두칸 전에서 두칸을 뛰어 오르던지, 한칸전에서 한칸을 뛰어 오르던지. 근데 두칸을 올라서 굳이 한칸을 빼먹어야 될 일은 없다. 그래서 무조건 한칸씩 계속 오르면 최대값이다. 다 올라간게 무조건 최대값이다. 이건 문제가 되질 않는다. 그래서 문제에선 세칸이 연속되면 안된다는 조건을 건다. 두칸전에서 두칸을 뛰어 오르는 경우를 생각해보자. 이건 단순히 N - 2 번째 칸까지의 최대값에서, N 칸을 밟은 거다. 두칸을 올라온 거니 따로 제약사항이 없다.MAX(N) = MAX(N-2) + COST(N)이 나온다. 한칸전에서 한칸을 뛰어 오르는 경우를 생각해보자. 여긴 조건이 있다.따라서 패턴을 강제시킨다. N - 1 번째 칸에서 한칸을 뛰어 올랐..
Windows OS - 스레드(Thread) 1편
Windows OS - 스레드(Thread) 1편
2022.01.12아주 기본적인 스레드의 개념. '프로세스는 왜 존재하는가' 를 생각해본다.왜 존재하는가? 간단하다. 프로세스는 프로그램 실행을 위해 존재한다. 프로그램 실행은 어떻게 이루어지는가? 프로그램은 명령어의 집합이다. 기계어 명령어를 파일로 만들면 그게 우리가 실행파일이라고 부르는것이 된다. 기계어 명령어가 CPU로 전달되면 CPU는 그것을 이해하고 실행한다. 이게 프로그램의 실행이다. 아무튼, 프로세스는 프로그램 실행을 위해 존재한다고 했다. 여기서 스레드라는 개념이 등장한다. 스레드라는 개념은 프로세스의 개념보다는 비교적 늦게 등장했다. 프로세스가 가지는 프로그램 실행의 개념을 스레드에게 100% 이식했다. 간단한 비유를 하자면 부서가 분리된 것이다. 이 스레드라는 것이 프로그램을 실행한다. 프로세스와 스레..
[BOJ] 1932 정수 삼각형 - 동적 계획법
[BOJ] 1932 정수 삼각형 - 동적 계획법
2022.01.10매우 간단한 문제이다. 아래층으로 값을 더하고, 거기 기록한다. 어떠한 인덱스에서 갈수있는 아래층 원소의 인덱스를 구하기 위해서는 현재 인덱스와 내가 속한 레이어의 번호를 더해주면 쉽게 구할수 있다. 인덱스 2는 4와 5로 접근 가능하고, 인덱스 3도 5에 접근 가능하다. 자연스럽게 최대값이 구해진다. 레이어를 하나씩 증가시키면서 원소 개수만큼 루프를 돌리며 바로 다음 레이어의 최대값을 계속 구해주다 보면 원하는 값을 구할 수 있다. 코드로 구현한 결과는 다음과 같다. #include int MaxResult[125251] = { 0 , }; int Cost[125251] = { 0 , }; int main() { std::cin.tie(0); std::cin.sync_with_stdio(false); ..
Winsock/C++ - IOCP 종료처리 관련
Winsock/C++ - IOCP 종료처리 관련
2022.01.101. closesocket 이후에 OS는 closesocket 의 인자로 전달했던 것과 같은 값을 가지는 핸들을 리턴할 수 있다. closesocket은 TCP 단에서의 연결종료 루틴의 수행 뿐 아니라 핸들을 반납하는 역할 또한 수행한다. closesocket이후 OS는 같은 핸들을 반환할 수 있는데, IOCP의 경우 멀티스레드로 사용하는 경우가 대부분이기 때문에 동기화 문제가 발생할 가능성이 크다. 따라서, closesocket을 두번이상 호출하는 것은 위험성을 가지며, closesocket을 호출하기 전에는 해당 소켓 핸들에 더이상 접근이 없음을 확실시 해야 한다. 2. 1Recv 1Post 가 가장 보편적이고 가장 편리하고 가장 깔끔하다. (수신하고 - Post 를 반복한다.) 수신에 대한 완료 통..
Winsock/C++ - 4. setsockopt, getsockopt, WSAIoctl
Winsock/C++ - 4. setsockopt, getsockopt, WSAIoctl
2022.01.04[프로그래밍/소켓 프로그래밍] - Winsock - 1. WSAGetLastError, FormetMessage [프로그래밍/소켓 프로그래밍] - Winsock - 2. TCP 연결 bind,listen,accept 그리고 connect [프로그래밍/소켓 프로그래밍] - Winsock - 3. 데이터 송수신 send, recv 운영체제는 다양한 소켓 옵션등을 제공한다. winsock을 사용하는 App은 소켓 옵션을 사용해 소켓의 동작방식을 제어할 수 있다. 기본적으로는 TCP등 네트워크 프로토콜의 동작방식과 밀접한 관련이 있으나, 그렇지 않은 옵션도 있다. OS 자체의 전역적 네트워크 옵션과 정책에 따라 다르게 동작할 수 있다. 옵션 설정에는 setsockopt 함수가 사용된다. optval은 포인터를 ..
Winsock/C++ - 3. 데이터 송수신 send, recv
Winsock/C++ - 3. 데이터 송수신 send, recv
2022.01.03Winsock - 1. WSAGetLastError, FormetMessage https://so-what-93.tistory.com/42 Winsock - 2. TCP 연결 bind,listen,accept 그리고 connect https://so-what-93.tistory.com/43 연결이 되었으니 데이터 송수신을 진행해 보기로 한다. 송수신은 send와 recv를 이용한다. send와 recv는 사용법이 보이듯이 매우 간단하다. 사용법은 매우 간단하다. send가 보내는 함수라고 생각할 수 있고, recv가 받는 함수라고 생각할 수 있다. 허나 실제적인 동작은 어디까지나 송수신 커널 버퍼에 대한 복사 작업이다. send 함수의 경우, 커널의 송신 버퍼에 buf의 내용을 len 만큼 카피한다. 송..
Winsock/C++ - 2. TCP 연결 bind,listen,accept 그리고 connect
Winsock/C++ - 2. TCP 연결 bind,listen,accept 그리고 connect
2022.01.03TCP 연결을 위해서는 우선 포트를 LISTENING 상태로 만들어야 한다. 그래야 TCP 간 3way hand shake를 진행할 수 있다. 이는 netstat -a 로 확인이 가능하다. 소켓을 이용해 구현할 때에는 다음과 같이 진행한다. 매우 간단하다. 1. 소켓을 생성한다. 2. 만들어진 소켓에 주소를 매핑시킨다. 3. listen을 호출한다. 이러면 해당 주소( 해당 소켓) 은 LISTENING 상태가 된다. SOCKET ListenSocket = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP); //AF_INET -> 주소체계 //SOCK_STREAM-> TCP 전송방식 //IPPROTO_TCP-> IPv4 헤더 안에 6이 입력됨. 소켓을 만들때에는 socket 함수를..
Winsock/C++ - 1. WSAGetLastError, FormetMessage
Winsock/C++ - 1. WSAGetLastError, FormetMessage
2022.01.03WSA(Windows Socket API)에서 소켓작업 실패시 WSAGetLastError로 이를 얻어 올 수 있다. 이 에러코드는 전역변수가 아니라 TLS(Thread Local Storage) 에 저장된다. 이 함수는 각 스레드가 저마다 에러코드를 저장한다는 것. 그러니 에러가 발생한 컨텍스트를 수행중인 스레드의 에러코드가 다른 스레드에 의해 오염될 일은 걱정하지 않아도 된다. 얻어온 에러코드는 MSDN을 통해 정보를 확인한다. https://docs.microsoft.com/ko-kr/windows/win32/winsock/windows-sockets-error-codes-2 Windows 소켓 오류 코드 (Winsock2. h) - Win32 apps Windows WSAGetLastError 함..
Windows OS - C/C++ App과 Process(프로세스) 기본
Windows OS - C/C++ App과 Process(프로세스) 기본
2022.01.02Windows OS의 프로세스 Windows OS에서 프로세스는 실행중인 프로그램의 Instance라고 정의된다. 프로세스에 관련된 내용은 정말로 방대하지만, 우선은 기본적으로 간략한 내용들만을 다루기로 한다. 프로세스는 두개의 컴포넌트로 구성된다. 1. 프로세스 관리를 위해 운영체제가 사용하는 커널 오브젝트. 2. 프로세스 실행 모듈 Code, DLL Code, Thread Stack과 Heap 등을 위한 메모리 블럭. 프로세스는 절대로 자력으로 실행될 수 없다. 프로세스의 Context를 실행하는 주체는 어디까지나 Thread이다. 따라서 OS가 프로세스를 생성하면 일단은 무조건 1개의 스레드가 기본적으로 생성되는데, 이를 주 스레드(Primary Thread) 라고 부른다. 프로세스내에 Thread..
Windows OS - Kernel Object(커널 오브젝트)
Windows OS - Kernel Object(커널 오브젝트)
2022.01.02커널 오브젝트는 무엇인가? Windows는 Object의 형태로 OS내의 자원을 관리한다. Object는 메모리 블럭의 형태를 띄고있다. C/C++ 의 구조체를 생각하면 된다. https://docs.microsoft.com/en-us/windows/win32/sysinfo/object-categories Object Categories - Win32 apps The system provides three categories of objects: user, graphics device interface (GDI), and kernel. docs.microsoft.com 이중에서, 그 중요도가 높아 Windows Kernel에 의해서 관리되는 자원을 Kernel Object로 분리해두었다. Windows ..
L2 - LAN Adapter(랜카드) 의 동작
L2 - LAN Adapter(랜카드) 의 동작
2021.12.31LAN Adapter는 송신에 대해서 어떤일을 하는가? 송신하려는 데이터가 랜카드 까지 도착했다면 사실상 통신에 필요한 정보는 완성이 된 상태이다. 물론 IP Header 까지만 넣고, 랜카드에서 MAC Header를 붙이는 것 아닌가 오해할 수 있다. 랜카드가 MAC Address를 가지고, MAC Address가 L2에서 사용되는 주소니까, L2 Header도 랜카드에서 붙이는 것이 아닌가...? " 생각할수 있겠지만, 그렇지 않다. 랜카드에 도착하기 전 IP Header, MAC Header 세팅을 모두 끝낸다. Header를 붙이는 것은, OS 내지는 소프트웨어가 하는일이다. IP Header와 MAC Header는 단지 L3장비와 L2장비가 이해할수 있는 주소체계를 가지고 있는 것이다. 데이터 ..