백트래킹 검색 결과

해당 글 4건
백트래킹과 가지치기에 대해서 예제 문제를 통해 알아봅시다.

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

구현, 백트래킹은 코딩 테스트에서 많이 나오는 단골 주제 중 하나입니다. 물론 tree dp나, segment tree하고 조합론을 아름답게 섞어놓은 dp도 나오기는 하지만. 중요도가 상대적으로 높지 않습니다. 그 말인 즉슨, 포기할 건 포기하더라도, 다른 사람들이 다 풀 수 있는 기본부터 챙겨 가자는 의미입니다. 그 기본 중 하나는 백트래킹입니다. 새로 추가된 문제인 18290번과 18292번 문제 NM과 K 시리즈를 보겠습니다. 개인적으로 적당히 난이도가 있으니, 입문 문제로는 좋은 듯 싶습니다. 문제는 아래와 같습니다. 조건을 잘 읽어보시고, 어떻게 풀어야 할 지 잘 생각해 보세요. 18292는 K 조건이 다른데요. K가 구간 [1, min(50,NM)]에 속하는 정수이다. 라는 것만 다릅니다. 그..
구현 2020. 1. 28. 17:03
quento 퍼즐 문제 : 백 트래킹으로 풀어봅시다.

안녕하세요. chogahui05입니다. 인성에서 100%의 확률로 떨어지다 보니 제 인성에 문제가 있는 듯 싶어요. 셀프 깍기는 밴이고요. 오늘은 좀 유명한 게임을 다뤄볼 것인데요. quento라고, n개의 숫자와 n-1개의 연산자를 조합해서 특정한 수 m을 만들어야 합니다. 이 때, 한 번 방문한 칸은 다시 방문할 수 없고, 인접한 칸으로만 이동이 가능합니다. 예를 들어 봅시다. 7 밑에 네모가 2개 있어요. 이는 수는 2개, 연산자는 하나를 사용 해야 한다는 이야기입니다. 그러면 (0,0)에서 출발해서 오른쪽으로 가면 될 거에요. 5 + 2 = 7이기 때문입니다. 이번에는 11을 만들어야 하는데요. 사용해야 하는 숫자의 갯수는 3개, 연산자는 2개입니다. 7+4도 답은 됩니다. 하지만, 사용한 숫자의..
구현 2019. 11. 2. 01:25
백트래킹 : 모든 경우를 탐색한다.

백준 사이트에 있는 구현 문제는, 대다수가 브루트 포스로 풀리는 경우가 많습니다. 코딩 테스트를 준비하시는 분들도 적지 않으실 거 같은데요. 그것들을 잘 풀기 위해서, 이론적인 지식 3~4편 정도만 올리고, 실전에 들어가도록 하겠습니다. 백트래킹 탐색은, 다음과 같은 알고리즘으로 동작합니다. 뭔가 복잡해 보이는데요. 제일 중요한 부분은, (1)번과 (3)번, (5)번이라고 할 수 있어요. 이 셋만 잘 작성하면 끝났다고 볼 수 있어요. 그런데, 아직 이해가 안 가는 부분이 많습니다. 들어올 수 있는 상태들은 대체 무엇을 의미할까요? 예를 들어, 스토쿠를 생각해 봅시다. 빈칸에 숫자를 넣어야 할 때, 1부터 9까지만 넣을 수 있어요. 즉, 우리가 빈 칸에 넣을 수 있는 숫자들의 집합은 {1, ... , 9}..
구현 2019. 9. 26. 20:07