알고리즘 유형 (백트래킹)

나는 C++ 를 사용해서 백준 알고리즘 문제를 푼다. 단계별로 풀기로 문제를 푸는데 생소하고 처음보는 유형의 알고리즘이 나오면 블로그에 정리하려고 한다.

 

지금껏 프로그래밍 언어를 통해 과제가 주어지면 복잡도, 메모리, 중복여부 이런 부분들을 고려하지않고 짰었다. 알고리즘문제를 풀게 되면 나처럼 프로그래밍을 하던 사람은 필시 막힐 수 밖에 없다. 단계별 풀기 단계에서 처음으로 막혔던 부분은 정렬 알고리즘에서 였고 새롭게 느낀점과 알고리즘을 종류별로 이 블로그에 포스팅 했었다. 단순히 과제를 구현하는 데에 그치지 않고 시간복잡도와 메모리를 고려해서 짜는 프로그램의 중요성을 알게 되었다. 

 

정렬 알고리즘 이후 개인적으로 막혔던 곳은 재귀-백트래킹-DP 단계이다. 재귀는 과제를 수행하면서도 많이 접해보아서 그렇게 어렵다고 생각치 않았다. 하지만 백트래킹이 첫 난관이었고 오늘은 백트래킹에 대해서 정리하려고 한다. 

 

백트래킹

백트래킹이란 모든 경우의 수를 탐색해보되, 특정 조건을 걸어 두고 그 조건을 만족하지 못하면 바로 그 전 단계로 돌아가서 진행하는 알고리즘을 의미한다. 모든 경우의 수를 탐색한다는 점에서 브루트포스와 비슷하다. 하지만 전 단계를 되돌아간다는 점에서 차이가 있는 듯 하다. 그러기에 브루트포스의 개념이 더 크다고 (백트래킹을 포함한다고) 볼 수 있다. 

 

백준 질문게시판에 있는 답변이다.

 

백트레킹의 문제 중 거의 모든 것이 특정 형태 (백트래킹의 형태)로 풀리기 때문에 백트래킹은 그 형태를 익히는 것이 중요하다. 재귀 구조를 띄는데, 재귀가 종료되는 조건문을 설정해주고 else 문에서 탐색해야하는 부분에 대해 반복문을 돌린다. 그리고 하나씩 차례로 선택하는데 다른 재귀가 호출되었을 때 앞선 재귀에서 해당 부분이 선택되었음을 알려주어야 하니까 또 다른 재귀를 호출하기 전에 used[i]를 true로 바꾸어서 선택되었음을 표시하고 재귀를 호출해야 한다. 재귀가 끝나면 다시 used[i]를 false 로 바꾸어 주어야 한다. 

 

이렇게 풀어서 쓰니까 이해가 잘 되지 않는데 문제를 통해 이해하는 것이 더 빠르다. 

 

 

구조로 표현하면 이런 형태다.

 

 

 

15649번: N과 M (1) (acmicpc.net)

15649번: N과 M (1)

백트래킹의 형태를 익힐 수 있는 좋은 문제이다. 핵심은 재귀를 쓰기 전에 used[i-1] = true로 바꾸어서 다음 재귀 때 해당 숫자가 포함되지 않도록 해주고 재귀가 끝난 뒤엔 다시 사용가능 하도록 하는 것이다. -> 백트래킹의 조건을 걸어 두고 만족하지 못하면 바로 전 단계로 돌아간다는 점이 중요하다.

 

 

 

void backTraking(int &N, int &M, int* arr, bool* used, int index){
    if(index == M) {
        for(int i =0;i<M;i++) cout << arr[i] << " ";
        cout << '\n';
    }
    else {
        for(int i=1;i<=N;i++){
            if(used[i-1]){
                arr[index] = i;
                used[i-1] = false;
                backTraking(N,M,arr,used,index+1);
                used[i-1] = true;
            }
        }
    }
}

 

 

 

해당 문제에 대한 백트래킹 구조이다. 밑의 문제들은 같은 형태이지만 숫자를 선택하는 조건이 달라져 조건이나 반복문 범위를 잘 조절해주면 되는 문제들이다. 

 

15650번: N과 M (2) (acmicpc.net)

15651번: N과 M (3) (acmicpc.net)

15652번: N과 M (4) (acmicpc.net)

 

 

 

 

밑의 문제들은 조금 더 활용한 문제들이다. 그치만 크게 백트래킹의 전형적인 형태를 벗어나진 않고 조건문 설정과 반복문 범위가 복잡해진 문제이다. 

 

---

9663번: N-Queen (acmicpc.net)

9663번: N-Queen

백트래킹으로 잘 짜서 했는데 시간초과가 떴다. 계속 고민하다가 도저히 모르겠어, 해답을 보았다. 내 문제는 크게 2가지였다. 

1. Queen이 놓인 공간을 저장하기 위해서 2차원 배열을 사용했다. -> 그냥 vector로 인덱스는 row, 값은 col로 할 수 있었다.

2. 대각선 요소들을 파악하는데 나는 반복문을 4번 돌렸는데 아마 여기서 시간을 많이 잡아 먹었을 것이다. 대각선 row,col 간의 관계를 쉽게 파악하는 방법이 있었다. . [백준 / BOJ] - 9663번 N-Queen C++ 풀이 :: Just Give Me The Code (tistory.com) 이 블로그 에서 정리를 잘 해주셨다.

 

 

 

14888번: 연산자 끼워넣기 (acmicpc.net)

14888번: 연산자 끼워넣기

나름 잘 푼 문제이다. 백트래킹의 본질을 잘 파악했고 문제에서 어떤 부분을 반복하고 되돌릴 때 바꾸어 주어야 하는지를 잘 파악해서 작성했다. 최대값과 최솟값의 초기값을 설정하는데 살짝 오해가 있어서 2번 정도 틀렸지만 간단히 해결했다. 

 

번외로 맞힌 사람들 코드를 봤는데 간결했다. 나는 연산자를 배열에 저장하고 sum도 변수에 저장해서 계속 재귀할 때마다 넘겨주어서 코드도 길어지고 함수를 호출할 때마다 인자가 많아서 오래 걸릴 우려가 있는데 다른 사람들은 그냥 바뀌는 값을 +1 해주어서 재귀를 호출함으로써 부담을 줄였고 코드도 간단했다. 47250230번 소스 코드 (acmicpc.net)

 

 

 

14889번: 스타트와 링크 (acmicpc.net)

14889번: 스타트와 링크

나름 잘 풀었다. 첫 제출에서 re/2를 왜 해야 하는지 이해하지 못했는데 다시 제출했을 땐 해결해서 제출했다. Getminus 함수에서 for문  안에서 살짝 오해가 있었다. 근데 다른 사람은 엄청 간단하게 풀었다. . 43480586번 소스 코드 (acmicpc.net) 나는 백트래킹을 풀 때 직관적으로 풀려고 하는데 다른 사람들은 문제의 원리를 파악하고 이용해서 수학적으로 코드를 줄이고 간단하게 만든다. 나도 직관적으로 짜는 것은 좋지만 문제의 본질을 파악해서 코드를 줄이는 것도 좋은 연습이 될 것이다.