본문 바로가기

백트래킹6

14889. 스타트와 링크 사람은 총 N명, 최대 20명 이를 순열로 늘어 놓아서 앞에는 스타트팀, 뒤에는 링크팀으로 하면 중복계산도 상당히 많고, 총 경우의 수는 20! = 상당히 큰 수이다 >>>>>>>>>>>> 1억 당연히 시간초과가 난다. 문제를 풀면서 자연스럽게 생각할 수 있는 것은 사실 조합이다. 20C10 는 10! 보다 작을 것이라는 것을 예측할 수 있는데 실제로 그 결과는 10!(3백만)보다 훨씬 작다. 18만정도이다. 여기에 각 팀 스코어를 계산해야하는 시간이 (N/2) x (N/2) 이므로 100이라고 하면, 1800만 < 2초 안에 가능하다. 내가 맨 처음에 한 것은, 예를들어 1, 2, 3을 뽑았으면 총 1, 2, 3, 4, 5, 6 인 set에서 1, 2, 3을 뽑는 것이다. 즉 4, 5, 6을 만드는 것.. 2019. 9. 21.
[백트래킹] 백준 2580 스도쿠 백트래킹을 알고 있다면, 그대로 하면 풀린다! 원리는 간단하다, 모든 경우를 탐색하는 것인데 빈칸에 들어갈 수 있는 후보자를 찾은 뒤, 처음 후보자를 놓고, 다음 빈칸을 같은 방법으로 탐색한다. 그러다가 막히면(후보자가 없다거나) 다시 돌아오면 된다 (백트래킹!) 주의할 것은, 스페셜 져지문제인 만큼 답이되는 후보 제일 먼저 발견한 것을 찾으면, 바로 프로그램을 종료하면 된다. 헤더파일에 있는 exit(0)함수를 썼다. 후보자를 찾기 위해 가로세로를 탐색하고, 사각형을 탐색하는데 아이디어만 잘 내면 될 듯하다! #include #include #include #include using namespace std; int N = 9; int a[9][9]; int dx[] = {-1, 1, 0, 0}; in.. 2019. 9. 19.
[백준] 15651 N과 M (3) - 중복순열 15650 N과 M (2)를 풀었다면 정말 쉽게 풀리는 문제이다. #include int N, M; char a[15]; void repeated_permutation(int depth){ if (depth == M){ for (int i=0; i 2019. 9. 19.
[백준] N과 M (2) - 조합 조합. depth를 증가 시키는 것과, start를 하나 더 늘리는 것이 관건이다. 한 재귀함수가 호출되면, depth가 고정되어 있는 채로, start와 관련된 i 인덱스가 바뀌면서 다음 조합의 수를 채운다. #include int N, M; int a[9]; void combination(int depth, int start){ if (depth == M){ for (int i=0; i 2019. 9. 19.
[백준] 15649 N과 M (1) - 순열 단계별로 풀어보기에서 N과 M 시리즈 4개 중 개인적으로 가장 어렵다고 생각한다. 하지만, dfs와 백트래킹을 알고 있다면, N과 M문제 자체가 그렇게 어려운 편은 아니다. DFS는 그래프에서 깊이 우선 탐색을 의미하지만, 완전 탐색에서 주로 쓰이는 알고리즘으로, 모든 것을 다해보는 브루트포스 알고리즘과도 연관이 있다. 백트래킹은 여기에 조건을 더해주어, 원하는 경로로 탐색할 수 있게 도와주는 장치이다. 구현 코드 2개를 소개하고자 한다. #include using namespace std; int n, m; int a[8]; void swap_(int &a, int &b){ int temp = a; a = b; b = temp; } void rotateR(int start, int end){ int t.. 2019. 9. 19.
[백트래킹] 1987 알파벳 1. 알파벳 보드 b 생성 2. 알파벳 모음 alphabets 생성 - 이미 찾은 알파벳 확인용 3. 방향 설정 상 하 좌 우 dx = {-1, 1, 0, 0} dy = {0, 0, -1, 1} 이 보드의 (0, 0) 부터 시작해서, 상하좌우 매번 탐색하면서 - 보드의 바깥으로 가는 경우는 다시 돌아옴(백트랙). - 새로운 알파벳을 탐색했으면 기록하고, 다음 경로 탐색. - 이미 기록된 알파벳을 탐색했으면 백트랙. ex) 2 4 CAAB ADCB 이와 같은 알파벳 보드에서, 재귀함수가 어떻게 진행되는지 보자. C : 알파벳 체크. 1 상 : 없음, 돌아옴 2 하 : A 체크 2-1 상 : C가 이미 체크 되어있음, 돌아옴 2-2 하 : 없음, 돌아옴 2-3 좌 : 없음, 돌아옴 2-4 우 : D 체크 2.. 2019. 6. 27.
728x90