알고리즘/백트래킹(Backtraking) (2) 썸네일형 리스트형 [알고리즘] N-퀸(Queen) 문제 - 코딩밥상 N-Queen 문제 이는 백트래킹 알고리즘을 사용할 수 있는 대표적인 문제중 하나로, 체스에서 여덟 방향으로 모두 움직일 수 있는 퀸 8개를 8*8크기의 체스판 안에 서로 공격할 수 없도록 배치하는 모든 경우를 구하는 문제입니다. 체스판의 칸이 모두 64개이고 그 중 8개의 퀸을 배치할 수 있으므로 후보 해의 수는 총 64C8(조합)개 입니다. 약 44억개가 조금 넘는 후보 해 중에서 실제 해는 92개 뿐입니다. 처음 8개의 퀸 문제는 8*8크기의 체스판을 염두에 두고 제안됐지만 다른 크기의 체스판으로 문제를 축소 및 확장할 수 있기때문에 N개의 퀸 문제라고 불리게 된 것입니다. 이 문제는 백트래킹 알고리즘으로 후보해를 대거 줄여 연산 횟수를 줄일 수 있습니다. 첫 번째 행에 차례대로 퀸을 하나씩 놓았을.. [알고리즘] 백트래킹(Backtracking) - 코딩밥상 백트래킹(Backtraking)이란? 백트래킹은 여러 후보 중 특정 조건을 충족시키는 모든 해를 찾는 알고리즘입니다. DP나 그리디(Greedy) 알고리즘이 풀 수 있는 문제의 유형이 따로 있듯이 백트래킹 역시 그렇습니다. 백트래킹이 다루는 문제들은 해가 하나 이상 존재합니다. 이때 그 해들을 일컬어 '모든 해'라고 합니다. 해를 구하는 과정에서 해가 될 수 있는 가능성을 가진 부분해의 조합을 '후보 해'라고 합니다. 백트래킹이 다루는 문제들은 후보해의 수가 굉장히 많다는 특징이 있습니다. 이 중에서 해가 될 조건을 만족시키는 '진짜 해'를 효율적으로 찾는 것이 백트래킹의 목적입니다. 백트래킹이 다루는 문제들은 다양한 후보해를 갖고 있기때문에 대부분 트리의 형태로 표현할 수 있습니다. 따라서 해를 찾는.. 이전 1 다음