개인사

리뷰SSAFY 백트래킹 시간에 배워서 풀었다. 싸피 짱! 문제 풀이DAT 배열을 총 세개 만들어 준다. col 기준, 우하향, 좌하향 대각선에 방문 체크를 하기 위함우하향, 좌하향 DAT의 index로 전달해 줄 값을 저장할 2차 배열 2개를 만들어 준다.우하향 배열은 우하향 대각선의 값이 같게, 좌하향 배열은 좌하향 대각선의 값이 같게 만들어준다. 값은 DAT의 범위 내에 있고, 각 대각선과 값이 겹치지 않는다면 상관 없다.row를 매개변수로 0부터 백트래킹을 시작한다. 만약 row가 n과 동일하다면 배치가 가능한 것이다. cnt를 1 더해준다.for문을 시작하고 0부터 n까지 순회를 돈다. 위에서 말했듯 행은 현재 재귀의 row로 받고 있다.현재 열에 놓을 수 있다면 (판별 조건을 통과했다면) 모든 ..

개요1. 중복 순열중복이 가능한 N개 중에서 R개를 선택하는 경우의 수(순서를 고려한다, 중복 조합)별다른 판별조건 없이 모든 수를 도출해 주면 된다.1 1 21 2 12 1 1 2. 순열서로 다른 N개 중에서 R개를  선택하는 경우의 수(순서를 고려한다, 중복인 경우는 선택하지 않는다.)DAT를 활용하여 이미 선택한 경우에는 선택하지 않도록(방문 여부 체크) 판별조건을 추가해 준다.1 2 31 3 22 3 1 3. 중복 조합중복이 가능한 N개 중에서 R개를 선택하는 경우의 수(순서를 고려하지 않는다.)중복이 가능하다 = 방문 처리를 하지 않는다.조합을 위해 현재 뽑는 순서가 2번째 이상일 경우 이전에 뽑았던 수보다 작을경우 선택하지 않는다. 라는 판별 조건을 추가해 준다.1 1 11 1 21 1 31 ..

개요백트래킹 : 재귀 호출 중 가망성이 있는지 여부를 판별하면서 진행하는 방식재귀를 통해 경우의 수를 모두 탐색하여 구하고자 하는 조건에 일치하는 경우를 모두 구할 수 있다.실행하고자 하는 하는 반복 횟수, 재귀를 빠져나올 기저 조건, 각 반복 횟수에 적용할 식을 잘 세우면 효율적으로 사용할 수 있다.  예제1. 조합을 선택하여 출력하기서로 다른 n개의 수에서 k개의 수로 이루어진 조합을 출력하기코드#include using namespace std;int n, k;int arr[100];int DAT[110];void bt(int index) { // 2. 기저 조건 if (index >= k) { for (int i = 0; i > n >> k; for (int i = 0; i > arr[i]; }..

개요함수란 무엇인가? 코드를 기능 단위로 묶어둔 것이다.return type funcname() { body}와 같은 형식을 가진다. 지역/전역/함수를 사용할때 어떤 메모리 영역에서 쓰이는지 잘 구분해야 한다. 재귀는 다시 돌아오다 라는 뜻으로 재귀 함수는 다시 돌아오는 함수이다. 즉 다시 실행되는 함수 (run / recall)재귀 함수는 자기 자신을 리턴 혹은 호출 하므로 종료 조건을 설정하지 않으면 원하는 의도가 나오지 않을 가능성이 매우 높다. (함수를 호출하는 것 자체가 메모리를 사용하는 것이므로 while처럼 무한루프에 빠지진 않을 것이다.)따라서 재귀 함수를 사용할 당시엔 종료 조건을 설정해 주어야 한다. 예제1. 무한 루프코드#include using namespace std;void he..