알고리즘

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

[C++] 에라토스테네스의 체 , 소수판별을 위한 도구

에라토스테네스의 체는 소수판별을 하기 위한 간단하고도 강력한 방법입니다. 1,0과 영은 소수가 아니므로 2부터 판별을 시작합니다. 소수의 정의는 약수가 자기 자신과 1만을 가진 숫자입니다. 그러므로 2는 소수입니다. 하지만 2의 배수는 2를 약수로 갖기 시작하므로 소수의 조건에서 벗어나게 됩니다. 이러한 점을 이용해 빠르게 소수가 아닌 수를 false로 저장하는 방법입니다. int m[1001]; // 에라토스테네스의 체 배열 크기 지정 //2~999까지 소수판별을 하는 코드입니다. void eratos() { for(int i=2;i

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

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

[백준] 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문자열 사이에 문자를 넣을 수 없으..