문제 링크15655 N과 M (6) 접근N개의 자연수 중, M개의 자연수를 뽑아 수열을 만든다. 이때 그 수열은 중복되는 수 조합이 아니어야 하고, 사전순으로 출력되어야 한다. N과 M(5) 문제 풀이에서 조건 하나를 추가하여 해결하였다. (1, 7)이라는 수열이 있을 때 (7, 1)이라는 수열은 뽑히면 안 되므로 처음 뽑은 수보다 나중에 뽑은 수가 작으면 무효시키는 조건문을 추가했다. 코드#include #include using namespace std;// N개 중에서, M개 뽑음int N, M;// n번째로 뽑은 수를 저장int picked[10];// 숫자 모음int numbers[10];// 방문했는지bool isUsed[10];// k 번째로 저장할 수를 탐색 void Solve(int k)..
문제 링크15654 N과 M (5) 접근기존 N과 M (1) 문제에서 입력을 받는 케이스만 추가된 문제이다. 이때 중요한 점은 사전순으로 수열을 출력해야 하므로, 배열에 수들을 입력받고 정렬해 주었다. 코드#include #include using namespace std;// N개 중에서, M개 뽑음int N, M;// n번째로 뽑은 수를 저장int picked[10];// 숫자 모음int numbers[10];// 방문했는지bool isUsed[10];// k 번째로 저장할 수를 탐색 void Solve(int k){ if (k == M) { for (int i = 0; i > N >> M; for (int i = 0; i > numbers[i]; // 사전순으..
문제 링크15652 N과 M (4) 접근N개의 숫자 중에서 M개를 뽑아 수열을 만든다. 이때 중복해서 뽑아도 되지만 뽑은 수열이 내림차순이 되어서는 안 된다.내림차순이 되어선 안된다는 조건만이 N과 M (3) 문제에서 추가됐을 뿐이어서 N과 M (3) 문제 풀이에서 비내림차순 조건을 추가하여 풀었다. 코드#include using namespace std;// N개 중에서, M개 뽑음int N, M;// n번째로 뽑은 수를 저장int numbers[10];// k 번째로 저장할 수를 탐색 void Solve(int k){ if (k == M) { for (int i = 0; i 0 && numbers[k - 1] > i + 1) continue; numbers[k] ..
문제 링크15651 N과 M (3) 접근기존 N과 M 문제와 달리 중복으로 뽑는 것을 허용하는 문제이다. 따라서 백트래킹을 실시할 때 중복 체크를 하지 않았다. 코드#include using namespace std;// N개 중에서, M개 뽑음int N, M;// n번째로 뽑은 수를 저장int numbers[10];// k 번째로 저장할 수를 탐색 void Solve(int k){ if (k == M) { for (int i = 0; i > N >> M; Solve(0); return 0;}
문제 링크15650 N과 M (2) 접근N과 M (1) 문제를 조금 변형한 문제이다. 조건이 하나 추가되었다.고른 수열은 오름차순이어야 한다.예를 들어, (1, 2), (1, 3)은 되지만 (2, 1), (3, 1)은 안 된다. 이미 뽑은 숫자가 다음 뽑을 숫자보다 크면 백트래킹을 진행하지 못하게 막아 주면 된다. 따라서 백트래킹을 하기 전에 다음 조건문을 추가하여 오름차순인 수열만 얻을 수 있게끔 필터링했다. // 오름차순인 수열만을 출력하기 위해 // (1, 2) (1, 3) 은 되지만 (3, 1), (2, 1)은 안 되므로 // 이미 뽑은 숫자가 다음 뽑을 숫자보다 크면 진행하지 못하도록 했다. if (numberCount > 0 && numbers..
문제 링크9663 N-Queen접근역시 백트래킹 연습 문제이다. 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제인데, 중요한 건 나는 체스의 룰을 모른다. 그래서 퀸의 이동 규칙을 찾아봤다. 퀸의 이동 규칙 퀸은 상하좌우 맨 끝까지 이동할 수 있다.퀸은 4방향 대각선 맨 끝까지 이동할 수 있다.문제 적용N x N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이므로, 일단 같은 행에는 1개의 퀸만이 위치할 수 있다는 걸 알 수 있다. 이렇게 규칙을 찾아보면, 퀸은 다른 퀸과 같은 행에 있을 수 없다. 퀸은 다른 퀸과 같은 열에 있을 수 없다. 좌측 하단과 우측 상단을 연결하는 대각선이 있고 (x, y)에 퀸이 있을 때 x + y의 값이 n이라고 하자.그렇다면 다른 ..
문제 링크N과 M (1) 우선 나는 백 트래킹을 연습하려는 의도로 이 문제를 풀어 보았다. 여기서 백 트래킹이란?현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘. 게임으로 비유하자면 현재 상태에서 가능한 모든 선택지를 다 플레이해 보는 방법이 백 트래킹이다. 백 트래킹은 BFS, DFS처럼 기본적인 알고리즘 구조가 잡혀 있으니 잘 익혀 둘 필요가 있다. 접근재귀 함수로 풀이해 보기로 했다. 1부터 n까지의 숫자 중 m개를 중복 없이 골라야 하므로 그 수들이 들어갈 배열(numbers)과 그 수를 이미 골랐는지 여부를 확인할 배열(isUsed)이 필요하다. 그리고 뽑은 수가 몇 번째 수인지는 변수 k를 두어 확인하였다. 알고리즘1. 1부터 n까지의 수에 대해 for문을 돈다. 아직 i..
