'java' 태그의 글 목록

이번에는 다음과 같은 역 피라미드를 만들어 보자.

*********
*******
*****
***
*

문제 핵심

1 <= N <= 100
2 * N - 1 개의 별을 찍어낸다고 한다.
가운데 정렬로 별을 (2 * N - 1), (2 * N - 3), ..., 1개의 별을 찍어내는 문제

풀이 과정

별 찍기 5와 같이 규칙을 찾아 풀어나가 보자.

1. N이 5일 때 공백의 개수는 0, 1, 2, 3, ..., N -1개이다.

2. 이 때 별의 개수는 (2 * N - 1)부터 시작하여 2개씩 적어진다.. 즉 홀수로 진행된다.

3. 각각의 층은 (2 * N - 1), (2 * N - 2), ..., N로 감소된다.

4. 1부터 N + i까지 항상 반복하면 i값에 따라 3번의 조건을 만족하고 j < N - i값에 따라 공백은 점차 늘어나게 된다.

5. 나머지를 별로 채움으로써 피라미드처럼 나오게 된다.

for (int i = N - 1; i >= 0; i--) {
    for (int j = 1; j <= N + i; j++) {
        if(j < N - i) {
            stringBuilder.append(' ');
        }
        else {
            stringBuilder.append('*');
        }
    }
    stringBuilder.append('\n');
}

5번 문제를 반대로 생각하여 기존의 코드를 조금만 바꾸면 되는 문제이다.
이제 다음문제는 다양한 조건으로 9번을 풀기 전에
뇌를 다지는 문제가 될 것이다.

전체 코드

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));
        int N = Integer.parseInt(br.readLine());
        StringBuilder stringBuilder = new StringBuilder();

        for (int i = N - 1; i >= 0; i--) {
            for (int j = 1; j <= N + i; j++) {
                if(j < N - i) {
                    stringBuilder.append(' ');
                }
                else {
                    stringBuilder.append('*');
                }
            }
            stringBuilder.append('\n');
        }

        System.out.println(stringBuilder);
    }
}

'백준 단계별 풀이' 카테고리의 다른 글

[ 백준 2442번 문제 ] 별 찍기 - 5 - JAVA (1)	2025.06.15
[ 백준 2441번 문제 ] 별 찍기 - 4 - JAVA (2)	2025.06.13
[ 백준 2440번 문제 ] 별 찍기 - 3 - JAVA (1)	2025.06.12
[ 백준 2439번 문제 ] 별 찍기 - 2 - JAVA (2)	2025.06.11
[ 백준 2438번 문제 ] 별 찍기 - 1 - JAVA (1)	2025.06.10

이번에는 2번 문제와 같이 오른쪽 벽에 붙어 별을 그려나가는 방식이다.
좌우 대칭으로 숫자를 바꿔 생각하면 편하다.

[ 백준 2439번 문제 ] 별 찍기 - 2 - JAVA

이전 별 찍기에서 생각했던 공백을 생각해야 하는 문제가 나왔다.N * N의 크기로 생각했을 때 공백과 별 위치를 생각하면 풀면 된다. [ 백준 2438번 문제 ] 별 찍기 - 1 - JAVA단계적 풀이라는 카테고

p-coding.tistory.com

문제 핵심

1 <= N <= 100
N 별 개수를 시작으로 점점 줄여나가 왼쪽 벽에 붙여 나가는 과정
즉 공백이 0 ~ N - 1까지 별의 개수가 N ~ 1 개까지

풀이 과정

조건문을 사용하여 공백부터 나왔던 값을 별부터 나오게 끔 변경하면 된다.

1. i를 통해 N번 반복

2. j를 통해 j < i 인 경우에만 공백 처리, i 값이 증가함에 따라 0, 1, 2, 3, 4 ~ N - 1번 공백을 출력

3. 그 외의 조건은 모두 별로 처리

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if(j < i) {
            str.append(' ');
        }
        else {
            str.append('*');
        }
    }
    str.append('\n');
}

