백트래킹10 [백준 15654/javascript] N과 M (5) 자바스크립트로 풀어본 백트래킹 문제이다 조건의 배열을 미리 오름차순으로 정렬하면 0번째 부터 채워나가는 백트래킹 시에 사전순으로 나열 가능하다 자리수가 모두 채워 질때마다 수들을 임시배열에 넣고 join 을 통해 공백을 주어 매 경우마다 출력하게 하였다 https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net let input = []; const readline = require("readline").createInterface({ input.. 2022. 8. 23. [백준 9663/c++] N-Queen 백트래킹 심화 문제. 푸는 방법은 2가지가 자주 쓰인다 첫번째로, 조건을 판단할 함수를 만드는 방법 퀸은 위 아래 대각선에 영향을 주므로 퀸의 위치들을 배열에 넣은 후 배열을 돌며 놓을 수 있는지 여부를 판단할 함수를 만들어서 푸는 방법 퀸의 위치를 나타내는 배열을 나타낼 시 배열 내 요소의 인덱스를 열로, 요소의 값을 행으로 나타내서 2차원 배열이 아닌 1차원 배열만으로 퀸의 위치를 표현 가능하다 간단하지만, 배열을 돌며 여부를 체크해야 하므로, 시간복잡도가 추가로 O(n) 가 소모된다 두번째로, 함수대신 퀸이 영향력을 줄 수 있는 라인들을 배열로 저장해서 이전의 isused 체크처럼 사용하여 퀸을 놓을 수 있는지 체크하여 푸는 방법이다 배열의 크기를 40 으로 설정했는데, 가로가 n칸 일때 열의 인덱.. 2022. 8. 4. [백준 15652/c++] N과 M (4) 백준 백트래킹 4번째 문제 이전에 풀었던 중복 수 가능 + 오름차순 수열 인 문제이다 중복 가능이므로 isused 로 체크할 필요없고 오름차순 수열이어야 하므로 인자로 최저인 수를 전달해서 재귀 반복문에서의 증가할 i로 전달 해주자 https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include using namespace std; int n, m; int ar[10]; void bt(int k, int num) { if (k == m) { .. 2022. 8. 3. [백준 15651/c++] N과 M (3) 백트래킹의 3번째 기본문제. 선택할 수를 중복으로 여러번 사용하여도 되므로 이전의 풀었던 N과 M (1) https://tokkic.tistory.com/188 [백준 15649/c++] N과 M (1) 백트래킹을 사용하여 푸는 첫 문제이다 백트래킹이란 이전 결과를 보존하고 그 이전 결과를 기반으로 재귀를 사용하여 경우의 수를 찾는 방법이다 백트래킹은 브루트 포스 = 완전 탐색 과는 조 tokkic.tistory.com 문제에서 isused 의 조건을 풀어주고 관련 식만 삭제하면 성립하는 간단한 문제이다 https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 .. 2022. 8. 2. 이전 1 2 3 다음