목록algorithm/C++ (19)
on my way
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/ZUaKr/btrjxABxL7f/ejFjFrIHKqykakNWiXkic1/img.png)
* 생각한 아이디어 및 문제 풀이 * 코드 #include using namespace std; int getMax(int n1, int n2, int n3){ int max = 0; if (max > N >> M; int dp[1001][1001]; for(int i=1; i val; max = getMax(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]); dp[i][j] = ..
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/HhlL1/btrjudUuAiB/8vZAQ0cQYeYTqqa0E8feek/img.png)
* 생각한 아이디어 및 문제 풀이 dp[n] = dp[n-1] + dp[n-2]; dp[1], d[2]는 초기에 선언해준다. * 코드 #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int N; cin >> N; int dp[1001]; dp[1] = 1; dp[2] = 2; if(N > 2){ for(int i=3; i
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/nPznO/btrjvSidD5Y/MUqmepYNJtlk462gNhCZ31/img.png)
* 생각한 아이디어 및 문제 풀이 다이나믹 프로그래밍을 통해 문제를 푸는 방법은 1, 2, 3의 합을 미리 수동으로 구해놓아야 한다는 것이 시간을 아낀다는 점의 핵심이다. 1을 1, 2, 3의 합으로 만드는 방법 : 1가지(1)로 dp[1] = 1 2를 1, 2, 3의 합으로 만드는 방법 : 2가지(1+1, 2)로 dp[2] = 2 3을 1, 2, 3의 합으로 만드는 방법 : 4가지(1+2, 2+1, 1+1+1, 3) 그리고 +1된 다음수부터는 이렇게 1, 2, 3을 합한 방법에서 값을 +1씩 더하면 되는 것이므로 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]의 공식으로 만들어지는 것을 알 수 있다. * 코드 #include using namespace std; int main(){ i..
![](http://i1.daumcdn.net/thumb/C150x150.fwebp.q85/?fname=https://blog.kakaocdn.net/dn/QIRkE/btriMIGU7B2/zytTMBzBE79p1UOBQm5Xck/img.png)
* 생각한 아이디어 및 문제 풀이 체스에서 queen의 특성은 거리와 상관없이 모든 방향으로 움직일 수 있다. n*n 정사각형 안에 n개의 queen을 배치하는 문제로, queen들은 자신의 일직선상 및 대각선상에 아무 것도 놓이면 안된다. Queen함수에서는 각각 단계별로 퀸이 존재할 수 있는 여부를 확인한다. isUsed1는 같은 열에 퀸이 존재하는지, isUsed2는 우상대각선에 퀸이 존재하는지, isUsed3는 좌상대각선에 퀸이 존재하는지 확인한다. (가로의 인덱스가 i, 세로의 인덱스가 j일때 우상대각선은 i+j가 모두 일치, 좌상대각선은 i-j=0이다.) 만약 (level, i)에 퀸을 둘 수 없다면 isUsed1, isUsed2, isUsed3를 모두 true로 변경하고 Queen(level..
* 생각한 아이디어 및 문제 풀이계산 가능한 모든 경우의 수를 완전 탐색으로 계산하여 풀이하면 된다. 연산자의 우선 순위같은 것이 없고, 그냥 앞에서 뒤로 차례로 모든 연산자마다의 값을 max와 min으로 계산한다. * 코드#include#includeusing namespace std;int N;int number[12];int operators[4];int maxNum = INT32_MIN;int minNum = INT32_MAX;void Calculator(int plus, int minus, int mul, int div, int count, int sum) { if (count == N) { maxNum = max(maxNum, sum); minNum = min(minNum, sum); } ..
* 생각한 아이디어 및 문제 풀이수 하나를 더할 때 마다 답이 아니면 처음부터 진행하는 것이 아닌, 그 수를 빼고 다른 수를 더해 확인하는 백트래킹 방식을 사용하여 재귀함수 형식으로 문제를 풀이한다. 주의할 점은 sum이 해당하는 값에 도달하더라도 뒤의 것을 계속해서 탐색해야한다는 것이다. * 코드#include using namespace std;int arr[21];int N, S, cnt=0;void backTracking(int start, int sum) { if (start >= N) return; int tmp = sum; tmp += arr[start]; if (tmp == S) cnt++; for (int i=start+1; i> N >> S; for (int i=0; i> arr[i]..