다음은 지금까지 배운 문제를 토대로
1~4번 중 2개를 합쳐서 풀어보는 5 ~ 6번 문제이다.
9번까지 쭉 뇌를 깨어보는 별 찍기를 해보자.

전체 코드

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 = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(j < i) {
                    str.append(' ');
                }
                else {
                    str.append('*');
                }
            }
            str.append('\n');
        }

        System.out.println(str);
    }
}

'백준 단계별 풀이' 카테고리의 다른 글

[ 백준 2443번 문제 ] 별 찍기 - 6 - JAVA (1)	2025.06.17
[ 백준 2442번 문제 ] 별 찍기 - 5 - JAVA (1)	2025.06.15
[ 백준 2440번 문제 ] 별 찍기 - 3 - JAVA (1)	2025.06.12
[ 백준 2439번 문제 ] 별 찍기 - 2 - JAVA (2)	2025.06.11
[ 백준 2438번 문제 ] 별 찍기 - 1 - JAVA (1)	2025.06.10

1번과 비슷한 문제로 별 찍기 1번 문제를 반대로 생각하면 알 수 있다.

[ 백준 2438번 문제 ] 별 찍기 - 1 - JAVA

단계적 풀이라는 카테고리를 달고 운영함으로써본래의 의미를 지키기 위해 별 찍기 - 10 문제를 포스팅 하려고 했으나레벨 문제로 존재하기 때문에 1 ~ 10까지 포스팅 해보려고 한다.별 찍기를 통

p-coding.tistory.com

문제 핵심

1 <= N <= 100
별을 N부터 1까지 찍어내는 구조

풀이 과정

문제 자체는 어렵지 않아 N부터 1까지 역으로 출력하면 된다.

문제 1번에서 봤던 것과 같이 공백으로 생각하면 이해하기 쉽다.

1. N부터 시작해 i가 증감함에 따라 점점 별의 출력 개수를 줄여나가는 방식

for(int i = 0; i < N; i++) {

    for(int j = N - i; j > 0; j--) {
        str.append("*");
    }
    str.append("\n");
}

이번에는 직접 이차원 배열을 생성해 칸을 채워 나가는 방법도 시도해 보자.

1번 문제를 반대로만 생각하면 아주 쉽게 풀 수 있는 문제이다.
원래 목표였던 10번 문제 이전까지는 브론즈 문제로 쉽게 풀 수 있다.

전체 코드

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 = 0; i < N; i++) {

            for(int j = N - i; j > 0; j--) {
                str.append("*");
            }
            str.append("\n");
        }

        System.out.println(str);
    }
}

'백준 단계별 풀이' 카테고리의 다른 글

[ 백준 2442번 문제 ] 별 찍기 - 5 - JAVA (1)	2025.06.15
[ 백준 2441번 문제 ] 별 찍기 - 4 - JAVA (2)	2025.06.13
[ 백준 2439번 문제 ] 별 찍기 - 2 - JAVA (2)	2025.06.11
[ 백준 2438번 문제 ] 별 찍기 - 1 - JAVA (1)	2025.06.10
[ 백준 15652번 문제 ] N과 M (4) - JAVA (1)	2025.05.29

이전 별 찍기에서 생각했던 공백을 생각해야 하는 문제가 나왔다.
N * N의 크기로 생각했을 때 공백과 별 위치를 생각하면 풀면 된다.

[ 백준 2438번 문제 ] 별 찍기 - 1 - JAVA

단계적 풀이라는 카테고리를 달고 운영함으로써본래의 의미를 지키기 위해 별 찍기 - 10 문제를 포스팅 하려고 했으나레벨 문제로 존재하기 때문에 1 ~ 10까지 포스팅 해보려고 한다.별 찍기를 통

p-coding.tistory.com

문제 핵심

1 <= N <= 100
N - 1 공백개수를 시작으로 0까지, 별은 1 ~ 5까지 그려나가는 구조

풀이 과정

별 찍기 1에서 사용했던 방식으로 공백과 별을 그려야 하는 조건을 맞추어 코드 구현하면 된다.

