문제 링크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..
문제 링크1182 부분수열의 합 접근모든 경우의 수를 확인하는 백트래킹 문제이다. N개의 정수로 이루어진 수열이 있을 때, 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성해야 한다. 이때, 중요한 점은 크기가 양수인 부분 수열 중에서 경우의 수를 구해야 한다는 것이다. 이 말은, 공집합은 포함하지 않는다는 말이다. 이 문제는 중학교 때 배웠던 부분 집합 구하기 경우의 수 문제를 떠올려 쉽게 해결할 수 있다.만약 n1, n2, n3의 수 중 부분 수열을 만들어 합 S를 만들어야 한다면, n1을 선택하고, 안 하고, n2를 선택하고, 안 하고를 반복해서 선택한 숫자들의 합이 S가 되게 만들면 된다. 이때 주의해야 할 점은 S가 1 이상인 경우는 상관없으나 S가 0일 때 아무..
CLR(Common Language Runtime)CLR은 소프트웨어 실행 환경 또는 런타임 환경에 가깝다. 운영 체제와 실행되는 프로그램 사이에서 중간 계층 역할을 수행하는 시스템 소프트웨어의 일종이다. 운영 체제에서 애플리케이션이 실행될 수 있도록 돕는 "해석기"이자 "관리자"이며 이를 통해 .NET 애플리케이션이 하드웨어나 운영 체제와 직접적으로 상호작용하지 않고도 실행될 수 있게 한다.자세히는 .NET Framework 및 .NET Core에서 동작하는 실행 환경(runtime)을 의미하며 CLR은 C#, VB.NET, F# 등 다양한 .NET 언어로 작성된 프로그램이 실행될 수 있도록 지원하는 핵심적인 역할을 한다. CLR의 주요 역할과 기능1. 코드 실행C# 소스 코드는 컴파일되면 IL (I..
문제 링크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..
문제 링크2447 별 찍기 - 10 접근처음에는 단순히 별을 print 하려고 생각했으나 계속 실패하자 나에게 익숙한 2차원 공백 배열에 원소를 집어 넣는 방식으로 해결했다. 27 * 27 사각형을 9개로 쪼개 봤을 때, 가운데만 비어 있으므로 이걸 그대로 코드로 옮겨 주었다. 재귀 함수void PrintStars(int n, int x, int y) base conditionn을 계속 3으로 나누다가 1이 되면 별을 찍기로 했다. 재귀 식 for (int i = 0; i x, y 좌표를 3의 배수씩 옮겨 다시 별을 찍도록 했다. 이때 n * n 사각형 기준 가운데가 비어있기 때문에 조건식을 추가하여 건너뛰게 만들었다. 전체 코드#define _CRT_SECURE_NO_WARNINGS#include ..
문제 링크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..
문제 링크1780 종이의 개수접근재귀 함수라고 생각하고 너무 겁먹고 들어갔더니 처음엔 정말 안 풀렸다. 끙끙 앓다가 그냥 생각나는대로 로직을 추상적으로 짜서 도전해 보았다.알고리즘1. 현재 범위 내의 종이가 다 같은 종류의 종이인지 확인한다.1-1. 만약 같은 종류라면 해당하는 종이의 카운트를 증가시킨다.1-2. 만약 다른 종류라면 9등분해서 똑같이 1을 반복한다.의사 코드#include #include using namespace std;vector> papers;int N;int paper[3];void Solve(int x, int y, int n){ if (/*만약 같은 종류의 종이라면*/) { paper[/*종이 인덱스*/]++; return; } ..
