패스트캠퍼스 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 강의를 정리한 내용
완전탐색 - 기초
완전 탐색(Brute Force)
- 문제 해결을 위해 모든 경우를 전부 탐색하는 방법
- 그 중에서도 백 트래킹(Back-Tracking)을 통해야 하는 상황 해결
- 모든 코테 문제에서 기본적으로 접근해봐야 한다. 많은 연습이 필요하다.
장점 : 부분점수 얻기 좋음
단점 : 시간복잡도가 일반적으로 높음
완전탐색 종류
- N개 중 중복을 허용해서
- N개 중 중복 없이
- M개를 순서있게 나열
- M개를 고르기
(1 ,3) / (1, 4) / (2, 3) / (2, 4) - 4가지
완전 탐색은 함수 정의에서 50%는 먹고 들어간다.
// Recurrence Function (재귀 함수)
// 만약 M개를 전부 고름 => 조건에 맞는 탐색을 한 가지 성공한 것
// 아직 M개를 고르지 않음 => k번째부터 M번째 원소를 조건에 맞게 고르는 방법을 시도
static void rec_func(int k) { }
public static void main(String[] args) {
input();
// 1번째 원소부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 탐색해줘
rec_func(1);
System.out.println(sb.totring());
}완전탐색 복잡도
(1+3) 방법
N개 중 중복을 허용하여 M개를 순서있게 나열
- 15651번 문제
예를 들어, N = 4, M = 3이라고 하자. 그러면 (_ _ _) 3칸이 있고 각각 1~4까지 들어갈 수 있다.
- 시간 복잡도 계산
4 * 4 * 4일 것이다.- 일반화하면 O(NM)이다. 문제에서 N과 M의 최대가 7이었으니 77 하면 대략 82만이다. 완탐 써도 될듯?
- 강의 코드
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static void input(){
FastReader scan = new FastReader();
N = scan.nextInt();
M = scan.nextInt();
// M번째 까지 받지만, M+1 (= 다 찬 경우) 확인을 위해
selected = new int[M + 1];
}
static int N, M;
static int[] selected;
// Recurrence Function (재귀 함수)
// 만약 M개를 전부 고름 => 조건에 맞는 탐색을 한 가지 선공한 것
// 아직 M개를 고르지 않음 => k번째부터 M번째 원소를 조건에 맞게 고르는 방법을 시도
static void rec_func(int k) {
if (k == M + 1) { // 다 골랐다 ! // selected[1...M] 배열이 새롭게 탐색된 결과
for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
sb.append('\n');
} else {
for (int cand = 1; cand <= N; cand++) {
selected[k] = cand;
// k + 1 번째부터 ~ M 번을 모두 탐색하는 일을 해야하는 상황
rec_func(k + 1);
// 끝나면 더이상 기록할 필요 없으니까
selected[k] = 0;
}
}
}
public static void main(String[] args) {
input();
// 1 번째 원소부터 M 번째 원소를 조건에 맞는 모든 방법을 찾아줘
rec_func(1);
System.out.println(sb.toString());
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws FileNotFoundException {
br = new BufferedReader(new FileReader(new File(s)));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}- 줄인 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] selected;
static StringBuilder sb = new StringBuilder();
static void recv_func(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
sb.append('\n');
} else {
for (int cand = 1; cand <= N; cand++) {
selected[k] = cand;
recv_func(k + 1);
selected[k] = 0;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
selected = new int[M + 1];
recv_func(1);
System.out.println(sb.toString());
}
}(2+3) 방법
N개 중 중복을 허용없이 M개를 순서있게 나열
- 15649번 문제
- 이중 for문으로 시간 복잡도가 더 높은 버전
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N, M;
static int[] selected;
static void recv_func(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) {
sb.append(selected[i]).append(' ');
}
sb.append('\n');
} else {
for (int cand = 1; cand <= N; cand++) {
boolean isUsed = false;
for (int j = 1; j < k; j++) {
if (cand == selected[j])
isUsed = true;
}
if (!isUsed) {
selected[k] = cand;
recv_func(k + 1);
selected[k] = 0;
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
selected = new int[M + 1];
recv_func(1);
System.out.println(sb.toString());
}
}- for문 1번만 쓰고 시간 복잡도 줄인 버전
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N, M;
static int[] selected, used;
static void recv_func(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) {
sb.append(selected[i]).append(' ');
}
sb.append('\n');
} else {
for (int cand = 1; cand <= N; cand++) {
if (used[cand] == 1) continue;
selected[k] = cand;
used[cand] = 1;
recv_func(k + 1);
selected[k] = 0;
used[cand] = 0;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
selected = new int[M + 1];
used = new int[N + 1];
recv_func(1);
System.out.println(sb.toString());
}
}(1+4) 방법
N개 중 중복을 허용하여 M개를 고르기
- 15652번 문제
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] selected;
static StringBuilder sb = new StringBuilder();
static void recv_func(int k) {
if ( k == M + 1) {
for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
sb.append('\n');
} else {
int start = selected[k-1];
if (start == 0) start = 1;
for (int cand = start; cand <= N; cand++) {
selected[k] = cand;
recv_func(k + 1);
selected[k] = 0;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
selected = new int[M + 1];
recv_func(1);
System.out.println(sb.toString());
}
}(2+4) 방법
N개 중 중복없이 M개를 고르기
- 15650번 문제
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] selected;
static StringBuilder sb = new StringBuilder();
static void recv_func(int k) {
if ( k == M + 1) {
for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
sb.append('\n');
} else {
for (int cand = selected[k-1] + 1; cand <= N; cand++) {
selected[k] = cand;
recv_func(k + 1);
selected[k] = 0;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
selected = new int[M + 1];
recv_func(1);
System.out.println(sb.toString());
}
}- used 써서 한번 해봤음
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[] selected, used;
static StringBuilder sb = new StringBuilder();
static void recv_func(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
sb.append('\n');
} else {
int start = selected[k-1];
if (start == 0) start = 1;
for (int cand = start; cand <= N; cand++) {
if (used[cand] == 1) continue;
selected[k] = cand;
used[cand] = 1;
recv_func(k + 1);
selected[k] = 0;
used[cand] = 0;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
selected = new int[M + 1];
used = new int[N + 1];
recv_func(1);
System.out.println(sb.toString());
}
}BOJ 14888
- 출력을 잘 보면 연산자를 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다는 의미를 주의
- int 범위 : -21억 ~ 21억
- 그냥 int형을 쓰지 말고 근거에 의해 사용하자.
- 연산자라는 카드가 N-1개의 카드 중에서 중복 없이(같은 카드는 한 번만 사용) N-1개를 순서 있게 나열
- 시간복잡도 큰 버전
- 탐색이 완료될 때마다 연산이 수행되어서 비효율적
static int N, max, min;
static int[] nums, operators, order;
// order[1...N-1]에 연산자들이 순서대로 저장될 것
static void rec_func(int k, int value) {
if (k == N) { // 모든 연산자들을 전부 나열하는 방법을 찾은 상태
// 정한 연산자 순서대로 계산해서 정답을 갱신
} else { // k 번째 연산자는 무엇을 선택할 것인가?
// 4가지의 연산자 중 뭘 쓸 것인지 선택하고 재귀호출하기
}
}import java.util.*;
import java.io.*;
public class Main {
static FastReader scan = new FastReader();
static StringBuilder sb = new StringBuilder();
static int N, max, min;
static int[] nums, operators, order;
static void input(){
N = scan.nextInt();
// 입력 숫자 N개
nums = new int[N + 1];
// 연산자 +, -, *, / 4개
operators = new int[5];
// 연산자 가능한거 N-1개
order = new int[N];
for (int i = 1; i <= N; i++) {
nums[i] = scan.nextInt();
}
for (int i = 1; i <= 4; i++) {
operators[i] = scan.nextInt();
}
max = Integer.MIN_VALUE;
min = Integer.MAX_VALUE;
}
// order[1...N-1]에 연산자들이 순서대로 저장
static void rec_func(int k) {
// k == (N - 1) + 1)
// 모든 연산자들을 전부 나열하는 방법을 찾은 상태
if (k == N) {
// 정한 연산자 순서대로 계산해서 정답을 갱신
int value = calculator();
max = Math.max(max, value);
min = Math.min(min, value);
} else { // k번째 연산자는 무엇을 선택할 것인가?
// 4가지 연산자 들 중 뭘 쓸 것인지 선택하고 재귀호출
for (int cand = 1; cand <= 4; cand++) {
if (operators[cand] >= 1) {
operators[cand]--;
order[k] = cand;
rec_func(k+1);
operators[cand]++;
order[k] = 0;
}
}
}
}
// 완성된 식에 맞게 계산을 해서 정답에 갱신하는 작업
static int calculator() {
// nums, order
int value = nums[1];
for (int i = 1; i <= N - 1; i++) {
// value, order[i], nums[i+1]
if (order[i] == 1) // +
value = value + nums[i + 1];
if (order[i] == 2) // -
value = value - nums[i + 1];
if (order[i] == 3) // *
value = value * nums[i + 1];
if (order[i] == 4) // /
value = value / nums[i + 1];
}
return value;
}
public static void main(String[] args) {
input();
rec_func(1);
sb.append(max).append('\n').append(min);
System.out.println(sb.toString());
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}- 시간복잡도 최적화 버전
- 연산 결과도 같이 들고 다니도록
static int N, max, min;
static int[] nums, operators, order;
// order[1...N-1]에 연산자들이 순서대로 저장될 것
// k - 1번째 연산자까지 계산한 결과가 value
static void rec_func(int k, int value) {
if (k == N) { // 모든 연산자들을 전부 나열하는 방법을 찾은 상태
// value를 정답에 갱신
} else { // k 번째 연산자는 무엇을 선택할 것인가?
// 4가지의 연산자 중 뭘 쓸 것인지 선택하고
// 연산자를 계산한 후에 재귀호출하기
}
}import java.util.*;
import java.io.*;
public class Main {
static FastReader scan = new FastReader();
static StringBuilder sb = new StringBuilder();
static int N, max, min;
static int[] nums, operators, order;
static void input() {
N = scan.nextInt();
nums = new int[N + 1];
operators = new int[5];
order = new int[N];
for (int i = 1; i <= N; i++) {
nums[i] = scan.nextInt();
}
for (int i = 1; i <= 4; i++) {
operators[i] = scan.nextInt();
}
max = Integer.MIN_VALUE;
min = Integer.MAX_VALUE;
}
// order[1...N-1]에 연산자들이 순서대로 저장
static void rec_func(int k, int value) {
// k == (N - 1) + 1)
// 모든 연산자들을 전부 나열하는 방법을 찾은 상태
if (k == N) {
// 정한 연산자 순서대로 계산해서 정답을 갱신
//int value = calculator();
max = Math.max(max, value);
min = Math.min(min, value);
} else { // k번째 연산자는 무엇을 선택할 것인가?
// 4가지 연산자 들 중 뭘 쓸 것인지 선택하고 재귀호출
for (int cand = 1; cand <= 4; cand++) {
if (operators[cand] >= 1) {
operators[cand]--;
order[k] = cand;
rec_func(k + 1, calculator(value, cand, nums[k + 1]));
operators[cand]++;
order[k] = 0;
}
}
}
}
// 피연산자 2개와 연산자가 주어졌을 때 계산해주는 함수
static int calculator(int operand1, int operator, int operand2) {
if (operator == 1) {
return operand1 + operand2;
}
else if (operator == 2) {
return operand1 - operand2;
}
else if (operator == 3) {
return operand1 * operand2;
}
else {
return operand1 / operand2;
}
}
public static void main(String[] args) {
input();
rec_func(1, nums[1]);
sb.append(max).append('\n').append(min);
System.out.println(sb.toString());
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}BOJ 9663
- 아이디어의 전환, 반드시 2차원 배열일 필요는 없다.
- 1차원 배열로 생각하고 index를 row로,
col[index]를 col로 생각해보자 - 1번 행에 놓을 퀸의 열, 2번 행에 놓을 퀸의 열, … , N번 행에 놓을 퀸의 열을 재귀
- 1차원 배열로 생각하고 index를 row로,
- N개 중에서 중복을 허용하여 N개를 순서대로 나열하는 모든 경우 탐색
- 시간초과 버전
- 연산을 무조건 다돌아서 체크한다.
- N = 14일 때 21억을 넘을 수도 있어서, 일단 int로 정하고 N=14를 입력으로 넣어보고 확인하자.
attack()메서드의 경우 열이 같은 경우, 대각선 정방향, 대각선 역방향을 계산해줬다.- 왜냐하면, 대각선은 행과 열의 합이나 차가 같으면 정방향, 역방향으로 알 수 있음
static int N, count;
static int[] col; // col[i] : i번 행의 퀸은 col[i]번 열에 놓았다는 기록
// row번 ~ N번 행에 대해 가능한 퀸을 놓는 경우의 수 구하기
static void rec_func(int row) {
if (row == N + 1) { // 각 행마다 하나씩 잘 놓았다.
if (validity_check()) { // 서로 공격하는 퀸들이 없는 경우
count++;
}
} else {
for (int c = 1; c <= N; c++) {
col[row] = c;
rec_func(row + 1);
col[row] = 0;
}
}
}import java.io.*;
public class Main {
static int N, count;
static int[] col;
static void rec_func(int row) {
if (row == N+1) {
if (check()) {
count++;
}
} else {
for (int c = 1; c <= N; c++) {
col[row] = c;
rec_func(row + 1);
col[row] = 0;
}
}
}
static boolean check() {
for (int i = 1; i <= N; i++) {
// (i, col[i])
for (int j = 1; j < i; j++) {
// (j, col[j])
if (attack(i, col[i], j, col[j]))
return false;
}
}
return true;
}
static boolean attack(int r1, int c1, int r2, int c2) {
if (c1 == c2) return true;
if (r1 - c1 == r2 - c2) return true;
if (r1 + c1 == r2 + c2) return true;
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
col = new int[N+1];
rec_func(1);
System.out.println(count);
}
}- 정답, 구현 스케치 심화
static int N, count;
static int[] col; // col[i] : i번 행의 퀸은 col[i]번 열에 놓았다는 기록
// row번 ~ N번 행에 대해서 가능한 퀸을 놓는 경우의 수 구하기
static void rec_func(int row) {
if (row == N + 1) { // 1 ~ N번 행에 대해서 성공적으로 놓았다!
count++;
} else {
for (int c = 1; c <= N; c++) {
// row 행의 c 열에 놓을 수 있으면
col[row] = c;
rec_func(row + 1);
col[row] = 0;
}
}
}import java.io.*;
public class Main {
static int N, count;
static int[] col;
static StringBuilder sb = new StringBuilder();
static void rec_func(int row) {
if (row == N+1) {
count++;
} else {
for (int c = 1; c <= N; c++) {
boolean possible = true;
for (int i = 1; i <= row - 1; i++) {
if (attack(row, c, i, col[i])) {
possible = false;
break;
}
}
if (possible) {
col[row] = c;
rec_func(row + 1);
col[row] = 0;
}
}
}
}
static boolean check() {
for (int i = 1; i <= N; i++) {
// (i, col[i])
for (int j = 1; j < i; j++) {
// (j, col[j])
if (attack(i, col[i], j, col[j]))
return false;
}
}
return true;
}
static boolean attack(int r1, int c1, int r2, int c2) {
if (c1 == c2) return true;
if (r1 - c1 == r2 - c2) return true;
if (r1 + c1 == r2 + c2) return true;
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
col = new int[N+1];
rec_func(1);
System.out.println(sb.append(count));
}
}BOJ 1182
- 목표는
S = 0인 것 - 부분 수열 : 수열의 일부 항을 선택해서 원래 순서대로 나열
- 진 부분 수열들 중에서 합이 정확히 S가 되는 경우의 수
- 1번 원소 ~ N번 원소
- 1번 원소(0 or 1) , 2번 원소 (0 or 1), 3번 원소(0 or 1) , … N번 원소(0 or 1)
- 0 : 부분 수열에 포함시키지 않는다.
- 1 : 부분 수열에 포함시킨다.
- 이렇게 하면 하나의 부분수열
- 0 또는 1을 중복해서 여러 개 나열 가능 + 순서도 중요함
N = 2,M = 20문제를 푸는 것과 동일
static int N, S, count;
static int[] nums;
// k번째 원소를 포함시킬 지 정하는 함수
// value:=k-1 번째 원소까지 골라진 원소들의 합
static void rec_func(int k, int value) {
if (k == N + 1) { // 부분 수열을 하나 완성시킨 상태
// value가 S랑 같은 지 확인
} else {
// k번째 원소를 포함시킬 지 결정하고 재귀호출
}
}public static void main(String[] args) {
input();
// 1번째 원소부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 탐색
rec_func(1, 0);
// count가 정말 "진 부분집합"만 다루는 지 확인
System.out.println(count);
}import java.util.*;
import java.io.*;
public class Main {
static int N, S, count;
static int[] input;
// k번째 원소를 진 부분수열에 포함시킬지 결정하는 함수
// value는 k-1번째 원소까지 골라진 원소들의 합
static void rec_func(int k, int value) {
if (k == N + 1) {
if (S == value) count++;
} else {
// k번째 원소를 포함시키고 넘기기
rec_func(k+1, value + input[k]);
// 포함 안시키고 넘기기
rec_func(k+1, value);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
input = new int[N+1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
input[i] = Integer.parseInt(st.nextToken());
}
rec_func(1, 0);
if (S == 0) {
count--;
}
System.out.println(count);
}
}