1에서는 구조를 설명하기 위해 2차원 배열을 사용하였지만 배열없이 바로 StringBuilder에 값을 추가 하면 된다.

1. N개의 줄을 반복문을 통해 생성

2. 한 줄마다 j가 ( N - i - 1 ) 보다 작을 때 공백 출력, i가 증가함에 따라 공백 감소

3. 아닌 경우에는 별 출력

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if(j < N - i - 1) {
            stringBuilder.append(' ');
        }
        else {
            stringBuilder.append('*');
        }
    }
    stringBuilder.append('\n');
}

아직까지는 괴랄한 별 찍기가 아니라서 괜찮은 것 같다.
이 차원 배열 안에 어떻게 그릴 것인가
그게 중점으로 보인다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        StringBuilder stringBuilder = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(j < N - i - 1) {
                    stringBuilder.append(' ');
                }
                else {
                    stringBuilder.append('*');
                }
            }
            stringBuilder.append('\n');
        }

        System.out.println(stringBuilder);

    }
}

'백준 단계별 풀이' 카테고리의 다른 글

[ 백준 2441번 문제 ] 별 찍기 - 4 - JAVA (2)	2025.06.13
[ 백준 2440번 문제 ] 별 찍기 - 3 - JAVA (1)	2025.06.12
[ 백준 2438번 문제 ] 별 찍기 - 1 - JAVA (1)	2025.06.10
[ 백준 15652번 문제 ] N과 M (4) - JAVA (1)	2025.05.29
[ 백준 15651번 문제 ] N과 M (3) - JAVA (1)	2025.05.24

단계적 풀이라는 카테고리를 달고 운영함으로써
본래의 의미를 지키기 위해 별 찍기 - 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);
    }
}

'백준 단계별 풀이' 카테고리의 다른 글

[ 백준 2440번 문제 ] 별 찍기 - 3 - JAVA (1)	2025.06.12
[ 백준 2439번 문제 ] 별 찍기 - 2 - JAVA (2)	2025.06.11
[ 백준 15652번 문제 ] N과 M (4) - JAVA (1)	2025.05.29
[ 백준 15651번 문제 ] N과 M (3) - JAVA (1)	2025.05.24
[ 백준 15650번 문제 ] N과 M (2) - JAVA (1)	2025.05.23

이번에는 백준 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);

    }
}

'백준 단계별 풀이' 카테고리의 다른 글

[ 백준 2439번 문제 ] 별 찍기 - 2 - JAVA (2)	2025.06.11
[ 백준 2438번 문제 ] 별 찍기 - 1 - JAVA (1)	2025.06.10
[ 백준 15651번 문제 ] N과 M (3) - JAVA (1)	2025.05.24
[ 백준 15650번 문제 ] N과 M (2) - JAVA (1)	2025.05.23
[ 백준 24060번 문제 ] 알고리즘 수업 - 병합 정렬 1 - JAVA (2)	2025.05.21

이번에는 백준 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);

    }
}

'백준 단계별 풀이' 카테고리의 다른 글

[ 백준 2438번 문제 ] 별 찍기 - 1 - JAVA (1)	2025.06.10
[ 백준 15652번 문제 ] N과 M (4) - JAVA (1)	2025.05.29
[ 백준 15650번 문제 ] N과 M (2) - JAVA (1)	2025.05.23
[ 백준 24060번 문제 ] 알고리즘 수업 - 병합 정렬 1 - JAVA (2)	2025.05.21
[ 백준 4779번 문제 ] 칸토어 집합 - JAVA (0)	2025.04.03

이번에는 백준 15650번 문제를 통해 백트래킹 알고리즘 학습을 강화해 보자.
저번 15649번 문제에서 살짝 변형된 문제이다.

문제 핵심

1부터 N까지의 자연수 중 중복 없이 M개를 고른 수열
1 <= M <= N < 8
오름차순이여야 한다.

풀이 과정

