백트래킹 검색 결과

해당 글 4건

[BOJ 9663] N-Queen(C++)

N-Queen (Gold 5) 문제 전체 문제 보기 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근법 N-Queen 문제는 Backtracking을 활용하여 풀 수 있습니다. Backtracking의 알고리즘은 항상 다음과 같은 패턴으로 구현할 수 있습니다. 탈출 조건 확인 반복문을 활용한 모든 브랜치 탐색 조건에 만족하는 브랜치만 재귀적으로 탐색 N-Queen 문제 또한 위의 방식으로 풀이할 수 있습니다. 일반적인 Backtracking 알고리즘보다 유효성 검사 부분이 까다롭고 가지치기를 효과적으로 하기 위한 접근법이..
Algorithms/Backtracking 2021. 9. 20. 19:06

[BOJ 15654] N과 M (5) (C++)

N과 M(5) Silver 3 문제 전체 문제 보기 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 접근법 이 문제는 BOJ 15649 번 문제와 유사합니다. 그래서 접근법은 BOJ 15649 문제 풀이를 참고해 주세요. 전체 구현 #include #include #include #define endl '\n' using namespace std; void Backtracking(const vector& arr, vector& temp, vector& visited, const int M) { if (..
Algorithms/Backtracking 2021. 9. 18. 13:04

[프로그래머스]메뉴 리뉴얼 (C++ / 2021 KAKAO BLIND)

메뉴 리뉴얼 (Level 2) 문제 전체 문제 보기 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 접근법 이 문제는 Brute force 방식으로 모든 조합을 계산해서 풀어야 하는 문제입니다. order 하나의 최대 길이가 10으로 충분히 작기 때문에 모든 경우의 수를 따져볼 수 있습니다. 모든 조합의 경우의 수를 만들기 위해서는 백트래킹을 사용할 수 있습니다. (백트래킹에 대한 이해가 필요하다면 이 글을 참고해주세요) 백트래킹을 사용하여 문제를 풀기 위해서 아래와 같이 길이별로 해시 테이블을 11개 생성했습..
Algorithms/Backtracking 2021. 9. 11. 23:56

[BOJ 15649] N과 M (1) (C++)

N과 M(1) (Silver 3) 문제 전체 문제 보기 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 접근법 이 문제는 1 ~ N까지의 자연수 M개를 조합하여서 나올 수 있는 모든 수열을 만드는 문제로 백트래킹으로 풀 수 있는 문제입니다. 백트레킹은 모든 조합을 시도해서 문제의 해를 찾는 알고리즘입니다. 백트레킹의 가장 큰 장점은 불필요한 자식 노드(경우의 수 및 조합) 탐색을 배제함으로 계산시간을 단축할 수 있다는 점입니다. 백트레킹은 재귀적으로 구현할 수 있습니다. 재귀적으로 구현하기 때문에 코드는 간결..
Algorithms/Backtracking 2021. 9. 11. 23:39