차곡차곡

https://www.acmicpc.net/problem/15686 아이디어치킨집의 개수 C개의 경우 C개의 치킨집 중 M개를 선택하는 모든 조합 : 1716개 조합각 조합에 대해 모든 집의 치킨 거리 계산(집의 개수 H, 치킨집 개수 M) : 최악의 경우 1300최악의 경우 O(1716⋅1300)≈2,230,800  즉 2.23×10^6 의 연산이 필요하기 때문에 브루투포스와 백트래킹을 활용해 모든 치킨집의 조합을 확인하며 계산하여 정답을 도출할 수 있다.  코드입력부N, M = map(int, input().split())city = [list(map(int, input().split())) for _ in range(N)]result = int(1e9)store = []house = []for i ..

https://www.acmicpc.net/problem/9663 해당 풀이는 Python 으로 제출시에도 시간초과가 발생하지 않습니다. 초기 아이디어처음에 문제를 풀 때는 2차원 배열을 사용하여 체스판을 표현한 후, 백트래킹을 이용해 각 칸에 퀸을 배치했다. 결과는 당연히 시간초과가 발생했다.N이 커질수록 백트래킹을 통해 모든 가능성을 탐색하는 과정에서 시간 복잡도가 급격히 증가하기 때문이다. 이를 해결하기 위해서 퀸의 이동 방식에 대해서 다시 생각해보면 아래와 같다. 퀸의  이동방식 퀸은 다음과 같은 방식으로 이동한다. 같은 행에 있는 퀸끼리는 서로 공격할 수 없으므로, 한 행에 하나의 퀸만 배치할 수 있다.퀸은 같은 열에 있는 다른 퀸과도 공격할 수 없으므로, 한 열에도 퀸은 하나만 배치되어야 한다..

백트래킹 재귀적으로 문제를 하나씩 풀어나가되 현재 재귀를 통해 확인 중인 상태(노드)가 제한 조건에 위배되는지 판단하고 위배되는 경우 해당 상태를 제외하고 다음 단계로 나아가는 방식이다. 해를 찾는 도중에 막히면 해당 상태로 더 탐색하지 않고 돌아가서 해를 찾아나가는 방식이다. 이때 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)이라고 한다. 모든 경우의 수를 체크하지 않게 되므로 시간을 단축할 수 있다. 유사한 알고리즘으로 DFS(깊이 우선 탐색)이 있다. DFS와 백트래킹의 차이는 DFS는 모든 경우의 수를 탐색하지만 백트래킹은 DFS와 다르게 백트래킹은 불필요한 탐색을 하지 않는다. 사용 문제 의사결정 문제 최적화 문제 열거 문제 핵심 아이디어 재귀 호출 : 문제를 해결하..