저번에는 모든과정을 체크했다면 이번 문제는 앞에 숫자가 커짐에 따라 끝의 숫자의 개수가 작아지므로 ( 즉, 오름차순이므로 ) 앞에 숫자 기준으로만 생각하면 된다. 다음 그림과 같이 진행된다. N = 4, M = 2 기준

1. 배열 첫 번째 요소를 채워 넣는다.

2. 두번 째 요소를 넣기 위해 다시 함수를 호출하여 1-1로 진행한다.

3. 두번 째 요소를 넣은 후 다시 함수를 호출하고 깊이와 M값이 같기 때문에 출력한 후 반환한다.

4. 1-1 안에 배열에서 i 값이 증가한 1-2 와 같이 진행되어 이를 N값 전까지 반복한다.

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 + 1);
    }
}

오랜만에 뵙습니다. 취준 준비중 생활적 요소가 부족하여
두달가량 일용직 근무를 다녀왔습니다.
다시 천천히 시작해 보려고 합니다. 기다려 주셔서 감사합니다.

전체 코드

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 + 1);
        }
    }


    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);

    }
}

'백준 단계별 풀이' 카테고리의 다른 글

[ 백준 15652번 문제 ] N과 M (4) - JAVA (1)	2025.05.29
[ 백준 15651번 문제 ] N과 M (3) - JAVA (1)	2025.05.24
[ 백준 24060번 문제 ] 알고리즘 수업 - 병합 정렬 1 - JAVA (2)	2025.05.21
[ 백준 4779번 문제 ] 칸토어 집합 - JAVA (0)	2025.04.03
[ 백준 15649번 문제 ] N과 M (1) - JAVA (1)	2025.03.24

이번에는 백준 24060번 문제를 통해 병합 정렬 개념을 다시 다져보자.
이번 문제도 저번 개념 정리와 같이 재귀 방식으로 계속 나누고
병합하며 정렬한다.

[ 알고리즘 ] 병합 정렬 - JAVA

백준 24060번 문제를 풀기 전에 병합 정렬 알고리즘의 로직에 대해아주 자세히 포스팅 해보려 한다. 사실 이미지로 본다면 아주 쉬운데 이걸 구현하고자 하면 머리가 아플 수도 있다. 때문에 이

p-coding.tistory.com

🔍 문제 핵심

병합 정렬은 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 방법을 사용한다.
주어진 배열을 계속해서 절반으로 나누고, 더 이상 나눌 수 없을 때까지 나눈 뒤, 정렬된 상태로 병합한다.
문제에서 예시로 주어진 병합 정렬 과정을 잘 이해하고, 이를 직접 구현해보는 것이 핵심이다.

📌 병합 정렬이란?

1. 분할 (Divide)

배열을 절반으로 나눈다.
이 과정을 배열의 크기가 1이 될 때까지 반복한다.
각 하위 배열은 재귀적으로 처리된다.

2. 정복 (Conquer)

크기가 1인 배열끼리 **두 개씩 병합(Merge)**하며 정렬해나간다.
병합 과정에서 두 배열의 원소를 비교하여 작은 값을 먼저 넣는 방식으로 정렬이 이루어진다.

3. 병합 (Combine)

정렬된 두 배열을 하나로 합치며 정렬을 유지한다.

재귀 방식으로 정렬하는 복잡한 구조로 공부하기 좋은 문제이다.
이해도를 높이기 위해 많은 관련 문제를 푸는 것을 추천한다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private static int count = 0;
    private static int number = -1;
    private static int K;

    private static void mergeSort(int[] arr, int left, int right) {
        if(left < right) {
            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {

        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1;
        int z = 0;

        while(i <= mid && j <= right) {
            if(arr[i] <= arr[j]) {
                temp[z++] = arr[i++];
            }
            else {
                temp[z++] = arr[j++];
            }

        }

        while(i <= mid) {
            temp[z++] = arr[i++];
        }

        while(j <= right) {
            temp[z++] = arr[j++];
        }


        for (int l = 0; l < temp.length; l++) {
            arr[left + l] = temp[l];
            count++;
            if(count == K) {
                number = temp[l];
            }
        }


    }

    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());
        K = Integer.parseInt(stringTokenizer.nextToken());

        int[] arr = new int[N];

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        mergeSort(arr, 0, N - 1);

        System.out.println(number);

    }
}

