문제 설명DP 문제입니다. 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.제한 사항풀이  ..

SpinLock멀티스레드 환경에서 동기화를 관리하기 위해 사용되는 락(잠금) 메커니즘공유 자원에 접근하려는 여러 스레드 중 하나만 접근하도록 보장하지만, 대기 중인 스레드가 CPU를 사용하면서 반복적으로 락 상태를 확인하는 방식 user level에서 발생하는 동기화방법 [동작 방식]1. 락이 풀려있다면 락을 획득하고, 자원을 사용. 락이 걸려 있다면, 다른 스레드가 락을 풀 때까지 계속 반복해서 락 상태 확인2. 스핀(반복), 락이 풀릴 때까지 기다리면서 반복적으로 상태를 확인하기 때문에 spinlock.3. 자원을 사용한 스레드는 락을 해제하여 다른 슬드가 자원에 접근할 수 있도록 함 [장점]: 시스템 호출을 통해 커널 모드로 전환하는  [[#Mutex Lock]]  에 비해 오버헤드가 적음  락이 ..

문제 설명DP 문제입니다. 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.  모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의..

문제 설명DP 문제입니다. 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.제한 사항풀이  전체 코드#include #include using namespace std;const int MAX = 1000001;int N;int DP[MAX];int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N; DP[1] = 0; for (int i = 2; i 횟수만 구하는 문제였으면 위와같이 작..

문제 설명DP 문제입니다. 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.제한 사항풀이 DP[i] = max(DP[i], DP[1...i-1] + Arr[i]);전체 코드#include #include using namespace std;const int MAX = 1001;int N;int DP[MAX];int Arr[MAX];int main() { ios::sync_with_stdio(false); ci..

문제 설명DP 문제입니다. 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.제한 사항 풀이DP[i-1]에 2*1타일 붙이는 경우 + DP[i-2]에 2*2 타일 붙이는 경우따라서 DP[i] = DP[i-1] + DP[i-2]. 전체 코드#include using namespace std;const int MAX = 1001;int N;int DP[MAX];int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N; DP[1] = 1; DP[2] = 2; for(int i=3; i

멀티 쓰레드 환경?: 일반적인 STL Container 문법은 멀티 쓰레드 환경에서 동작하지 않음1. vector : 메모리 동적할당 방식. 1. 문제 : 멀티 스레드 환경에서는 순서가 보장되지 않아, 메모리 공간을 삭제하거나 옮기는 과정에서 crash 발생, 메모리 손실 발생2. 해결법1 : vector.reserve()를 사용하면 메모리 공간을 삭제하거나 옮기는 일이 발생하지 않아서 crash는 나지 않지만, 메모리 손실 발생 3. 해결법2 : Lock사용2. volatile : 컴파일러에게 최적화를 하지 말아달라고 부탁int32 a = 0;a=1; a=2; a=3; a=4; cout : Debug모드가 아닌 Release모드(최적화 진행)로 빌드하면 a = 4만 남게 됨 volatile 키워드를 추..

문제 설명DP 문제입니다.돌 게임은 두 명이서 즐기는 재밌는 게임이다.탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 제한 사항풀이N이 3의 배수일 때(3, 6, 9)에는 DP[i] = DP[i-3] + 1이고, 그렇지 않다면 DP[i] = DP[i-1] + 1 이 된다.  전체 코드#include using namespace std;const int MAX = 1001;int N;int DP[MAX];int main() { ios::sync_with_stdio(fal..