완전탐색

[백준] 1051번 숫자 정사각형 (C++)

https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 www.acmicpc.net * 입력받은 숫자들 중에서 4개의 꼭짓점이 모두 같은 정사각형 중에서 최대크기를 구하면 되는 문제입니다. 완전탐색 + 구현 + 몇몇의 조건 주의 처음에 n과 m으로 행과 열의 크기를 알려줍니다. 이때 행열의 크기를 알 수 있고, 행열안에서 최대크기를 가지는 정사각형 또한 구할 수 있습니다. 이 부분에서 저는 실수를 하였는데요. 코드와 예시를 통해 알아보겠습니다. for (int i = 1; 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문자열 사이에 문자를 넣을 수 없으..

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

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(..