Today I learned : 정처기, 토익

오늘 할 일

1. 바킹독 백트래킹
2. 프로그래머스 SQL
3. 토익 단어랑 LC, RC 테스트
4. 바킹독 시뮬레이션
5. 바킹독 재귀 워크북
6. 요세푸스 문제와 BFS 복습하기

일단 정처기를 먼저 슼 다 보고 프로그래머스 SQL이랑 바킹독 백트래킹 풀고 저녁에 스카 가서 토익만 조지기 그리고 집에 와서 바킹독 워크북

바킹독의 실전 알고리즘 : 백트래킹

알고리즘 설명

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 이라고 한다.

연습 문제 1 : N과 M

#include <bits/stdc++.h>
using namespace std;

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

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

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

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

내가 풀다가 안되겠어서 풀이 봤다. 이전 시간에 배운 재귀와도 살짝 닮아있다. 이 형태가 백트래킹의 전형적인 구조라고 한다.

여담

이번주부터 output 스터디에 산출물을 제출해야 한다. 나는 코테 위주로 산출물을 내야 하는데 이걸 어떻게 제출할까 하다가 commit 모아둔 PR 링크로 보내려고 한다. 그래서 간만에 브랜치 하나 만들고 PR 생성이 가능한 환경을 만들어주었다. 별 건 아니지만 PR과 merge를 적절히 사용할 수 있게 된 것이 좀 좋다(?)

회고

요즘 과하다!!! 과하게 할 일 잡고 과하게 못지킨다!!! 브레인 덤프를 좀 해야할듯 싶다. 그리고 브레인덤프만은 꼭 수기로 해야 효과가 있는 거 같다. A 일을 하더라도 갑자기 B 생각이 나다가 C 생각이 나고 챙길 게 많고 어디에도 집중을 못하는 모습이다. 정신 차리자.