C++

[백준] 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..

[백준] 1120 문자열 - 완전탐색

www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 문제만 이해하면 쉽게 풀 수 있는 완탐 문제 길이가 작은 문자열 A 가 문자열 B에 위치했을때, 가장 많이 중첩된 문자의 갯수를 구하면 바로 문제 해결! 문자열 앞뒤로 문자를 추가 할 수 있어서, 길이가 차이나는 만큼은 문자의 차이 없이 원하는 문자로 채울 수 있다. 따라서 A 문자열이 B문자열에 문자가 가장 많이 중첩되는 곳을 찾고, A문자열 사이에 문자를 넣을 수 없으..

[백준] 일곱난쟁이 완전탐색

www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 기초적인 완전탐색 문제 7개를 선택해서 100이되는 경우를 찾는 것 보다, 전체 합을 구하고 2개 숫자를 빼서 100이 되는 조건을 찾고 출력하면 된다. #include using namespace std; int main() { vector v; int im; int sum = 0; for (int i = 1; i > im; v.push_back(im); sum += im; } sort(v.begin(), v.end(..