'pruning' 태그의 글 목록

제가 개최한 대회 중에, 2번 문제는 브루트 포스, 백 트래킹을 이용한 문제였습니다. 코딩 테스트에서 상당히 자주 보이고, 반드시 풀고 넘어가야 하는 유형이므로, 2번에 출제하였습니다. 보통, 백트래킹이라고 하면, dfs를 돌리면서 처리하는 경우가 일반적입니다. 이 문제도 예외는 아닙니다. 문제는 중복 방문하는 것을 어떻게 처리할 것인지였습니다. 예를 들어, (1, 1)에 고구마가 있는데, (1, 1)을 3번 방문했다면, (1, 1)에 있는 고구마를 한 번 먹은 것이지, 세 번 먹은 것이 아니기 때문입니다. 여기서 언급하는 문제는 실버1에서 골드5 정도로 그렇게 어렵지 않습니다. 그렇기에 더 자세히 분석해 보도록 하겠습니다. 가장 먼저 생각할 수 있는 방법은, 중복된 데이터를 제거하는 방법이 있습니다. ..