Be a developer

집합을 만드는 문제는 비트 마스크를 통해서 풀 수 있다. 만약 공집합에 1이라는 원소를 추가한다면 이는 0이라는 숫자의 1번 비트에 1을 추가하는 것과 같다. 따라서 집합을 나타내는 변수 ans가 있고, ans가 0이라고 하자. ans |= (1

연산자 끼워넣기 문제와 똑같다. 다른 점이 있다면 모든 숫자를 다 사용했을 때 함수를 return 시킨다는 것. 각 숫자 사이에 4개의 연산자가 다 들어갈 가능성이 있으므로, 4^(N-1)의 시간복잡도를 갖는다. N이 최대 11이므로 브루트포스로 풀 수 있는 문제이다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include #include using namespace std; vector ans;int n; void solve(int idx, int sum, int plus, int minus, int mult, int div, vector num) { //모든 숫자를 연산에 다 사용하면 return한다. i..

앞에 까지 재귀로 푼 문제들은 하나의 경우를 선택하느냐 선택하지 않느냐 하는 문제였다. 하지만 이번 문제는 연산자 4가지 중 하나를 넣느냐 아니면 넣지 않느냐 하는 문제이기 때문에 경우의 수를 4가지로 나누어서 풀었다. 연산자의 수가 주어진 숫자의 수 보다 1개 적어서 딱 맞기 때문에, 불가능한 경우를 따로 만들어줄 필요가 없다. 재귀의 종료 조건은 연산자의 개수를 다 사용하여 0개가 되는 것이다. minmax_element함수를 사용하는 법을 익숙하게 해야 겠다. auto 연산자를 사용하는 것을 익혀야 한다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include #include using namespace..

앞선 문제들을 풀었다면 쉽게 풀 수 있는 문제이다. 마찬가지로 현재 날짜를 선택하는 경우와 선택하지 않는 경우로 나눠서 풀면된다. N+1일을 넘어가지 않도록 하는 것이 중요하다.(딱 N+1일에 끝나도록 한다.) 답이 될 수 있는 경우에 return을 하는 것을 매번 까먹는다. 까먹지 않도록 주의 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include using namespace std; int n;int ans; void solve(int idx, int sum, vector t, vector p) { //N+1일을 넘어가면 안되므로 return if (idx > n)return; //..

sum은 인자로 전달해준다. 중간에 원소 몇 개로 합을 완성할 수도 있지만, 아래 코드에서 sum과 s가 같더라도 이후의 원소가 들어오는 것에 따라서 다시 sum과 s가 같아질 수 있다. 따라서 경우의 수를 (s==sum && i == n)과 (s != sum && i == n) 두 가지로 나누어서 풀어야 한다. 또한 합이 0이 입력되면, 아무것도 선택하지 않아도 0이 되므로, 공집합은 허용되지 않는다. 따라서 답을 출력할 때 1을 빼준다. 123456789101112131415161718192021222324252627282930#include #include #include using namespace std; int n, s;vector v(20);int ans; void go(int i, int ..

이전에 풀었던 로또 문제를 재귀로 푸는 것이다. 이전에는 순열로 풀기위해 선택한 번호는 0으로 넣고, 선택하지 않은 번호는 1로 넣는 새로운 vector를 선언해주었다. 하지만 재귀에서는 앞선 암호 문제처럼 재귀를 통해 넣고, 안 넣고를 할 수 있기 때문에 새로운 vector가 필요없다. 대신 넣고 안 넣고를 check할 check 배열을 하나 생성한다. check 배열을 놓고 풀지 않고, vector하나를 두고 선택하면 vector에 push_back으로 넣고, 넣지 않으면 pop_back으로 빼서 풀 수도 있다. 자세한 설명은 아래 주석으로.. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484..

일단 암호가 오름차순이 되어야 하므로 입력받은 문자들을 sorting한다. sort는 algorithm 헤더에 있는 함수이다. 문자열을 만들고 문자를 더하여 문장을 만들어 출력해야 하므로, string을 쓴다. c++은 string 자료형이고, java는 String 자료형이다. 헷갈리지 말자. 자세한 설명은 아래 코드의 주석으로.. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include #include #include using namespace std; int l, c;//l은 만들어야 할 암호의 길이, c는 주어지는 알파벳의 수 bool ch..

이전에 for문을 통해서 같은 문제를 풀었다. for문은 재귀로 바꿀 수 있기 때문에 재귀로도 풀 수 있다. for문은 10개를 만들어야 했지만, 재귀는 많은 코드가 필요없으므로 조금 더 간단하게 풀 수 있다. 재귀는 1.불가능한 경우 2.정답을 찾은 경우 3.다음 경우를 호출하는 경우 와 같은 3가지 경우로 나누어 풀어야 한다. 1,2,3을 선택할 수 있으므로 시간 복잡도는 O(3^n)이다. 자세한 설명은 아래 코드의 주석으로.. 123456789101112131415161718192021222324252627282930#include using namespace std; int ans;int n;void solve(int sum) { //1, 2, 3 중에 더하는 거라서 n을 넘어갈 수도 있음. 그 ..