'백준 단계별 풀이' 카테고리의 다른 글

[ 백준 15651번 문제 ] N과 M (3) - JAVA (1)	2025.05.24
[ 백준 15650번 문제 ] N과 M (2) - JAVA (1)	2025.05.23
[ 백준 4779번 문제 ] 칸토어 집합 - JAVA (0)	2025.04.03
[ 백준 15649번 문제 ] N과 M (1) - JAVA (1)	2025.03.24
[ 백준 26069번 문제 ] 붙임성 좋은 총총이 - JAVA (1)	2025.03.12

요즘 시험이니 일이니 핑계 거리가 생겨 포스팅이 많이 늦어졌습니다.
다시 매일 노력하여 포스팅 하도록 노력하겠습니다. 감사합니다.

이번에는 백준 15649번 문제를 통해 백트래킹 알고리즘을 실습해 보자.

백트래킹이란 간단히 설명하면
가능한 모든 경로 탐색 중 조건이 맞지 않으면 이전 단계로 돌아가 다시 탐색하는 알고리즘이다.

문제 핵심

1부터 N까지의 자연수 중 중복 없이 M개를 고른 수열
1 <= M <= N < 8

풀이 과정

반복과 재귀를 통해 깊이에 따라 값을 처리한다.

dfs를 참고할 수 있겠다.

핵심 코드

현재 깊이를 체크한다.
1. 최대 깊이에 도달한다면 리스트 값을 저장하고 리턴한다.
반복문을 통해 방문되지 않은 리스트 요소를 특정하여 방문한다.
리스트 현재 깊이 인덱스에 값을 저장한다.
재귀를 통해 다음 깊이로 이동한다.
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를 통해 이전으로 돌아온다.
1. 이 때 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);
    }
}

'백준 단계별 풀이' 카테고리의 다른 글

[ 백준 24060번 문제 ] 알고리즘 수업 - 병합 정렬 1 - JAVA (2)	2025.05.21
[ 백준 4779번 문제 ] 칸토어 집합 - JAVA (0)	2025.04.03
[ 백준 26069번 문제 ] 붙임성 좋은 총총이 - JAVA (1)	2025.03.12
[ 백준 25192번 문제 ] 인사성 밝은 곰곰이 - JAVA (2)	2025.03.09
[ 백준 1010번 문제 ] 다리 놓기 - JAVA (2)	2025.03.08

java

문제 핵심

풀이 과정

전체 코드

'백준 단계별 풀이' 카테고리의 다른 글

문제 핵심

풀이 과정

전체 코드

'백준 단계별 풀이' 카테고리의 다른 글

문제 핵심

풀이 과정

전체 코드

'백준 단계별 풀이' 카테고리의 다른 글

문제 핵심

풀이 과정

전체 코드

'백준 단계별 풀이' 카테고리의 다른 글

문제 핵심

풀이 과정 1

풀이 과정 2

전체 코드 1

전체 코드 2

'백준 단계별 풀이' 카테고리의 다른 글

문제 핵심

풀이 과정

핵심 코드

전체 코드

'백준 단계별 풀이' 카테고리의 다른 글

문제 핵심

풀이 과정

핵심 코드

전체 코드

'백준 단계별 풀이' 카테고리의 다른 글

문제 핵심

풀이 과정

전체 코드

'백준 단계별 풀이' 카테고리의 다른 글

🔍 문제 핵심

📌 병합 정렬이란?

1. 분할 (Divide)

2. 정복 (Conquer)

3. 병합 (Combine)

전체 코드

'백준 단계별 풀이' 카테고리의 다른 글

문제 핵심

풀이 과정

핵심 코드

EX) N : 4, M : 2

전체 코드

'백준 단계별 풀이' 카테고리의 다른 글

티스토리툴바