백트래킹3 [BOJ] 3980. 선발 명단(Python) / DFS, Backtracking 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 11개의 포지션에 11명의 선수를 채웠을 때, 능력치의 합의 최댓값을 구하는 문제. # 42분 소요. (한 번에 통과, PyPy3 제출 기준 시간 1위 달성했다!) 사용 알고리즘 : Backtracking, DFS 순열 구하기 무난하게 순열 구하는 dfs 재귀로 접근해 가지치기하여 가짓 수를 쳐냈다. 원래 dfs 순열로는 11개 자리에 11명을 각각 다른 자리에 배치하는 경우의 수가 39,916,800개가 나오는데, Backtracking으로 가지치기하면 경우의 수가 1824개로 확연히 준다. perm 함.. 2021. 4. 15. [BOJ] 1941. 소문난 칠공주(Python) / DFS, Backtracking 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 전형적인 Backtracking 문제이다. 내가 매우 취약한 알고리즘.. 이번 주는 백트래킹/DFS 문제를 파보자 사용 알고리즘 : Backtracking / DFS 재귀로 조합 구현 조합으로 접근해야한다는 것을 생각도 하지 못했다. 가짓 수가 너무 많을 것이라 생각했는데, 백트래킹으로 Y를 4번 이상 만났다면 return하여 가지치기로 어느정도 거를 수 있다. dfs 함수로 25개 칸에서 7개 칸을 선택하는 조합을 구현한다. 이 때, 7개 숫자를 리스트로 담는데,.. 2021. 4. 13. [Algorithm] 백트래킹(Backtracking)이란? Backtracking은 제약조건 만족문제에서 해를 찾는 방법이다. 개념 : 여러가지 경우의 수가 있는 문제에서 특정조건을 만족하는 찾는 데 있어, 조건을 탐색하다가 어느 순간 조건이 맞지 않는 것으로 판단되면 그 쪽의 경우의 수는 더이상 체크하지 않고 다른 경우의 수를 체크하는 것. 일종의 문제 푸는 전략으로, 알고리즘은 아니다. 고려할 수 있는 경우의 수를 상태공간트리로 표현 DFS 방식으로 후보군 확인 상태공간트리 탐색하며 제약조건을 만족하지 않으면 해당 부분에서 파생될 수 있는 모든 경우의 수를 더이상 보지 않는다. 이후 해의 후보가 될 만한 곳을 바로 넘어가서 탐색을 이어간다. 이를 통해 체크해야 하는 조건의 수를 확연히 줄이므로 계산량을 줄일 수 있는 기법이다. Promising : 조건 검사.. 2021. 3. 9. 이전 1 다음
