오늘의 코테 문제

오늘의 코테문제는 유명한 N-Queen문제!
하지만 난 처음 풀어보는 거였따...

백트래킹은 아직도 부족한 부분이 너무 많다고 느끼는 부분이 많다.

우선 백준의 N과 M 을 6번까지 복습하면서 풀었다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>

using namespace std;

int n,m;
int arr[10];
bool isused[10];

void func(int k) {
    if(k==m) {
        for(int i=0; i<m; i++)cout << arr[i]<< " ";
        cout << "\n";
        return;
    }

    int st=1;
    if(k !=0) st = arr[k-1];

//i의 값은 index의 값을 의미한다. 즉 1부터 값이 일정하게 시작하면 1로 시작하면 되는거
//하지만 value[]라는 배열에 들어있는 값으로 조합하려고 할때는 시작점이 0으로 된다.
    for(int i=st; i<=n; i++) {
        if(!isused[i]) {
            arr[k] = i;//index이자 숫자의 순서
            isused[i] =1;
            func(k+1);
            isused[i] =0;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n>>m;
    func(0);

}

백트래킹 재귀함수의 일반적인 형태? 라고 생각하면 된다.
필요한 재귀 함수의 형태는 내가 위에 작성한 그림대로 필요한 재료를 골라서 구현하면 된다.

ex)

• 다음 depth에서 본인을 제외한다. -> isused[]를 사용한다.
• 중복 조합부분은 제외한다. -> 시작점 컨트롤 필요하다.

이분탐색

• 주어진 배열은 정렬되어 있어야한다.
• 무한 루프에 빠지지 않도록 한다.

약 3일간 풀어봤던 문제지만 아직 익숙하지 않은 개념이라 자주 반복해서 풀어봐야하는 문제이다.
가볍게 정렬해서 값을 뽑아내는건 편하게 할 수 있는 정도지만 upper값이랑 lower값을 구하는 것이 아직은 익숙하지 않다. (구할 순 있는데 굉장히 효율성 떨어지는 방법으로 구함)

내일도 할 일이 너무나도 많다... 이력서 다시 수정하고 고쳐보기
java로 익숙하지 않은 compare함수 구현해서 정렬하는 방법 복습하기, 재귀함수 복습하기, 이분탐색 복습하기, DP강의 듣기 ㅠ
얼른얼른 열심히 따라갈 수 있기를 바랄뿐

하루 깨작깨짝CS공부도 잊지 않기...