코딩성장스토리

https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net 이 문제를 풀 때 브루트 포스로 next_permutation함수를 쓰면 20!이기 때문에 2초라는 시간을 아득히 넘는다. 즉 이 문제는 브루트포스로 푸는 것이 아니다. 순열의 수는 그 원소 값을 보면 된다. 예시를 들자 3 5 1 4 2 라는 순열이 있다. 그러면 이 순열이 몇 번쨰 인지는 1 x x x x 4! 2 x x x x 4! 3 1 2 4 5 로 4!*2..

순열 함수 next_permutation 이 있고 이를 구현해보겠다. 일단 순열을 구할려면 1.a[i-1]=i이면서 a[j]>a[i-1]를 만족하는 가장 큰 j를 찾는다. 3.a[i-1]과 a[j]를 스왑 한다. 4.a[i]부터 순열을 뒤집는다. 예를 들어 7 2 3 6 5 4 1 이 있다. 여기서 1번 과정을 거치면 7 2 3 6 5 4 1 3이 가장 큰 i가 된다.그리고 2번 과정을 거치면 7 2 3 6 5 4 1 4가 가장 큰 j가 된다. 그리고 스왑하면 7 2 4 6 5 3 1 이 되고 여기서 4번 과정을 거치면 7 2 4 1 3 5 6 가 되면서 7 2 3 6 5 4 1 의 다음 순열이 된다. 코드를 보자 #include using namespace std; void swap(int &a,int..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 이 문제를 순열로 풀었는데 여기서 궁금했던게 해결이 되었다. next_permuation이라는 순열 함수를 쓸 때 1,1,2,2,2 와 같이 같은 수가 있을 떄 어떻게 작동되는가인데 올바르게 작동 되는 것이다. 1 1 2 2 2 1 2 1 2 2 등등 처럼 순서대로 간다. 그래서 이 문제를 풀 때 비교배열 n개의 수에서 6개만 1을 넣고 나머지 0을 넣었다. 그리고 비교배열에 1이 들었..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 이 문제는 일단 주어진 수의 범위가 10까지이고 모든 순서를 따지면 10팩토리얼 이다. 즉 브루트 포스(완전 탐색)이 가능하다 0이 나오면 갈 수 없는 것이므로 이 조건만 주의하며 모든 순열 돌며 최솟값을 구하면 된다. 코드를 보자 #include #include #include using namespace std; int main(){ int n; c..