컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제 해결 알고리즘 a ~ z 까지 K개를 백트래킹으로 무작위로 골라 배열에 표시한다. 이 때, anta tica가 항상 문자열 앞 뒤에 들어있으므로 a, n, t, i, c는 처음부터 저장해준다. 그러고 문자열의 4번째부터 끝에서 4번째까지 배열에 있는 문자열인지 아닌지 검사하고, 모두 있다면 표시해준다. 여기서 pos 파라미터를 적절히 써줘야 시간초과를 피할 수 있다. 소스 코드 #in..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 알고리즘 대표적인 백트래킹 문제 아래의 링크에 푸는 방법이 있습니다. https://kimmessi.tistory.com/86?category=871925 [알고리즘] 백트래킹 - n-Queens, 해밀턴회로 되추적 (Back Tracking) 틀린 답에 접근했을 때, 틀리기 전의 상태로 돌아가서 다른 선택을 하는 알고리즘 만약 답이 나올 때까지가 시간 복잡도가 엄청 복잡하게 나올 수도 있지만, 이 답..

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 문제 해결 알고리즘 비숍의 특성을 이해해야하는 문제. 체스판에 검은색 타일의 비숍과 흰색 타일의 비숍은 서로 공격할 수 없다. 그렇기 때문에 검은색 비숍과 흰색 비숍을 따로 구분해서 깊이 우선 탐색을 진행해야할 필요가 있다. 만약에 그냥 색깔 상관없이 모든 타일의 비숍을 한 번에 깊이 우선탐색을 진행한다면 시간초과가 난다. 그렇게 한다면 시간 복잡도는 $O(2^{(N*N)})$ 이지만 위의 방식대로 색깔 ..

https://www.acmicpc.net/problem/2239 https://www.acmicpc.net/problem/2580 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 해결 알고리즘 이 두개의 문제가 결이 같아서 같이 정리한다. 우선 입력을 받..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 해결 알고리즘 백트래킹, 깊이 우선 탐색 문제 (0, 0)부터 DFS를 해주는데 이 때, 문제에서 나온 것처럼 중복되는 알파벳을 체크해주는 배열과, 지나온 자리들을 체크해주는 배열을 각각 두고 탐색하는데 시간을 아낀다. 나머지는 그냥 전형적인 백트래킹이다. 소스 코드 #include using namespace std; int R, C; char arr[21][21]; bool vis..

https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net 문제 해결 알고리즘 전형적인 백트래킹 문제인데 거기에 인접해 있는 모든 문자가 같지 않은 문자열이라는 조건만 추가해준다. 소스 코드 #include using namespace std; int arr[26]; int result = 0; int N; bool isTrue(string str){ bool flag = true; for(int i=0;i str; N = str.size(); for(int ..

https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 문제 해결 알고리즘 string으로 숫자를 입력 받아 앞자리 수와 비교 한 후에 long long으로 배열에 입력해 백트래킹이 끝나면 배열을 정렬해 그에 해당하는 감소하는 숫자를 출력한다. 소스 코드 #include using namespace std; int N; vector v; void dfs(string str){ if(str != "") { long long n = stol..

분기한정법이란? 분기한정 설계전략은 상태공간트리를 사용해 문제를 푼다는 사실이 되추적과 매우 비슷하다. 차이점으로 분기한정법은 (1) 트리 횡단방법에 구애받지 않고, (2) 최적화 문제를 푸는데만 쓰인다. 분기한정 알고리즘은 어떤 마디가 유망한지를 결정하기 위해서 그 마디에서 수(한계값)를 계산한다. 이 수는 그 마디 아래로 확장해 구할 수 있는 해답의 한계(bound)를 나타낸다. 그 한계값이 그때까지 찾은 최고 해답값보다 더 좋지 않으면 그 마디는 유망하지 않다. 최적값은 문제에 따라서 최대값이 될 수도 있고, 최소값이 될 수도 있으므로 여기서 "좋다"란 문제에 따라서 더 작다는 의미도 되고 더 크다는 의미도 된다. https://kimmessi.tistory.com/74?category=871925..

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 문제 해결 알고리즘 DFS를 활용해 백트래킹 기법으로 모든 도시들을 탐색한 후에 가장 적은 비용을 출력해준다. 소스 코드 #include using namespace std; int N; int W[11][11]; bool visited[11]; int result = 99999999; bool visitedCheck(){ for(int i=2;i N;..

www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 알고리즘 문제 해결 이 문제는 매우 간단하게 c++에 있는 라이브러리인 next_permutation 함수를 이용하면 쉽게 풀 수 있는 문제였다. 이 문제에서 중요한 건 중복된 출력이 있으면 안되므로 팩토리얼 함수를 따로 만들어서 그만큼을 건너뛰고 출력한 것을 볼 수 있다. 그리고 또 M까지의 숫자만 출력하는 것도 포인트이다. 소스 코드 #include using namespace std; int pac(in..