순열

[백준] 10819번 차이를 최대로 , 순열문제

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 입력받은 값을 오름차순 정렬한 후, 순열로 나열해 모든 경우를 탐색하며 조건에 맞는 합이 가장큰 값을 출력해주면 된다. 하지만 처음 접근을 숫자를 하나씩 바꿔보며 문제에 주어진 조건에서의 합이 최대인 경우에 swap을 해주는 경우로 생각했다. 모든 test case를 커버할 수 없어서 최대합이 나오지 않았다. 풀이 #include #include #include #include using namespace st..

[백준] 16945 매직스퀘어로 변경하기 (순열을 이용한 풀이)

처음 접근 인접한 숫자를 좌우상하로 바꾸고 바꾼 행렬에 대해서 매직 스퀘어인지 아닌지 체크를 하려고 했다. 하지만 매직퀘어의 경우로 숫자를 바꿔주기 위해선 최소의 숫자를 최소의 경로를 바꿔야하는데 이러한 경우의 수를 체크하기가 무척 번거로운 접근이 되었다. 다른 접근 (풀이) 3행3열의 2차원 배열로 접근하는 것이 아닌, 1차원 벡터로 입력을 받고 매직 스퀘어의 성질을 이용한다. 매직스퀘어는 모든 원소가 중복이 없는 경우이다. 그리고 별도의 매직스퀘어 함수를 만들어서 (1차원 이지만 2차원적 위치로 생각) 입력받은 스퀘어 값과 비교하고 최소 움직임 값(문제에서 말한 숫자를 바꾼 차이 값)을 모두 더해서 최솟값을 구하면 된다. 즉 {1,2,3...9} 모든 순열을 돌리면서 매직스퀘어인지 아닌지를 구별하고,..

[C++] permutation을 이용한 조합과 순열 활용

완전탐색에 많이 이용되는 조합과 순열을 알아보려고 합니다. !! C++ 의 algorithm 헤더파일에 있는 next_permutation prev_permutation 을 이용해서 출력하고 활용하는 방법까지 알아보려고 합니다. 먼저 기본적인 순열 출력인 next_permutation 함수를 사용해볼게요. 순열로 출력할 원소들은 오름차순으로 정렬되어있어야 합니다 ! vector v{1,2,3,4}; -> OK vector v{1,3,10,4}; -> NO C++의 sort함수를 활용하면 permutation을 사용할때 좋겠죠? (tip: C++ sort 함수는 퀵소트 방식으로 구현되어 있어요~) vector v{1,2,3}; do{ for(auto it = v.begin();it != v.end();it..