Algorithm

백준 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..

백준 1992 쿼드트리 c++ // 재귀함수, 재귀시작-끝에 괄호추가하는방법

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 1. 괄호추가하는방법 재귀식 앞뒤로 (, )를 추가하면된다!!!! //시작할때 괄호열어 ret += "("; go(half, y, x); go(half, y, x+half); go(half, y+half, x); go(half, y+half, x+half); //종료할때 괄호닫어 ret += ")"; 2. 내 코드 #include using namespace std; int n, a[..

백준 2630 색종이 만들기 c++ // 재귀함수 , 일반식만들기

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 1. 내 코드 #include using namespace std; int n,ret1,ret2, a[150][150]; //시작좌표~끝좌표(시작좌표+n)까지 돌면서 모두같은지 검사 bool all_same(int n, int y, int x) { int first = a[y][x]; for (int i = y; i < y + n; ++i) { for (int j = x..

백준 1780 종이의 개수 c++ // 재귀함수, 일반식도출

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 1. 내 정답코드 #include using namespace std; int n,ret1,ret2,ret3, a[2200][2200]; //시작좌표~끝좌표(시작좌표+n)까지 돌면서 모두같은지 검사 bool all_same(int n, int y, int x) { int first = a[y][x]; for (int i = y; i < y + n; ++i) { for (int j = x..

백준 17478 재귀함수가 뭔가요? c++ // 재귀함수 callback은 재귀호출뒤에쓰면된다.

https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net #include using namespace std; int n; void print(const char* str, int stk) { for (int i = 0; i < stk; ++i) { cout