본문 바로가기

백트래킹

 (5)
[백준] 1759 암호 만들기 (JAVA) https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 이 문제는 기존의 백트래킹문제를 풀어보았다면 쉽게 풀리는 문제였다. 기존의 백트래킹의 문제(N과M문제 시리즈들)들과는 다른점이라면 이번 1759번 암호만들기는 숫자가 아닌 문자가 주어졌다는 것이다. 하지만 그 뿐일뿐 숫자가 문자로 바뀌었다는것을 제외하고서는 전부 동일하다 사전식으로 출력을 한다든지 아니면 어떠한 조건이 있는 점이 말이다. 알고리즘의 개요는 다음과 같다 우선 입력값으로 L C값을 입..
[백준] 14889 스타트와 링크 (JAVA) https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 이 문제를 처음 보았을때는 개인적으로는 실버3 같이 느껴지지 않았다. 나는 처음에 사람들의 집중하기보다는 점수들의 조합에 집중해서 어려웠던것 같다. 알고리즘의 개요는 다음과 같다. 모든 사람들의 조합을 구하고 각 조합당 낼수있는 시너지들의 총합을 구하고 이를 스타트와 링크로 나누너 계산해 가장 작은값을 출력하면 된다. 자세한것은 코드를 보면서 이해가 될것이다. import java.io.BufferedReader..
[백준] 15650 N과 M (2) (JAVA) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 이 문제는 저번에 풀었던 N과 M (1)문제에서 오름차순이 추가되었다는것을 제외하고는 전부 동일하다. 그래도 다시한번 더 설명을 해놓을테니 혹시라도 이러한 문제를 처음풀거나 여전히 어려운 사람들은 보기 바란다. 이 문제는 DFS와 비슷한 백트래킹을 사용한다. 여기서 백트래킹이 무엇이냐 하면 유망하지않은 노드는 선택하지 않는다는것이다. 예를 들어 이번에 포스팅하는 문제를 예시로 들어 설명을 ..
[백준] 14888 연산자 끼워넣기 (JAVA) https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 이 문제는 저번과 마찬가지로 백트래킹에 대해 알고있다면 어떠하게 풀지 감이 오는 문제였다. 나는 처음 이문제를 접하였을때 매경우 최적의 경우를 찾아내는 방법이 있는줄 알고 고민하였으나 브루트 포스라는 카테고리를 보고 그냥 전부 돌리기로 생각했다. 여기서 변수는 숫자의 개수를 나타내는 N, 최대값 MAX 최소값 MIN, 숫자들을 담을 ar..
[백준] 15649 N과M(1) (JAVA) 풀이 이 문제는 예전에 풀었던 N-queen과 동일한 백트래킹문제이다. 실버3의 낮은 난이도에 속하는데 백트랙킹의 기본 원리를 알면 쉽게 풀수있다. 백트래킹은 DFS와도 비슷한데 다른점이라면 DFS와는 다르게 해당 노드가 유망하지 않으면 취하지 않는다는 것이라는것이다. 이 문제에서 위의 말을 적용하면 만약 앞서 수열에서 이미 선태한 수가 있다면 선택한 수는 제외하고 순회를 한다는 것이다. 그리 어렵지 않은 코드니 보면 쉽게 이해할수있을듯 하다. 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.util.Str..

티스토리툴바