[이론][완전탐색][N자리 K진수] Chapter 3

완전탐색의 첫 번째 알고리즘 백트래킹 문제를 풀어보겠습니다.

---

N자리 K진수 : 문제

N-Queen

코드는 여기에서 확인할 수 있습니다.

arr[0]=1을 map의 0번째 row에는 1번째 col에 퀸이 위치함을 의미합니다. 이 때 각 퀸들이 같은 row/col에는 올 수 없기 때문에 visited[]를 사용합니다. 그리고 isPossible()함수는 직접 8방향으로 시뮬레이션을 하느 것이 아니라, 좌표값의 차이를 통해서 서로의 대각선에 위치했는지 판별합니다.

차이를 최대로

코드는 여기에서 확인할 수 있습니다.

이 문제는 기본적인 N자리 K진수 풀이로 가능합니다. N자리 K진수의 선택한다/선택하지 않는다의 풀이는 선택되는 index가 오름차순인 경우만 고려하기 때문에 적용할 수 없는 문제입니다.

도영이가 만든 맛있는 음식

코드는 여기에서 확인할 수 있습니다.

특정 음식에 대해서는 그 음식을 사용하든 사용하지 않든 두 가지 경우만 존재합니다. 그런데 음식을 1개 이상 사용하는 경우 모두에 대해서 ans를 갱신해야합니다. recur(int depth)에서 depth는 ‘depth번째 선택을 해야하는 경우’임을 생각해서 depth != 0 인 경우를 제외하고는 모두 갱신을 해줍니다.

오름차순으로 재료를 선택하기 때문에 가장 마지막 재료를 선택한 경우에는 choice를 사용한 덕분에 더이상 진행하지않고 recur이 종료됩니다.

퇴사

코드는 여기에서 확인할 수 있습니다.

1. 백트레킹 1번 개념으로만 풀어여하는 문제가 있을 수 있다.
2. 이 문제의 경우 특정 날짜의 일을 한다 안한다의 개념이 확실하므로 1번 개념으로만 풀 수 있다.
3. 백트레킹 0번 개념으로 풀이를 하면 어떤 일들을 할지 선택하고, 선택한 일들을 실제로 수행할 수 있는지를 판단하는 isCorrect()를 짜야한다. 그런데 이 과정이 너무 복잡하다. 그래서 1번 개념으로 접근한다.
4. depth를 이전에 고른 일이 끝나고 depth번째일을 시작할지 말지 판단해야한다.로 생각하는 것이 중요하다.
5. 예를 들어 0번째 날짜의 일이 2일이 걸리면, 0번째 날짜의 일은 0일쨰와 1일째에 수행하고 2일쨰의 일을 할지말지 선택해야한다.
6. 딱 N일 째에 일이 끝나는 경우만 생각해서 답을 갱신한다. N일을 넘으면 불가능한 일을 받아서 한 경우라서 제외한다.

가르침

코드는 여기에서 확인할 수 있습니다.

백트레킹 1번 개념으로 풀이을 하였습니다. 특정 알파벳을 선택할지/말지 결정해서 k개만큼 선택할 때까지 recur를 진행합니다. 이 떄 오름차순으로 선택하는 것으로 가정하고, antatica에 포함된 5개의 알파벳을 선택해야하는데 선택하지 않은 경우에는 recur()를 중단합니다. 만약 abcedf의 경우 꼭 들어가야하는 a와 c는 들어갔지만 t i c는 포함되지 않았기 때문에 isCorrect()method에서 한 번 더 걸러줍니다.