SM6 2016 오랜기간 우리 가족과 함께 해온 차로 아버지께서 신차로 교체하시면서 나에게로 오게 되었다. 사실 중간 중간에 사용하기도 했고 관리도 함께 했기 때문에 안심스럽기도 하다.
오랜된 차이지만 약 10만이 거의 다되어 갈 때 즈음에 르노와의 엔진 결함 소송에서 결국 인정받고 엔진 교체가 이루어져서 20만 주행거리이지만 다른 소모품만 교체한다면 크게 문제 될 것은 없어 보인다. (사실 이것도 점검 후 교체해 주셨고 이후 정비도 지원해 주신다 하셨다.)
때문에 기존에 렌트하고 다니며 즐겨 사용하던 CarPlay를 사용하고 싶어서 비싼 공임비 들이지 않고 직접 하는 과정을 포스팅 하려고 한다.
단계적 풀이라는 카테고리를 달고 운영함으로써 본래의 의미를 지키기 위해 별 찍기 - 10 문제를 포스팅 하려고 했으나 레벨 문제로 존재하기 때문에 1 ~ 10까지 포스팅 해보려고 한다. 별 찍기를 통해 우리의 뇌를 다시 깨어보자.
문제 핵심
1 <= N <= 100
1개부터 N개까지 별을 차례로 출력
풀이 과정 1
다음과 같은 2중 반복문으로 그릴 수 있다.
1. 1부터 N까지 5개의 라인을 그리는 반복문
2. 라인에서 별을 그려내는 반복문
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++) {
str.append("*");
}
str.append("\n");
}
이는 출력물이 다음과 같이 나타난다.
물론 틀렸다는 것은 아니지만 다음방법으로도 생각해보는 것이 좋겠다.
풀이 과정 2
다음 코드를 통해 N * N 크기의 보드를 만들어서 별(*)과 공백을 구분하여 값을 넣어 준다.
1. 풀이 과정1 과 방식은 동일하지만, 조건문을 만족하지 않는 나머지에 공백으로 채워 준다.
char[][] board = new char[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(j <= i) {
board[i][j] = '*';
}
else {
board[i][j] = ' ';
}
}
}
이는 다음과 같은 구조를 따른다.
난이도가 어려운 문제에서는 여러 풀이 방식을 생각하기도 어렵고 틀리는 경우가 많기 때문에 이 처럼 쉬운 문제에서 다양하게 시도해 보는 것이 좋다.
전체코드 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder str = new StringBuilder();
int N = Integer.parseInt(br.readLine());
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++) {
str.append("*");
}
str.append("\n");
}
System.out.println(str);
}
}
전체코드 2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
char[][] board = new char[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(j <= i ) {
board[i][j] = '*';
}
else {
board[i][j] = ' ';
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sb.append(board[i][j]);
}
sb.append("\n");
}
System.out.println(sb);
}
}
이번에는 백준 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);
}
}
