가지치기 검색 결과

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

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

안녕하세요. 조경완입니다. 백준에서 문제들을 풀다 보면, 소수인팰린드롬 문제도 보셨으리라 생각합니다. 어렵지 않은 문제이지만, Loop를 칠 때, 어떻게 치면 좋은지 생각해 볼 수 있는 문제인 듯 싶어서 가지고 오게 되었습니다. 문제는 아래와 같습니다. 최악의 경우에는 a가 5, b가 1억이니 만만치 않은 문제인 듯 싶습니다. 그런데, 314명이 풀어냈습니다. 1억까지를 에라스토스테네스의 체로 거른다고 해도 힘들고, 그렇다고 팰린드롬을 로그 복잡도로 판별하고 루트 복잡도로 소수임을 판별하자니. 그것도 힘듭니다. 어떻게 하면 좋을까요? 아이디어는 의외로 단순합니다. 일례로 99823419가 소수인지 판단하는 것은 쉽지 않습니다. 그런데, 팰린드롬인지는 어떻게 판정하면 되나요? 그냥 뒤에서 부터 본 문자랑 ..
자료알고/알고리즘 2020. 11. 12. 02:52