일희이비

우선 나는 N과 M 시리즈를 다 풀면서 백트레킹을 마스터 해보겠다.. 근데 이문제는 너무 간단해서 왜 3번인지 모르겠다 차라리 얘를 1번으로 두지 일단 문제를 봐보자우선 이번에는, 1부터 N까지 M개를 고르는데 같은 수를 여러번 골라도되고 오름차순도 아니다. 즉, 4 2 가 들어오면 1 1, 1 2, 1 3, 1 4, 2 1, .... 이런식으로 다 출력하면 된다. 이를 고려해서 코드를 짜보자#include using namespace std;int N, M;int arr[9];void backtrack(int depth) { if (depth == M) { for (int i = 0; i > N >> M; backtrack(0); return 0;}우선, 어차피 다 출력하..

오늘은 저번에 이어서 N과 M 두번째 문제를 풀어보겠다. 이 역시도 백트레킹을 쓸 것이다 N과 M(1)과 비슷하지만, 다른 점을 생각해보면 오름차순이어야 된다 즉, (1)에서는 1 2 2 1이 가능했지만 이 문제에선 2 1은 취급할 수 없다이를 고려해서 코드를 짜보자#include using namespace std;int N, M;int arr[9]; // 선택한 숫자를 저장할 배열bool visited[9]; // 방문 여부 체크void backtrack(int depth, int start) { if (depth == M) { // M개의 숫자를 선택했으면 출력 for (int i = 0; i > N >> M; backtrack(0, 1); return 0;}오름차..

우선 완전탐색이란 무엇인가 부터 알아봤다. 완전탐색이란? 모든 경우의 수를 다 따져가며 찾는 방식이라고 한다. 즉 어떤 답을 찾기 위해 n번의 시도를 해야된다면, 그 n번을 다 훑어서 맞는지 아닌지 찾는 느낌이다. 그래서 시간복잡도는 O(n)이다. 그래서 오래걸리는 편이기 때문에, 시간제한을 보고 가능한지 판단해야된다고 한다. 예를들어, 시간제한이 1초가 걸려있다. 1초엔 1억번의 계산만 가능하므로, 만약 10억번의 연산이 필요한 문제라면 완전탐색 알고리즘을 쓸 경우 시간오버가 된다한다. 그래서 문제를 풀 땐, 시간 복잡도를 계산하고 이를 기반으로 완전탐색이 가능한지 판단해야된다!\ 백트레킹이란? 모든 경우의 수를 탐색하다 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을..