알고리즘/백트래킹 썸네일형 리스트형 백준 2961번: 도영이가 만든 맛있는 음식 (JAVA) 문제 해석 재료를 최소 한개 이상 사용하여 음식을 만든다. 각 재료는 신맛 성분 S와 쓴맛 성분 B를 가지고 있다. 재료를 여러개 사용하면 최종 신맛은 사용한 재료들의 신맛의 곱이고 최종 쓴맛은 사용한 재료들의 쓴맛의 합이다. 음식의 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 것이 목표이다. 알고리즘 재귀적으로 호출하여 조합할 수 있는 재료의 경우를 모두 탐색하고 신맛과 쓴맛의 차이 최솟값을 갱신한다. 코드 더보기 백준 6603번: 로또 (JAVA) 문제 해석 로또는 1부터 49까지의 수 중 6개의 수로 구성된다. 로또 번호를 선택하는 전략은 1부터 49까지의 수 중 k개의 수를 골라 만든 집합 S에서 번호를 선택하는 것이다. 이 때 번호를 선택시 오름차순이 되도록 선택한다. 알고리즘 백트래킹을 통해 집합 S에서 오름차순으로 만들 수 있는 6개의 수 조합을 모두 찾아낸다. 코드 더보기 백준 18429번: 근손실 (JAVA) <백트래킹 알고리즘 활용> 문제 해석 1일차부터 N일차 동안 매일 K만큼 감소하고 매일 키트 사용을 통해 500 이상을 계속 유지해야 한다. 항상 500 이상으로 유지하기 위해 키트 사용 순서를 바꾼다. 알고리즘 예시 표를 보면 모든 경우에 대해 체크할 필요가 없다. 예시에서는 1번을 먼저 사용할 시 1일차부터 조건을 만족할 수가 없어 이후에 선택하는 키트 순서는 의미가 없다. 따라서 (X일차에 주어지는 중량 + 키트 사용 중량 - K)가 500 이상인 경우에만 다음 날짜에 사용할 키트를 고르는 과정을 재귀적으로 반복하면 가능한 경우의 수를 구할 수 있다. 코드 더보기 백준 14501번: 퇴사 (JAVA) <백트래킹 알고리즘 응용> 문제 해석 백준이는 N일까지만 상담일을 할 수 있다. 상담일은 최소 하루가 소요되고 당일을 포함한다. N과 각 날마다의 상담 소요시간, 페이가 입력으로 주어질 때 최대 수익을 얻을 수 있는 스케줄을 짜 최대 수익을 출력한다. 알고리즘 상담일을 하는 것을 함수로 뒀을 때 퇴사 전까지 계속해서 일을 해야하므로 재귀적으로 상담일 함수를 호출한다. 위의 예시에서 1일에 일을 한다면 2일, 3일은 일을 못하므로 그때의 데이터는 사용할 필요가 없다. 상담 소요시간 T를 이용하여 일하지 못하게 되는 날은 건너 뛰어서 상담일 함수를 재호출하고 퇴사날을 넘어가는 것에 대해서만 조건을 달아주면 된다. 1일에 첫 근무를 시작하는 것부터 하여 2일에 첫 근무, 3일에 첫 근무 ... N일에 첫 근무할 때의 경우들을 모두 조사.. 더보기 백준 15650: N과 M(2) (JAVA) <백트래킹 알고리즘 응용> 문제 해석 이전에 백트래킹 알고리즘으로 푼 N과 M 문제에서 오름차순인 수열만 골라내는 조건이 추가된 문제이다. 알고리즘 이전에 사용한 백트래킹과 유사한 형태이지만 함수에 인자로 깊이 뿐만 아니라 시작 위치도 인자로 주어야할 필요가 있다. 코드 resolve 함수의 인자로 idx(시작 위치 지정)을 추가하였다. 재귀호출을 하는 반복문에서 i의 시작조건을 이전처럼 0이 아닌 idx로 지정하였고 재귀호출시 i+1을 idx 인자로 전달하여 본인보다 큰 숫자에 대해서만 탐색하게 하였다. 1부터 시작하기에 초기 idx는 1로 한다. -> resolve(1, 0) N이 4이고 M이 2인 경우 재귀호출을 하는 반복문 진행 순서를 보면 1차 호출: i=1 / result[0]=1 / resolve(2, 1) 2차 호출.. 더보기 백준 15649번: N과 M(1) (JAVA) <백트래킹 알고리즘> 문제 해석 N이 입력값으로 주어질 때 1부터 N까지의 수에서 중복없이 M개씩 골라 나올 수 있는 모든 경우를 구한다. 오름차순으로 출력해야 한다. 출력할 숫자들을 담을 배열이 필요할 것으로 보인다. 알고리즘 기준이 되는 숫자를 선택했을 때 나올 수 있는 경우를 모두 찾을 수 있어야 한다. N이 4이고 M이 2인 경우 기준이 되는 수가 1일 때 (1, 2) / (1, 3) / (1, 4) 가 출력되어야 하는데 일일이 증가시켜주며 인덱스를 변경해줄 수 없기 때문에 방문여부를 기록하고 재귀적으로 수행해야할 필요를 느꼈다. 백트래킹 알고리즘 이 방식은 백트래킹 알고리즘이다. 백트래킹 알고리즘은 브루트포스 알고리즘과 달리 모든 가능성을 다 뒤져보는 것이 아닌 가능성이 있는 경우만 찾는 알고리즘이다. 노드 방문 기.. 더보기 이전 1 다음
