코딩 레시피

Algorithms/Backtracking 검색 결과

해당 글 9건

[프로그래머스] 후보키 (C++)

후보키(Level 2) 문제 전체 문제 보기 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 접근법 이번 문제는 하나 이상의 속성을 선택하여 만들 수 있는 후보키의 개수를 구하는 문제입니다. 하나 이상의 속성을 선택하기 위해서는 백트레킹을 활용하여 재귀적으로 접근할 수 있습니다. 재귀적으로 선택된 속성의 조합이 문제에서 주어진 "유일성"과 "최소성"을 만족하는지 검증하여 후보키로 확정 지..

Algorithms/Backtracking 2021. 11. 20. 18:09

[BOJ 17142] 연구소3 (C++)

연구소3 Gold 4 문제 전체 문제 보기 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 접근법 이번문제는 전체 바이러스 개수(M개 이하) 중 최적의 M개의 바이러스를 선택했을 때 전파시간의 최솟값을 구하는 문제입니다. 임의의 M개를 뽑았을 때 전파시간을 계산하기 위해서는 BFS를 사용할 수 있으며, M개를 뽑기 위해서는 백트레킹을 통한 완전 탐색을 사용할 수 있습니다. 최대 바이러스 개수는 10개이므로 최악의 경우에도 \(_{10}\mathrm{C}_{5} = 252\) 가지의 경우의 수가 존재합니다. 따라서 최악의..

Algorithms/Backtracking 2021. 11. 10. 14:17

[BOJ 15686] 치킨 배달(C++)

치킨 배달(Gold 5) 문제 전체 문제 보기 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 접근법 이번 문제는 입력받은 전체 치킨집들 중에서 M개를 선택했을 때 도시의 치킨 거리가 가장 작게 되도록 만들어야 합니다. 이번 문제는 선택 가능한 모든 경우의 수를 탐색하면서 도시의 치킨 거리를 계산하여 풀 수 있는 문제입니다. M의 최대값은 13이며, 치킨집의 개수는 M이상 13 이하입니다. 따라서 최악의 경우에는 13개의 치킨 집 중 6개 혹은 7개를 선택하는 경우 가장 오래 걸립니다. (..

Algorithms/Backtracking 2021. 11. 3. 12:25

[BOJ 14888] 연산자 끼워넣기(C++)

연산자 끼워넣기(Silver 1) 문제 전체 문제 보기 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 접근법 이번 문제는 연산자가 삽입될 수 있는 모든 위치를 완전탐색하여 풀 수 있습니다. 연산자는 수와 수 사이에만 삽입될 수 있기 때문에 연산자가 삽입될 수 있는 위치는 N - 1 개이며 N은 최대 11입니다. 그리고 각 연산자는 사용할 수 있는 개수가 한정적입니다. 그래서 모든 경우의 수를 계산하더라도 \(4^{10} = 1,048,576\) 보다 훨씬..

Algorithms/Backtracking 2021. 10. 2. 14:02