멀티 쓰레드 환경?: 일반적인 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..

문제 설명DFS + DP 문제입니다.여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로..

문제 설명DP 문제입니다.어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다.이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오. 제한 사항풀이  전체 코드#include using namespace std;const int MAX = 100001..

문제 설명DP 문제입니다.n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 제한 사항풀이  전체 코드#include using namespace std;const int MAX = 10001;int N, K;int DP[MAX] = {0, };int Coin[101] = {0, };int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N >> K; for(int i=1; i> Coin[i]; ..

문제 설명DP 문제입니다.3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 제한 사항풀이  전체 코드 #include using namespace std;const int MAX = 31;int N;int DP[MAX] = {0, };int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N; DP[0] = 1; DP[2] = 3; if(N%2 == 1) { cout

문제 설명DP 문제입니다.0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 제한 사항풀이 전체 코드 #include using namespace std;const int MAX = 201;int N, K;int DP[MAX][MAX] = {0, };int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N >> K; for(int j=0; j

문제 설명DP 문제입니다.어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다. 제한 사항풀이즉, DP[i] = DP[n-1]*2 + DP[n-2] 라는 식이 도출됩니다.전체 코드 #include using namespace std;const int MAX = 100001;int N;int DP[MAX]..

문제 설명DP 문제입니다.RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.제한 사항풀이전체 코드#include #include using namespace std;const int MAX = 1001;int N, minCost = 987654321;int DP[MAX][3] =..

문제 설명DP 문제입니다.요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 전설카드레드카드오렌지카드퍼플카드블루카드청록카드그린카드그레이카드 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다...