분류 전체보기

백준 15652 N과 M(4) c++ // 백트래킹, n H m 중복(?)조합

https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 문제해결 start부분을 arr[k-1]로 바꾸면 된다. 기존 조합 : st=arr[k-1]+1 2. 전체코드 #include using namespace std; int n,m; int arr[10]; int isused[10]; //현재까지 k개의 수를 선택함. void go(int k) { if (k==m){ for (int i = 0; i < m; ++i) { cout m; go(0..

백준 15651 N과 M(3) // 백트래킹, n ∏m 중복순열

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 중복순열 코드 : 순열코드에서 방문부분을 주석하면 된다! 2. 전체코드 #include using namespace std; int n,m; int arr[10]; int isused[10]; //현재까지 k개의 수를 선택함. void go(int k) { if (k==m){ for (int i = 0; i < m; ++i) { cout m; go(0); }

백준 15650 N과 M(2) c++ // n C m, 조합

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 전체코드 #include using namespace std; int n,m; int arr[10]; int isused[10]; //현재까지 k개의 수를 선택함. void go(int k) { if (k==m){ for (int i = 0; i m; go(0); }

백준 1182 부분수열의 합 c++ // 백트래킹

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1. 해결과정 함수정의 : (현재깊이, 총합) 탈출조건(기저사례) : 깊이>=n 재귀식 : 현재값(arr[cur])을 더한다 / 안더한다 2. 전체코드 #include using namespace std; int n,s,ret; int arr[24]; //현재깊이, 총합 void go(int cur, int tot) { if (cur==n){ if (tot ==..

백준 9663 N-Queen c++ // 재귀, 백트래킹, 일반식도출, 백트래킹 시간복잡도

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 일반식도출 1.1 / 대각선인경우 규칙 : (1,0) (0,1) -> x+y의 값이 1로 동일하다! -> (0,1)에 이미 두고 (1,0)에 두려고 할경우 isused[1]이 true이기 때문에 continue된다! 1.2 \ 대각선인경우 규칙 : (0,0) (1,1) -> x-y의 값이 0로 동일하다! -> (0,0)에 이미 두고 (1,1)에 두려고 할경우 isused[0]이 true이기 때문에 conti..

프로그래머스 전력망을 둘로 나누기 c++ // int dfs 자식수세기

https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. int dfs 자식수세기 지역변수로 ret=1 ret+=dfs(next) return ret 하면된다. int dfs(int node){ visited[node]=1; int ret=1; for(int next=0;next

백준 2448 별찍기-11 c++ // 재귀함수, 분할정복법

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 0. 함수정의 크기, 시작좌표에 별을 그리는 함수 //좌표기준 : 좌측위 기준 void go(int n, int y, int x) { 1. 세로 : n / 가로 : 2n-1 이다. ex) n==3일때 생각 2. 기저사례 n==3일때, 더이상 쪼갤수 없다. 좌표로 별을 그리면 된다. 3. 재귀식 go(12) == go(6) go(6) go(6) 3개로 분할 가능하다. 검은사각형 == 파란사각형3개로 분할한다. 검은사각형의 시작 좌표를 x,y라고 할때,..

백준 2448 별찍기-10 c++ // 재귀함수, 기저사례는 간단히, 2차원배열 fill 방법

https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 1. 2차원배열 fill 방법 //2차원 배열 초기화 방법 for (int i = 0; i < n; ++i) { fill(a[i], a[i] + n, ' '); } #include using namespace std; int n; char a[2500][2500]; //함수정의 : n만큼의 범위에 *-' ' 채워넣기 , 시작좌표 void go(int n, int y, i..