본문 바로가기

Backtracking3

[백준] 1799. 비숍 문제 풀이 처음에 생각했던 방법은 완전 탐색을 통해 최대 수를 찾는 방법이었다. 중간에 가지치기를 통해 시간을 줄일 수 있겠지만 n의 최대값이 100이고 (모든 점에 대해 놓는 경우/ 놓지 않는 경우) * (놓을 수 있는지 판단하기 위해 양 대각선을 탐색하는 경우)를 하게 되면 O(2^n * n)이기 때문에 시간초과가 발생할 것 같아서 다른 방법을 생각해봤다. 생각한 방법은 N-Queens에서 모든 행렬을 저장하지 않고 해당 idx에는 하나의 값만 올 수 있도록 한다면 시간을 줄일 수 있다는 생각을 했고 데이터를 어떻게 묶어야 할지 고민을 해봤다. N-Queens에서 queen은 가로,세로를 갈 수 있었고 이로 인해 하나의 행에 퀸을 놓을 경우에는 같은 행에는 퀀이 존재하지 못하는 성질을 이용했었다. 이.. 2021. 3. 7.

[백준] 1987. 알파벳 풀이 모든 경우의 수를 DFS로 탐색하며 이전에 방문한 알파벳인 경우 가지치기를 진행하엿다. 이 때 이전 방문 노드를 확인하는 방법으로 초기에는 ArrayList를 사용했지만 시간초과가 발생하였고 이에 대한 이유가 ArrayList의 remove 과정에서 O(N)의 시간복잡도가 발생했기 때문이라고 판단하였다. 그래서 이전 방문 알파벳을 유지하는 방식을 StringBuilder를 사용하였고 마지막 인덱스를 삭제함으로써 시간 초과를 해결하였다. 하지만 이 방법도 너무 느려서 이를 확인하는 방법으로 비트마스킹을 사용하였고 모든 경우에 distance를 비교하는 것이 아니라 유망하지 않은 경우에만 distance를 비교하도록 개선하였다. 비트마스킹으로는 현재 알파벳 - 'A'를 해줌으로써 포함 여부를 확인하였다.. 2021. 2. 19.

[백준] 3109. 빵집 풀이 DFS를 통해 탐색을 진행할 때 최대값을 찾는 경우는 대부분 모든 경우의 수를 확인해야 하기 때문에 유망하지 않은 경우 가지치기하는 백트래킹 방법을 사용할 수 없다. 하지만 이 문제는 시작 점은 가장 위에서부터 연결할 수 있는 경우에는 연결하는 경우가 최선의 방법이 되는 그리디한 접근 방식을 사용하였고 이를 통해 유망하지 않은 경우 탐색을 종료하는 경우 되돌아가는 백트래킹 방식을 사용하였다. 첫번쨰 열의 1번쨰 행부터 탐색을 진행하고, 만약 C번째 행에 도착했다면 이번 시작 위치에서의 탐색을 종료한다. 다음 위치도 동일하게 진행하는데 만약 실패한다고 하더라도 방문한 위치에 대한 체크를 되돌리지 않는다. 왜냐하면 해당 위치에서 파이프를 완성하지 못했다고 하더라도 뒤 선택지에서 해당 방향은 동일하게 실.. 2021. 2. 19.

이전 1 다음

티스토리툴바