[BOJ] 13902 개업 2 - 동적 계획법
[BOJ] 13902 개업 2 - 동적 계획법
2021.12.03동적계획법을 이용하면 쉽게 해결이 가능한 문제이다. 웍의 경우는 동시에 2개를 사용이 가능하므로, 웍의 조합으로 새로운 크기의 웍을 만들고 반복문을 이용해 동적계획법을 사용한다. N 그릇을 요리한다고 할때, 내가 가진 웍의 크기가 각각 3 4 5 6 이라고 하자. 그렇다면 요리횟수의 최소값은 (N - 3) 그릇을 요리하는 회수 + 1 (N - 4) 그릇을 요리하는 회수 + 1 (N - 5) 그릇을 요리하는 회수 + 1 (N - 6) 그릇을 요리하는 회수 + 1 중 하나이다. 코드로 구현하면 다음과 같다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; std::vector Works; bool ..
[BOJ] 1904 01타일 - 동적 계획법
[BOJ] 1904 01타일 - 동적 계획법
2021.12.03동적 계획법을 이용해야 하는 문제이다. 이전의 답이 다음의 답을 정한다. 수열을 만들때 1 또는 00 만 선택할 수 있다. N = 1 , N = 2 일 만들수 있는 수열은 각각 1 그리고 11,00 이다. 이제 3일때 부터가 중요하다. 길이가 3인 수열을 만들기 위해서는 길이가 2인 수열에 1을 추가를 하던지, 길이가 1인 수열에 00을 추가하던지, 11을 추가해야한다. 그런데 잘 생각을 해보면 길이가 1인 수열의 원소의 뒤에 11을 붙이면 경우는 길이가 2인 수열에서 1을 붙인것 과 겹친다. 길이가 N인 수열은 길이가 N-2인 수열의 개수 + 길이가 N-1인 수열의 개수 와 같다. WHY ? N-1 수열에는 N-2 에서 1을 추가해 만든 수열이 포함되어 있음을 기억하자. 따라서 N-2 수열에서는 무조건..
[BOJ] 14889 스타트와 링크 - Back Tracking
[BOJ] 14889 스타트와 링크 - Back Tracking
2021.12.02인원을 구성하는 문제 역시 Back Tracking 을 이용한 완전탐색 문제의 대표적인 예이다. 문제를 보면 같은 인원수를 원하고 있다. 10 명 중 5명을 골라서 팀을 이루면 나머지는 자동적 으로 정해지는 것이 아닌가? 따라서 재귀호출의 Depth는 선수의 수를 2로 나눈 값이 된다. 이제 재귀 함수를 만드려고 한다. 헌데 한가지 고민이 생긴다. A B 로 팀을 만들면 함수는 리턴한다. 상대팀은 자동적으로 C D 가 된다. C D 로 팀을 만들면 함수는 리턴한다. 상대팀은 자동적으로 A B 가 된다. 팀 이름만 달라지고 결국 같은 답을 두번 구하게 되는것이다. 그래서 한번 Depth의 끝에 도달하면 두개의 팀 모두의 능력치를 저장한다. A B 팀일때 C D 가 한팀이 된다. 이때 A B 를 가진 팀의 ..
[BOJ] 1003 피보나치 함수 - 동적 계획법
[BOJ] 1003 피보나치 함수 - 동적 계획법
2021.12.01동적계획법을 사용한다는 것은 이전의 연산결과를 통해 다음의 연산결과를 구해내겠다는 것이다. 위의 피보나치 함수의 예는 아주 간단하고도 대표적인 예이다. 위 함수를 F(N) 이라고 부른다고 하자. F(N) 은 F(N-1) 과 F(N-2) 를 호출한다. 그렇다면 F(N-1) 은 F(N-2)와 F(N-3)을 , F(N-2)는 F(N-3)과 F(N-4)를 호출 한다. 위의 조건을 보면 F(1)일때는 1을 출력한다. F(0)일때는 0을 출력한다. 그러면 F(2)는 ?? 1과 0을 1개씩 출력하는 것 이다. 조금만 더 계산해보면 F(3)은 F(2)의 결과 (1 과 0 각각 1개씩) 을 출력하되 F(1)의 것 (1만 1개)을 출력한다. F(4) 의 경우는 ? F(3)의 결과값에 , F(2) 결과값이 합쳐진 것이 결과..
[BOJ] 9184 신나는 함수 실행 - Memoization
[BOJ] 9184 신나는 함수 실행 - Memoization
2021.12.01문제를 읽어보면 상당히 식이 복잡하다. 어떻게 흘러갈지가 한눈에 보이지 않는다. Branch Depth가 깊어질 가능성이 크다. 이 경우에는 Branch의 결과값을 저장해두고 재귀 호출시 이전에 계산했던 값이 있을경우에는 Branch하는 대신 이미 구해진 값을 연산에 이용하면 속도 최적화에서 이득을 볼 수 있다. #define _CRT_SECURE_NO_WARNINGS #include #include int Ans[101][101][101] = { 0 , }; int RecursiveCall(int A, int B, int C) { if (A 70) { if (0 == Ans[70][70][70]) Ans[70][70][70] = RecursiveCall(70, 70, 70); return Ans[70]..
[BOJ] 14888 연산자 끼워넣기 - Back Tracking
[BOJ] 14888 연산자 끼워넣기 - Back Tracking
2021.12.01매우 평범하고도 쉬운 Back Tracking 문제이다. 기존의 Back Tracking 과 똑같이 Branch 의 Return 을 받고, 상태 초기화 후 반복문 돌리니 쉽게 풀어 낼 수 있었다. 연산자 우선순위는 무시한다고 했으므로 단순하게 이전 선택지에 대한 누적 결과를 Param으로 주는 Branch를 진행한다. Branch Depth 의 끝에 도달했을때가 식을 모두 진행한 결과이므로 이때에 최소값과 최대값을 갱신한다. 진입점에서 맨 처음에 오는 숫자는 이전의 결과가 없으므로 자기 자신을 넣어준다. #define _CRT_SECURE_NO_WARNINGS #include #include #include int Operators [4]; int Numbers [100]; int Max = 0X8000..
[BOJ] 2580 스도쿠 - Back Tracking
[BOJ] 2580 스도쿠 - Back Tracking
2021.12.01스도쿠 퍼즐은 다음과 같은 규칙을 가진다. 한칸에 1부터 9의 숫자를 넣을수 있다. 가로 줄에 같은 숫자가 존재 하면 안된다. 세로 줄에 같은 숫자가 존재 하면 안된다. 가로 세로 크기가 3인 큰 정사각형으로 잘랐을때, 하나의 큰 정사각형 내에 1부터 9의 숫자가 하나씩 존재해야 한다. 그렇다면, 어떠한 Row에 숫자가 존재하는지 간단하게 검사할 수 있다. 또, 어떠한 Col에 해당 숫자가 존재하는지 간단하게 검사할 수 있다. 가로세로 크기 3인 큰 정사각형 내에 숫자가 존재하는지 간단하게 검사할 수 있다. 퍼즐의 빈칸에 대해, 이 3가지 배열 조건을 검사하고, 만족하는 경우 숫자를 기입하며 Back Tracking 하면 쉽게 답을 찾을 수 있다. 코드를 구현하면 다음과 같다. #define _CRT_S..
Winsock - 소켓 송수신 버퍼 사이즈 대체 어떻게 해야하나?
Winsock - 소켓 송수신 버퍼 사이즈 대체 어떻게 해야하나?
2021.12.01winsock을 다루는 많은 서적에서 SO_SNDBUF를 0으로 맞추면 send 시에 커널 버퍼에 카피를 하지 않기 때문에 성능에 이득이 된다고 한다. 하지만 실제로는 0로 맞춘다고 해도 복사가 일어난다. 아래의 msdn을 참고. https://docs.microsoft.com/en-us/troubleshoot/windows/win32/data-segment-tcp-winsock You can change the amount of Winsock kernel buffer allocated to the socket using the SO_SNDBUF option (it's 8K by default). If necessary, Winsock can buffer more than the SO_SNDBUF buf..
[BOJ] 9663 N Queen 알고리즘 - Back Tracking
[BOJ] 9663 N Queen 알고리즘 - Back Tracking
2021.11.30NQueen 알고리즘은 Back Tracking 알고리즘의 대표적인 예이다. 간단하게 N개의 퀸을 크기가 N인 체스보드에 서로 공격할수 없게 배치 하려면 어떻게 해야 하느냐? 이다. 퀸의 경우 다음과 같은 공격범위를 가진다. 따라서, 내가 N개의 Row를 탐색하려고 한다면, 이전에 어떠한 열에 두었는가?를 기억하면 그 다음 열에서는 탐색을 할 필요가 없다. (퀸이 Y축으로 쭉 공격이 가능한것임을 기억.) 예를 들어보자. 8A에 퀸을 두었다. 8A에 퀸을 두었으니 해당 Row 8은 더이상 둘수 없다. Col A 에도 더 이상 둘 수 없다. 이 정보를 기록해둔다. 헌데, 한 Row에 퀸을 두면 어짜피 다음 라인을 서치 할것이 아닌가? 따라서 Col A에 퀸이 놓여있다는 것만 기억하면 된다. Row를 8부터 ..
[C++] 정적라이브러리 vs 동적라이브러리
[C++] 정적라이브러리 vs 동적라이브러리
2021.03.061. 동적 라이브러리(Dynamic Link Library) 프로그램 실행 시 필요시만 외부 DLL 파일에서 함수를 참조 프로그램 실행 시 프로그램 로딩 시간이 단축 함수 업그레이드 시 해당 DLL만 수정 배포한다 소스 외부 유출 방지 효과 실행 파일 만들때 필요한 파일: .h,.lib (*.dll 참조 용) 프로그램 실행할 할 때 필요한 파일: *.dll (배포할 때 *.dll 필요) dll 제작 시 lib도 같이 생성됨 2. 정적 라이브러리(Static Link Library) 필요한 함수를 프로그램 코드에 붙여 프로그램 자체에서 참조 프로그램 실행 후 빠른 처리시간 프로그램 실행 파일만 있으면 실행(하나의 파일만 있으면 됨) 소스 외부 유출 방지 효과 실행 파일 만들때 필요한 파일: .h,.lib ..
멀티스레드 프로그래밍 - Data Race
멀티스레드 프로그래밍 - Data Race
2021.02.17멀티스레드 프로그래밍을 접하고 가장 처음 접하는 문제가 바로 Data Race 문제이다. Data Race에 대해 설명할때 가장 자주 쓰이는 예시는 다음과 같다. 1. 전역변수 G가 있다. 이 값을 0으로 초기화한다. 2. 스레드 A가 G의 값을 1씩 n번 증가시킨다. 3. 스레드 B가 G의 값을 1씩 n번 감소시킨다. 당연하게도 A가 1씩 n번 더했고, B가 1씩 n번 뺐으니까 결과값은 0이 되어야한다. 허나, 이 일을 시키면 결과값은 0이되거나, 0이 아닐수도 있다. 왜 그런가 보면, G++ 이라는 코드는 다시 3개의 어셈블리어 연산으로 해석된다. 1. 전역변수 G의 값을 레지스터로 가져온다. 2. 레지스터에 저장된 값을 1증가 시킨다. 3. 레지스터에 저장된 값 ( 즉, 1이 증가된 값)을 다시 전..