이번에는 백준 15652번 문제를 통해 백트래킹 알고리즘 학습을 강화해 보자. N과 M의 최종문제이다. 지금까지 문제를 생각해보면 이 문제도 15651번 문제 처럼 아주 쉽게 풀 수 있다.
문제 핵심
1부터 N까지의 자연수 중 중복 없이 M개를 고른 수열
1 <= M <= N <= 8
중복하여 방문 가능
이전의 수보다 작지만 않으면 됨 ( 같은 수여도 가능 )
풀이 과정
지금까지 풀이 1, 2, 3문제를 보았다면 아주 쉽게 접근할 수 있다.
이전 문제의 이론은? "모든 경로가 중복 방문이 가능하다면? 다시 처음부터 시작하면 된다." 였다.
그렇다면 우리는 해당 숫자부터 즉, 1이면 1부터 2이면 2부터 그대로 값을 전달해주면 된다.
이전 문제에서 고정시켰던 값을 다시 변동 시켜 계속 전달해주면 된다.
핵심 코드를 살펴보자
핵심 코드
다음 반복문에서 i 값을 그대로 전달해주는 것을 알 수 있다.
그렇게 되면 2인 값이 그대로 2로 전달되고 start매개변수를 통해 (M = 3, N = 3 인 경우) 1, 2, 2 와 같은 값을 얻을 수 있다.
private static void backTracking(int depth, int M, int N, int start) {
if (depth == M) {
for (int i : arr) {
stringBuilder.append(i).append(" ");
}
stringBuilder.append("\n");
return;
}
for (int i = start; i < N; i++) {
arr[depth] = i + 1;
backTracking(depth + 1, M, N, i);
}
}
이제는 정말로 쉽게 풀이될 것이라고 생각한다. 이번 4개의 N과 M의 문제를 통해 충분히 학습될 것이라고 생각한다. 하지만 백트래킹이라고 해서 한 가지 유형만 있는 것은 아니니 몇 개 안남은 단계 문제를 풀고, 이후 다른 백트래킹 문제도 풀어보는 것이 좋겠다.
전체코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int[] arr;
private static StringBuilder stringBuilder = new StringBuilder();
private static void backTracking(int depth, int M, int N, int start) {
if (depth == M) {
for (int i : arr) {
stringBuilder.append(i).append(" ");
}
stringBuilder.append("\n");
return;
}
for (int i = start; i < N; i++) {
arr[depth] = i + 1;
backTracking(depth + 1, M, N, i);
}
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int N = Integer.parseInt(stringTokenizer.nextToken());
int M = Integer.parseInt(stringTokenizer.nextToken());
arr = new int[M];
backTracking(0, M, N, 0);
System.out.println(stringBuilder);
}
}
이번에는 백준 15651번 문제를 통해 백트래킹 알고리즘 학습을 강화해 보자. 이쯤되면 점점 익숙해질 것이다.
문제 핵심
1부터 N까지의 자연수 중 중복 없이 M개를 고른 수열
1 <= M <= N <= 7
중복하여 방문 가능
풀이 과정
이전 풀이를 보았다면 바로 생각이 날 수도 있다.
모든 경로가 중복 방문이 가능하다면? 다시 처음부터 시작하면 된다.
우리는 무조건 1부터 시작하는 조건을 가지고 있다. 그렇다면 변동하던 시작값을 고정시켜버리면 항상 중복하여 방문하게 된다.
핵심 코드
start 매개변수를 제외 시키고 반복문의 시작값을 0으로 고정하였다.
private static void backTracking(int depth, int M, int N) {
if (depth == M) {
for (int i : arr) {
stringBuilder.append(i).append(" ");
}
stringBuilder.append("\n");
return;
}
for (int i = 0; i < N; i++) {
arr[depth] = i + 1;
backTracking(depth + 1, M, N);
}
}
반복하여 진행하니 점점 한 눈에 알아볼 정도로 난이도가 내려가고 있다. ( 아니면 죄송...) 다음 4번째 N과 M을 끝으로 이해도를 높이길 바란다.
전체코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int[] arr;
private static StringBuilder stringBuilder = new StringBuilder();
private static void backTracking(int depth, int M, int N) {
if (depth == M) {
for (int i : arr) {
stringBuilder.append(i).append(" ");
}
stringBuilder.append("\n");
return;
}
for (int i = 0; i < N; i++) {
arr[depth] = i + 1;
backTracking(depth + 1, M, N);
}
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int N = Integer.parseInt(stringTokenizer.nextToken());
int M = Integer.parseInt(stringTokenizer.nextToken());
arr = new int[M];
backTracking(0, M, N);
System.out.println(stringBuilder);
}
}
요즘 시험이니 일이니 핑계 거리가 생겨 포스팅이 많이 늦어졌습니다. 다시 매일 노력하여 포스팅 하도록 노력하겠습니다. 감사합니다.
이번에는 백준 15649번 문제를 통해 백트래킹 알고리즘을 실습해 보자.
백트래킹이란 간단히 설명하면 가능한 모든 경로 탐색 중 조건이 맞지 않으면 이전 단계로 돌아가 다시 탐색하는 알고리즘이다.
문제 핵심
1부터 N까지의 자연수 중 중복 없이 M개를 고른 수열
1 <= M <= N < 8
풀이 과정
반복과 재귀를 통해 깊이에 따라 값을 처리한다.
dfs를 참고할 수 있겠다.
핵심 코드
현재 깊이를 체크한다.
최대 깊이에 도달한다면 리스트 값을 저장하고 리턴한다.
반복문을 통해 방문되지 않은 리스트 요소를 특정하여 방문한다.
리스트 현재 깊이 인덱스에 값을 저장한다.
재귀를 통해 다음 깊이로 이동한다.
false를 통해 방문을 초기화 하고 이전으로 이동
private static void backTracking(int depth, int M, int N) {
if(depth == M) {
for(int i : arr) {
stringBuilder.append(i).append(" ");
}
stringBuilder.append("\n");
return;
}
for(int i = 0; i < N; i++) {
if(!visited[i]) {
visited[i] = true;
arr[depth] = i + 1;
backTracking(depth + 1, M, N);
visited[i] = false;
}
}
}
EX) N : 4, M : 2
N과 M이 위와 같을 때 1회전의 경우 다음과 같이 진행된다.
이후 depth + 1을 통해 M과 같아지게 되므로 저장 후 리턴된다.
마지막 방문했던 인덱스를 false를 통해 이전으로 돌아온다.
이 때 arr 배열에는 이후 값을 덮어쓰기 때문에 제거할 필요 없다.
다소 난해하지만, 재귀 방식을 이용한다면 풀 수 있는 문제이다. 이번 풀이에서는 DFS와 비슷하다고 볼 수 있다. 일정 깊이까지 도달한 후 다시 돌아오는 알고리즘으로 디버깅을 통해 로직이 진행되는 순서를 확인하면 좋겠다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int [] arr;
private static boolean [] visited;
private static StringBuilder stringBuilder = new StringBuilder();
private static void backTracking(int depth, int M, int N) {
if(depth == M) {
for(int i : arr) {
stringBuilder.append(i).append(" ");
}
stringBuilder.append("\n");
return;
}
for(int i = 0; i < N; i++) {
if(!visited[i]) {
visited[i] = true;
arr[depth] = i + 1;
backTracking(depth + 1, M, N);
visited[i] = false;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
arr = new int[M];
visited = new boolean[N];
backTracking(0, M, N);
System.out.println(stringBuilder);
}
}
이번 글에서는 큐, 스택에 마무리 문제인 24511번 문제를 해결해 보자. 시간 제한과 메모리 제한이 까다로울 것으로 예상된다.
문제 핵심
첫째 줄 - 자료구조의 수 : N
둘째 줄 - 수열의 종류 : 0 ( Queue ), 1 ( Stack )
셋째 줄 - 자료구조의 초기값 설정
넷째 줄 - 삽입할 수열의 길이 : M
다섯째 줄 - 삽입할 수열의 원소들
풀이 과정
첫 번째 예제의 과정 중 첫 번째 스텝을 다음과 같이 나타낼 수 있다.
그림 처럼 queue와 stack을 구현하여 값을 삽입하고 제거하는 과정으로 구현해보자.
아마 메모리에서 먼저 초과되지 않을까 싶다.
1. 자료구조 저장
0, 1과 구별 값에 따라 큐인지 스택인지 구별하여 저장한다.
List<Object> dataStructure = new ArrayList<Object>();
for (int i = 0; i < N; i++) {
int type = Integer.parseInt(stringTokenizer.nextToken());
if (type == 0) {
dataStructure.add(new LinkedList<Integer>());
} else {
dataStructure.add(new Stack<Integer>());
}
}
2. 초기 값 저장
세번 째 줄의 초기 값들을 저장한다.
이 때 초기값들은 instanceof를 통해 자료구조를 판별 후 맞는 메소드를 사용한다.
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(stringTokenizer.nextToken());
if (dataStructure.get(i) instanceof Queue) {
((Queue<Integer>) dataStructure.get(i)).offer(num);
} else {
((Stack<Integer>) dataStructure.get(i)).add(num);
}
}
3. 메인 과정
새로운 값 들이 큐와 스택을 지나면서 반복되는 과정이다.
이 때, 사실 스택이 값을 거쳐가기만 하기 때문에 의미가 없다.
for (int i = 0; i < M; i++) {
int num = Integer.parseInt(stringTokenizer.nextToken());
int temp = num;
for (int j = 0; j < N; j++) {
if (dataStructure.get(j) instanceof Queue) {
((Queue<Integer>) dataStructure.get(j)).add(temp);
temp = ((Queue<Integer>) dataStructure.get(j)).remove();
}
}
stringBuilder.append(temp).append(" ");
}
결과는 시간 초과로 메모리 문제가 아닌 2 중 for문에 N과 M의 최악의 경우 (On2) 100,000 * 100,000 = 10,000,000,000 기 때문에 벌어진 일이다. 그렇다면 2 중 for문의 구조를 제거하고, 스택구조에서 값은 지나치기만 하기 때문에 경우에서 제거한다.
4. 자료구조의 재구성
그렇다면 큐의 구조일 때 값을 교체하는 과정이고, 그게 여러개라면 하나씩 밀려나는 과정이다.
큐 여러개가 하나의 값만 가지고 있기 때문에 여러개의 큐가 하나의 큐가 되어버린다.
( 즉, 다음과 같은 구조일 때 새로운 값이 들어온다면 하나의 큐처럼 행동한다. )
그렇다면 하나의 큐를 생성하고 큐일 경우에만 값을 추가한다.
Deque<String> queue = new ArrayDeque<>();
StringBuilder stringBuilder = new StringBuilder();
int N = Integer.parseInt(bufferedReader.readLine());
String[] dataStructureString = bufferedReader.readLine().split(" ");
String[] valueString = bufferedReader.readLine().split(" ");
for (int i = 0; i < N; i++) {
int type = Integer.parseInt(dataStructureString[i]);
if(type == 0){
queue.addLast(valueString[i]);
}
}
5. 메인 과정 재구성
다음과 같이 큐의 삽입과 삭제를 반복하면 O(n)의 경우의 수와 메모리 문제가 모두 해결된다.
int M = Integer.parseInt(bufferedReader.readLine());
String[] addValueString = bufferedReader.readLine().split(" ");
for (int i = 0; i < M; i++) {
queue.addFirst(addValueString[i]);
stringBuilder.append(queue.removeLast()).append(" ");
}
이번 문제는 마치 알고리즘이 큐처럼 행동하게 하여 해결할 수 있었다. 다음과 같이 자료구조의 개념을 이해한다면 여러방법으로 구현할 수 있다. 줄 서거나(큐), 박스에 물건을 넣고 빼거나(스택) 처럼 한 가지로 제한되지 않는다는 점이다.
시간과 메모리를 줄여야 한다는 점에서 이런 구조를 생각할 수 있었던 문제였다.
실패 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
List<Object> dataStructure = new ArrayList<Object>();
StringTokenizer stringTokenizer;
StringBuilder stringBuilder = new StringBuilder();
int N = Integer.parseInt(bufferedReader.readLine());
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int i = 0; i < N; i++) {
int type = Integer.parseInt(stringTokenizer.nextToken());
if (type == 0) {
dataStructure.add(new LinkedList<Integer>());
} else {
dataStructure.add(new Stack<Integer>());
}
}
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(stringTokenizer.nextToken());
if (dataStructure.get(i) instanceof Queue) {
((Queue<Integer>) dataStructure.get(i)).offer(num);
} else {
((Stack<Integer>) dataStructure.get(i)).add(num);
}
}
int M = Integer.parseInt(bufferedReader.readLine());
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int i = 0; i < M; i++) {
int num = Integer.parseInt(stringTokenizer.nextToken());
int temp = num;
for (int j = 0; j < N; j++) {
if (dataStructure.get(j) instanceof Queue) {
((Queue<Integer>) dataStructure.get(j)).add(temp);
temp = ((Queue<Integer>) dataStructure.get(j)).remove();
}
}
stringBuilder.append(temp).append(" ");
}
System.out.println(stringBuilder);
}
}
성공 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
Deque<String> queue = new ArrayDeque<>();
StringBuilder stringBuilder = new StringBuilder();
int N = Integer.parseInt(bufferedReader.readLine());
String[] dataStructureString = bufferedReader.readLine().split(" ");
String[] valueString = bufferedReader.readLine().split(" ");
for (int i = 0; i < N; i++) {
int type = Integer.parseInt(dataStructureString[i]);
if(type == 0){
queue.addLast(valueString[i]);
}
}
int M = Integer.parseInt(bufferedReader.readLine());
String[] addValueString = bufferedReader.readLine().split(" ");
for (int i = 0; i < M; i++) {
queue.addFirst(addValueString[i]);
stringBuilder.append(queue.removeLast()).append(" ");
}
System.out.println(stringBuilder);
}
}
이번 글에서는 백준 2346번 문제를 통해 queue 개념에 관해 좀 더 복잡한 문제를 풀어보자
문제 핵심
N : 풍선의 개수 ( 자연수 ) 1 ~ 1000
각 종이에 이동할 숫자가 적혀 있다. ( 0은 없다 )
적힌 종이 별로 양수면 오른쪽, 음수는 왼쪽으로 이동한다.
풀이 과정
다음 Deque를 통해 문제를 풀어 나가며, 인덱스를 기억해 두는 것이 핵심이다.
1. 풍선 번호와 종이 저장
1. 큐에 인덱스 값들을 저장한다.
2. move 정수 배열에 해당 종이를 저장한다.
Deque<Integer> indexQueue = new ArrayDeque<Integer>();
int[] move = new int[N];
for (int i = 0; i < N; i++) {
move[i] = Integer.parseInt(stringTokenizer.nextToken());
indexQueue.add(i);
}
2. 반복
첫 시작은 앞에서부터 시작하기 때문에 미리 처리 한다.
큐에서 꺼낸 값은 인덱스 값이고, 이 인덱스 값을 가지고 move 정수 배열에서 이동할 거리를 확인할 수 있다.
int removeIndex = indexQueue.removeFirst();
stringBuilder.append(removeIndex + 1).append(" ");
