5주차 내용정리 📌 백트래킹 백트래킹(Backtracking) 이란 ? 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다. 스무고개를 생각하면 쉽게 이해할 수 있음. ex ) 미로탐색 미로 탐색 문제같은 경우, 출발지부터 상,하,좌,우로 경우의 수를 dfs로 뻗어나가게 되는데, 더이상 진행할 수 없는 경우 다른 경우의 수로 해를 찾게된다. 📌 조합 nCr = n! / (n-r)! * r! 이 공식을 쓰지 않고 다음 공식을 쓴다. nCr = n-1Cr-1 + n-1Cr 위의 공식으로 예를들어 5명중에서 3명을 뽑는 경우의 수를 식으로 풀면 다음과 같다. 5C3 = 4C2 + 4C3 말로 풀어서 이야기 하면 5명중에서 3명을 뽑..

문제 링크 연구소 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net ❗ 풀이 방법 문제가 복잡한 만큼 로직을 나눠서 생각한 뒤, 구현해주는 것이 좋다. 문제를 읽어보면 다음의 세가지 로직이 필요한 것을 깨달을 수 있다. 벽을 세워보는 로직 바이러스를 퍼트리는 로직 안전영역의 갯수를 세는 로직 이렇게 정리가 되었다면, 다음은 위 세가지 로직을 어떻게 구현할 지 생각해보아야 한다. 벽을 세워보는 로직 모든 조합수를 따져보아야 하니 백트래킹으로 벽을 세워보고 허물어보고 하는식으로 하는것이 적절하지 않을까? 따라서 벽을 3개까지 세..

문제 링크 순열 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static int count; static String answer; static char[] arr; static boolean[] visited; static boolean flag; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { St..

문제 링크 로또 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static int k; static int[] arr; static boolean[] visited; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true) { k ..

문제 링크 N과 M 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static StringBuilder sb = new StringBuilder(); static int n; static int m; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); solution(); Sy..

문제 링크 N-Queen 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ❗ 풀이 방법 대표적인 백트래킹 문제이다. 처음에 퀸의 위치를 1차원 배열에 기록하면서 백트래킹하는 아이디어를 떠올리지 못하여 2차원 배열의 체스판을 만든 뒤 모든 칸에 대하여 퀸을 놓아본 다음 퀸을 놓은 위치와 공격할 수 있는 위치를 방문처리하고, 카운팅한 다음 방문처리를 풀어주는 굉장히 수고스러운 로직을 구현하였는데 다른 사람의 풀이를 보고 해당 아이디어를 베껴와서 다시 풀었더니 쉽게 풀렸다.. private static int[] arr; priv..