문제 링크N과 M (8) N과 M 시리즈를 풀면서 뭔가 계속 날먹하고 있는 기분이다...큰 틀은 똑같고 부분부분 조건만 바꿔주면 되는 문제이다 보니...약간 공부를 안 하는(?) 느낌이다.아무튼 점수 올리고 개꿀. ㅎㅎ 문제 해석N개의 자연수 중 M개를 뽑는다. 이때 수는 중복으로 뽑아도 되지만 다른 수열과 순서는 같으면 안된다. 또한 내림차순 수열은 불가능하다. 접근백트래킹을 이용하여 풀었다.이때 중복은 허용하고, 내림차순 수열을 방지하기 위해 조건을 하나 붙였다.아까 뽑았던 숫자가 지금 뽑을 숫자보다 크면, 이 수열은 내림차순 수열이 되므로 pass 한다. 코드#include #include using namespace std;// N개 중에서, M개 뽑음int N, M;// n번째로 뽑은 수를 저장..
문제 링크15656 N과 M (7) 접근N개의 수 중에서 M개를 뽑아 만들 수 있는 수열을 모두 만드는 문제이다. 이때, 같은 수를 여러 번 골라도 되지만 순서는 달라야 한다. 따라서 백트래킹을 이용해 모든 경우의 수를 찾아 주었다. 그리고 사전순으로 출력해야 하기 때문에 사전에 배열을 sort 해 주었다. 코드#include #include using namespace std;// N개 중에서, M개 뽑음int N, M;// n번째로 뽑은 수를 저장int picked[10];// 숫자 모음int numbers[10];// k 번째로 저장할 수를 탐색 void Solve(int k){ if (k == M) { for (int i = 0; i > N >> M; for (int ..
문제 링크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]; // 사전순으..
1. std::fill특정 값으로 지정된 범위 전체를 채운다.std::fill(first, last, value); first, last: 값을 채울 범위의 시작과 끝을 나타내는 반복자.value: 채울 값. 2. std::fill_n반복자 시점에서 지정된 개수만큼 값을 채운다. 채울 요소의 개수가 명확히 정해져 있을 때 유용하다.std::fill_n(first, n, value); first: 채우기 시작할 반복자.n: 값을 채울 요소의 개수.value: 채울 값. 3. std::memset메모리 블록을 특정 바이트 값으로 채운다. 원시 배열이나 메모리 버퍼를 초기화하거나 메모리를 지울 때 사용한다. 메모리를 바이트 단위로만 다루기 때문에 조심히 사용해야 한다.std::memset(ptr, value,..
문제 링크1182 부분수열의 합 접근모든 경우의 수를 확인하는 백트래킹 문제이다. N개의 정수로 이루어진 수열이 있을 때, 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성해야 한다. 이때, 중요한 점은 크기가 양수인 부분 수열 중에서 경우의 수를 구해야 한다는 것이다. 이 말은, 공집합은 포함하지 않는다는 말이다. 이 문제는 중학교 때 배웠던 부분 집합 구하기 경우의 수 문제를 떠올려 쉽게 해결할 수 있다.만약 n1, n2, n3의 수 중 부분 수열을 만들어 합 S를 만들어야 한다면, n1을 선택하고, 안 하고, n2를 선택하고, 안 하고를 반복해서 선택한 숫자들의 합이 S가 되게 만들면 된다. 이때 주의해야 할 점은 S가 1 이상인 경우는 상관없으나 S가 0일 때 아무..
문제 링크N과 M (1) 우선 나는 백 트래킹을 연습하려는 의도로 이 문제를 풀어 보았다. 여기서 백 트래킹이란?현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘. 게임으로 비유하자면 현재 상태에서 가능한 모든 선택지를 다 플레이해 보는 방법이 백 트래킹이다. 백 트래킹은 BFS, DFS처럼 기본적인 알고리즘 구조가 잡혀 있으니 잘 익혀 둘 필요가 있다. 접근재귀 함수로 풀이해 보기로 했다. 1부터 n까지의 숫자 중 m개를 중복 없이 골라야 하므로 그 수들이 들어갈 배열(numbers)과 그 수를 이미 골랐는지 여부를 확인할 배열(isUsed)이 필요하다. 그리고 뽑은 수가 몇 번째 수인지는 변수 k를 두어 확인하였다. 알고리즘1. 1부터 n까지의 수에 대해 for문을 돈다. 아직 i..
문제 링크1992 쿼드트리접근1. 함수식void Solve(int x, int y, int n) // n은 데이터의 범위2. base conditionn == 1일때, 해당 데이터는 무조건 출력3. 재귀식void Solve(x, y, n){ // "("을 출력 if(//모두 같은 데이터인지 확인) { // 같은 데이터라면 // 데이터 출력 } else // 같은 데이터가 아니라면 { // "("을 출력 Solve(x, y, n / 2) ... // 4등분하고, 모든 부분마다 // 재귀 함수 시작 // ")"을 출력 }}코드#define _CRT_SECURE_NO_WARNING..
