목록백트래킹 (7)

쉬운 프로그래밍

[알고리즘] 백준 14889 스타트와 링크 - JAVA

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 총원 4명이 축구를 한다고 예를 들면 (1, 2), (3,4)와 같이 팀 순서쌍을 어떤 방식으로 만드냐가 문제를 푸는데 핵심문제이다. visited[] boolean 배열을 만들어서 true인 인덱스끼리 한 팀, false인 인덱스끼리 한 팀이라는 아이디어로 문제를 해결하였다. 백트래킹 방식을 적용하여 모든 경우에 대한 순서쌍을 만들었다. 코드 설명은 주석에 자세히 써놓았다. import java.io.BufferedReader; ..
알고리즘/백트래킹 2021. 2. 6. 21:29
[알고리즘] 백준 14888 연산자 끼워넣기 - JAVA

www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 해결 방법 자체는 떠올리기 쉬웠다. 아래 그림과 같이 연산자의 개수를 통해 유망한 노드인지 가지치며 깊이우선탐색을 진행하며 depth가 꽉 차면 최대값과 최소값을 판단하고 반환하는 방식을 떠올렸다. 자세한 설명은 코드에 주석을 적어놨다. import java.io.BufferedReader; import java.io.IOException; impor..
알고리즘/백트래킹 2021. 2. 5. 22:31
[알고리즘] 백준 9663 N-Queen

www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BOJ_9663 { static int n; static int[] map; static int count = 0; public static void main(String[] args) throws IOException { BufferedR..
알고리즘/백트래킹 2021. 1. 10. 15:09
[알고리즘] 백준 6603 로또

www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_6603 { static int k; static int[] map; static boolean[] visited; static int[] arr..
알고리즘/백트래킹 2021. 1. 9. 15:28
[알고리즘] 백준 15652 N과 M (4)

www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_15642 { static int n; static int m; static int[] arr; static boolean[] visited; static..
알고리즘/백트래킹 2021. 1. 7. 20:59
[알고리즘] 백준 15650 N과 M (2)

www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_15650 { static int n; static int m; static int[] arr; static boolean[] visited; static..
알고리즘/백트래킹 2021. 1. 6. 21:27
[알고리즘] 백준 15649 N과 M (1)

www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_15649 { static int n; static int m; static boolean[] visited; static int[] arr; static..
알고리즘/백트래킹 2021. 1. 6. 20:53
Prev 1 Next