Be a developer

일단 암호가 오름차순이 되어야 하므로 입력받은 문자들을 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을 넘어갈 수도 있음. 그 ..

주어지는 숫자의 순서가 바뀌지 않기 때문에 연산자만 순열을 통해 풀면된다. 수의 개수가 최대 11개이므로 연산자의 개수는 최대 10개가 되어 순열로 풀 수 있는 문제이다. 브루트포스로 모든 경우의 수를 만들어 보면서 최댓값과 최솟값을 구한다. algorithm 헤더의 minmax_element함수를 이용한다. 자세한 설명은 코드의 주석으로.. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #include using namespace std; int main(int argc, char** argv) { int n; cin >> n; vector v(n); ve..

이 문제는 배열 안에 중복된 수가 있어도 next_permutation이 잘 작동한다는 것을 이용해서 푼다. 예시와 같이 k=8, s={1,2,3,5,8,13,21,34}인 경우 0을 먼저 6개 넣고, 다음에 1을 2개 넣어야 한다. 그렇게 되면 0 0 0 0 0 0 1 1과 같은 vector가 만들어지고, 이를 next_permutation을 사용해 섞으면 뒤에서 부터 섞이게 되어 모든 순열을 다 검사할 수 있다. 만약 1을 6개 먼저 넣고 0을 2개 넣게 되면, 1 1 1 1 1 1 0 0 과 같은 vector가 만들어지고, 모든 순열을 다 검사하지 못하게 된다. 원소는 오름차순으로 입력받기 때문에 sorting할 필요가 없다. 0과 1을 vector에 넣을 때 조심해야 한다. vector v(n)과..

N이 최대 10일 때 10개의 도시 목록을 배열에 넣고 next_permutation을 통해서 풀면된다. 원소가 10개 이하이기 때문에 브루트 포스로 풀 수 있는 문제다. 한 번 갔던 도시로는 다시 갈 수 없기 때문에 순열로 풀 수 있는 문제다. 시작점은 중요하지 않다. 만약 4개의 도시가 있다면 1 -> 2 -> 3 -> 4 -> 1 이 루트와 2 -> 3 -> 4 -> 1 -> 2 이 루트에 필요한 비용은 같기 때문이다. 따라서 시작점을 정해놓고 알고리즘 풀이를 하기 때문에 시간 복잡도가 O(N * N!)보다 작다.(O( (N-1) * (N-1)!)) 처음에 순서대로 도시 번호를 넣어준 다음 순열을 돌리면서 모든 경로의 수를 구한다. 자세한 설명은 주석으로.. 1234567891011121314151..

abs함수와 max함수를 쓴다는 것 외에는 딱히 설명할게 없다. 한 가지 중요한 점은 순열을 사용하기 위해서는 먼저 정렬을 해야 한다는 것이다.(모든 경우를 다 돌려보기 위해서) next_permutation을 사용할 때는 첫 번째 순열을 돌린 후에 해야 하기 때문에 do-while을 사용하자. 시간복잡도는 N이 최대 8이므로 8!로 순열로 해결할 수 있는 문제임을 알 수 있다. 1234567891011121314151617181920212223#include #include using namespace std; int main(int argc, char* argv[]) { int n, ans = 0, sum; cin >> n; int *bf = new int[n]; for (int i = 0; i > ..

순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 다음 순서의 순열을 찾으려면 c++에서는 next_permutation과 prev_permutation이 존재하기 때문에 사용하면 된다. 직접 구현하기 위한 방법은 아래와 같다. 1. A[i-1] =i 이면서 A[j] > A[i-1] 를 만족하는 가장 큰 j를 찾는다.(다음 순열은 순열을 하나의 수로 봤을 때 더 큰 수가 되어야 하므로, A[i-1]보다 큰 수를 앞으로 가져와야 한다. 작은 수를 앞으로 가져오는 것은 작은 수로 바꾸는 것이기 때문이다.) 3. A[i-1]과 A[j]를 swap한다. 4. A..

모든 방법의 수를 구하는 것이기 때문에 브루트포스로 푼다. 1,2,3 3가지 경우가 10번 가능하기 때문에 최대 3^10의 시간복잡도이다. 하지만 1을 10자리로 했을 때 최대의 경우의 수가 생기므로 3^10보다는 작을 것이다. 3^10도 1초의 제한시간 안에 가능하다. for문으로 풀려면 10개의 for문을 작성해야한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include int main() { int t; scanf("%d",&t); while (t--) { int ans = 0; int n; scanf("%d",&n); for (i..