❓ 부등호
🏷️ 관련 주제 : DFS Greedy Brute Force Back Tracking
💦 나의 시도
DFS를 이용한 완전 탐색(Brute Force)
첫번째 숫자부터 하나씩 부등호의 조건을 만족하는 값을 넣어가며 재귀함수를 호출하여 DFS로 문제를 해결해 보았습니다.
💥 최댓값 자료 범위 체크!
처음에 최댓값과 최솟값을 넣은 배열을 int형으로 선언하였었는데
결과 출력값이 이상하게 나와서 다시 생각해보니
최대로 나올 수 있는 값인 9876543210이 int형 범위를 넘어선 값이었습니다.
따라서 최대,최솟값을 담을 배열을 long타입으로 선언하여 문제를 풀었습니다.
💥 0으로 시작하는 값 체크!
맨 앞의 숫자가 0인 경우 결과값을 출력하기 위해서는 맨 앞에 0을 추가해 주어야 했습니다.
위의 경우 해당 값을 문자열로 변환한 결과의 길이가 k+1보다 작아지므로
먼저 최대,최솟값을 문자열로 변환 후, 조건문으로 문자열의 길이를 체크하고
길이가 k + 1보다 작은 경우 0을 추가, 결과값을 출력해 주었습니다.
⏱️ 탐색 범위를 좁혀보자!
처음에 매개변수를 잘못주어서 결괏값이 잘못 나왔었는데
해당 문제 코드 부분을 찾기 위해 코드 중간 연산 결과값을 출력하다가
최대, 최솟값을 구하기만 하면 되는데 모든 범위를 완전탐색하는 것이 너무 불필요한 탐색을 많이 하는 것 같다는 생각이 들었습니다.
'제일 작은 값부터 탐색하여 처음 나온 값이 최솟값이고 제일 큰 값부터 탐색하여 처음 나온 값이 최댓값이 될테니 Greedy로 탐색을 하면 중간 부분은 탐색하지 않아도 되어 시간이 훨씬 단축될거야!'
Greedy를 이용한 방법
완전탐색을 이용한 풀이에서는 결과값을 최대, 최솟값과 비교해 주었다면
Greedy를 이용한 풀이에서는 해당 부분을 없에고
메서드를 가장 작은 값에서 부터탐색하는 findMin()메서드와
가장 큰 값에서부터 탐색하는 findMax()메서드로 분리하고
모든 조건을 만족하는 값이 나오면 바로 해당 결과값을 반환하도록 코드를 수정하였습니다.
제출 결과 메모리나 시간 측면에서 완전 탐색보다 훨씬 효율적인 탐색을 한 것을 확인할 수 있었습니다.
📑제출 기록 및 오답 원인
두번째 제출이 Greedy를 이용한 방법,
세번째 제출이 완전탐색을 이용한 방법
처음에 매개변수를 잘못 넣고 완전탐색을 이용한 방법을 제출해서 틀렸었는데 수정하다가 Greedy를 이용한 방법이 나을 것 같아서 코드 수정 후, 제출 성공!
완전 탐색을 이용한 방법도 제출해 보고 싶어서 매개변수 수정해서 다시 제출 성공!
💯 해결 방법
완전 탐색(Brute Force)으로 해결
import java.io.*;
import java.util.*;
public class Main {
public static int k;
public static String[] signs;
public static long[] minMax;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
k = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
signs = new String[k];
for (int i = 0; i < k; i++) {
signs[i] = st.nextToken();
}
minMax = new long[]{9876543210L, 1L};
int[] visited = new int[10];
dfs(0L, 0, visited);
String min = String.valueOf(minMax[0]);
String max = String.valueOf(minMax[1]);
if (min.length() < k + 1) {
min = "0" + min;
}
if (max.length() < k + 1) {
max = "0" + max;
}
System.out.println(max+"\n"+min);
}
public static void dfs(long number, int idx, int[] visited) {
if (idx == k + 1) {
minMax[0] = Math.min(minMax[0], number);
minMax[1] = Math.max(minMax[1], number);
return;
}
if (idx == 0) {
for (int i = 0; i < 10; i++) {
int[] copyVisited = visited.clone();
copyVisited[i] = 1;
dfs(i, idx + 1, copyVisited);
}
} else {
int pre = (int) (number % 10);
switch (signs[idx - 1]) {
case "<":
for (int i = pre + 1; i < 10; i++) {
if (visited[i] == 1) {
continue;
}
int[] copyVisited = visited.clone();
copyVisited[i] = 1;
dfs(number * 10 + i, idx + 1, copyVisited);
}
break;
case ">":
for (int i = 0; i < pre; i++) {
if (visited[i] == 1) {
continue;
}
int[] copyVisited = visited.clone();
copyVisited[i] = 1;
dfs(number * 10 + i, idx + 1, copyVisited);
}
break;
default:
return;
}
}
}
}Greedy로 해결
import java.io.*;
import java.util.*;
public class Main {
public static int k;
public static String[] signs;
public static long[] minMax;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
k = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
signs = new String[k];
for (int i = 0; i < k; i++) {
signs[i] = st.nextToken();
}
int[] visited = new int[10];
;
String min = String.valueOf(findMin(0L, 0, visited));
String max = String.valueOf(findMax(0L, 0, visited));
if (min.length() < k + 1) {
min = "0" + min;
}
if (max.length() < k + 1) {
max = "0" + max;
}
System.out.println(max+"\n"+min);
}
public static long findMin(long number, int idx, int[] visited) {
if (idx == k + 1) {
return number;
}
if (idx == 0) {
for (int i = 0; i < 10; i++) {
int[] copyVisited = visited.clone();
copyVisited[i] = 1;
long minNum = findMin(i, idx + 1, copyVisited);
if (minNum != -1) {
return minNum;
}
}
} else {
int pre = (int) (number % 10);
switch (signs[idx - 1]) {
case "<":
for (int i = pre + 1; i < 10; i++) {
if (visited[i] == 1) {
continue;
}
int[] copyVisited = visited.clone();
copyVisited[i] = 1;
long minNum = findMin(number * 10 + i, idx + 1, copyVisited);
if (minNum != -1) {
return minNum;
}
}
break;
case ">":
for (int i = 0; i < pre; i++) {
if (visited[i] == 1) {
continue;
}
int[] copyVisited = visited.clone();
copyVisited[i] = 1;
long minNum = findMin(number * 10 + i, idx + 1, copyVisited);
if (minNum != -1) {
return minNum;
}
}
break;
}
}
return -1;
}
public static long findMax(long number, int idx, int[] visited) {
if (idx == k + 1) {
return number;
}
if (idx == 0) {
for (int i = 9; i >= 0; i--) {
int[] copyVisited = visited.clone();
copyVisited[i] = 1;
long maxNum = findMax(i, idx + 1, copyVisited);
if (maxNum != -1) {
return maxNum;
}
}
} else {
int pre = (int) (number % 10);
switch (signs[idx - 1]) {
case "<":
for (int i = 9; i >= pre + 1; i--) {
if (visited[i] == 1) {
continue;
}
int[] copyVisited = visited.clone();
copyVisited[i] = 1;
long maxNum = findMax(number * 10 + i, idx + 1, copyVisited);
if (maxNum != -1) {
return maxNum;
}
}
break;
case ">":
for (int i = pre - 1; i >= 0; i--) {
if (visited[i] == 1) {
continue;
}
int[] copyVisited = visited.clone();
copyVisited[i] = 1;
long maxNum = findMax(number * 10 + i, idx + 1, copyVisited);
if (maxNum != -1) {
return maxNum;
}
}
break;
}
}
return -1;
}
}📝 공부한 내용
그리디 알고리즘(Greedy Algorithm)
매 선택에서 "현재 상황에서 가장 최적인 답"을 선택해 전체에 적합한 결과를 도출하는 알고리즘
백트래킹을 통해 추가 점검을 하지 않고 현재 조건에서 선택을 했다면 더 이상 다른 선택 가능 경우는 검증하지 않는다.
하지만 부분 최적해가 언제나 전체 최적해가 되지는 않는다는 문제가 있다.
그럼에도 불구하고 속도가 매우 빠르기 때문에 다음 두 조건을 만족하는 경우 자주 사용될 수 있다.
Greedy 적용 조건
1) 탐욕 선택 속성(Greedy Choice Property)
- 이전 선택이 이후에 영향을 주지 않음.
2) 최적 부분 구조(Optimal Substructure)
- 부분 문제의 최적 결과가 전체에도 그대로 적용될 수 있어야 한다.2의 조건에서 DP(Dynamic Programming)을 떠올릴 수 있지만
DP의 경우 1번 조건을 만족하지 않는다.
Greedy 문제임을 증명하는 방법
반례를 1개만 찾으면 OK!
Greedy를 이용해 해결할 수 있는 문제 예시
활동 선택(Action Selection) 문제
N개의 활동이 있고 각 활동에는 시작 시간 및 종료 시간이 있을 때,
한 사람이 최대한 많이 할 수 있는 활동(Activity)의 수를 구하는 문제
즉, 각각의 활동(Activity)에는 시간이 소요되므로 하나를 선택했다면 그 동안 해당 시간에 다른 활동을 할 수 없다.
이러한 상황일 때 가장 많은 활동에 참여하려면 어떻게 해야할까?
Solution
언제 시작하든 전체에서 가장 종료 시간이 빠른 것부터 선택해야 한다.
(어차피 시작 시간은 종료 시간 이전이므로 고려하지 않는다.)
따라서 종료 시간을 기준으로 정렬한 뒤,
제일 먼저 끝나는 활동을 무조건 선택하고 끝났을 때,
바로 다음에 선택할 수 있는 활동을 찾아 수행하는 방식을 반복하여 해결할 수 있다.
