[백준] N과 M

[CMSSKKK]

TITLE

N과 M 1~12

백트랙킹 기초 다시 잡기

LINK

• 문제 출처 사이트 : 백준
• Link

📷 Screenshots

댓글 양식

• 아래 양식을 복사한 뒤 [shift]+[tab] 2회를 하고 작성하여 주세요

    ### 풀이 언어

    - python/java

    ### 코드

    ```python/java

    ```

    ### 핵심 로직 혹은 자료구조

    - 

    ### 시간 복잡도

    - O(  )

[CMSSKKK]

N과 M (1)

풀이 언어

• java

코드

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

public class Main {

    private static int n;
    private static int k;
    private static StringBuilder sb;

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

        int[] arr = new int[k];
        boolean[] check = new boolean[n];
        sb = new StringBuilder();
        dfs(check, 0, arr);

        System.out.println(sb);

    }

    private static void dfs(boolean[] check, int count, int[] arr) {

        if(count == k) {
            for (int i = 0; i < k; i++) {
                sb.append(arr[i]).append(" ");
            }
            sb.append('\n');
            return;
        }

        for (int i = 0; i < n; i++) {
            if(!check[i]) {
                arr[count] = i + 1;
                check[i] = true;
                dfs(check, count + 1, arr);
                check[i] = false;
            }

        }
    }

}

핵심 로직 혹은 자료구조

시간 복잡도

• O( )

[CMSSKKK]

N과 M(2)

풀이 언어

• java

코드

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

public class Main {

    private static int n;
    private static int m;
    private static StringBuilder sb;

    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());
        sb = new StringBuilder();

        int[] arr = new int[m];
        dfs(1, arr,0);

        System.out.println(sb);

    }

    private static void dfs(int curr, int[] arr,  int depth) {

        if (depth == m) {
            for (int i : arr) {
                sb.append(i).append(" ");
            }
            sb.append('\n');
            return;
        }

        for (int i = curr; i <= n; i++) {
            arr[depth] = i;
            dfs(i + 1, arr, depth + 1);
        }
    }

}

핵심 로직 혹은 자료구조

시간 복잡도

• O( )

[CMSSKKK]

N과 M(3)

풀이 언어

• java

코드

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

public class Main {

    private static int n;
    private static int m;
    private static StringBuilder sb = new StringBuilder();

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

        int[] arr = new int[m];

        dfs(0, arr);
        System.out.println(sb);
    }

    private static void dfs(int depth, int[] arr) {

        if(depth == m) {
            for (int i : arr ) {
                sb.append(i).append(" ");
            }
            sb.append('\n');
            return;
        }

        for (int i = 1; i <= n; i++) {
            arr[depth] = i;
            dfs(depth + 1, arr);
        }
    }

}

핵심 로직 혹은 자료구조

시간 복잡도

• O( )

[nathan29849]

N과 M (1)

풀이 언어

• python

코드

import sys

input = sys.stdin.readline
n, m = list(map(int, input().split()))
global result
global numbers
result = []
numbers = [i for i in range(1, n+1)]
visited = [0] * n


def comb(arr: list, visited: list, r: int)->None:
    if len(arr) == r:
        result.append(arr)
        return
    
    for i in range(len(visited)):
        if visited[i] == 0:
            visited[i] = 1
            tmp = arr[:]
            tmp.append(numbers[i])
            comb(tmp, visited, r)
            visited[i] = 0

comb([], visited, m)
for tmp in result:
    for t in tmp:
        print(t, end=" ")
    print()

핵심 로직 혹은 자료구조

• 백트래킹

시간 복잡도

• O( )

[nathan29849]

N과 M(2)

풀이 언어

• python

코드

import sys

input = sys.stdin.readline
n, m = list(map(int, input().split()))
global result
global numbers
result = []
numbers = [i for i in range(1, n+1)]
visited = [0] * n


def comb(arr: list, visited: list, r: int)->None:
    if len(arr) == r:
        result.append(arr)
        return
    
    for i in range(len(visited)):
        if visited[i] == 0:
            if arr:
                if arr[-1] > numbers[i]:
                    continue
            
            visited[i] = 1
            tmp = arr[:]
            tmp.append(numbers[i])
            comb(tmp, visited, r)
            visited[i] = 0

comb([], visited, m)
for tmp in result:
    for t in tmp:
        print(t, end=" ")
    print()

핵심 로직 혹은 자료구조

• 백트래킹

시간 복잡도

• O( )

[CMSSKKK]

N과 M(4)

풀이 언어

• java

코드

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

public class Main {

    private static int n;
    private static int m;
    private static StringBuilder sb = new StringBuilder();

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

        int[] arr = new int[m];

        dfs(1, 0, arr);
        System.out.println(sb);
    }

    private static void dfs(int curr, int depth, int[] arr) {

        if(depth == m) {
            for (int i : arr ) {
                sb.append(i).append(" ");
            }
            sb.append('\n');
            return;
        }

        for (int i = curr; i <= n; i++) {
            arr[depth] = i;
            dfs(i,depth + 1, arr);
        }
    }

}

핵심 로직 혹은 자료구조

시간 복잡도

• O( )

[CMSSKKK]

N과 M(5)

풀이 언어

• java

코드

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

public class Main {

    private static int n;
    private static int m;
    private static StringBuilder sb = new StringBuilder();
    private static int[] arr;
    
    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());
        st = new StringTokenizer(br.readLine());
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] temp = new int[m];

        Arrays.sort(arr);

        dfs(temp, new boolean[n], 0);
        System.out.println(sb);

    }

    private static void dfs(int[] temp, boolean[] check, int depth) {

        if(depth == m) {
            for (int i : temp) {
                sb.append(i).append(" ");
            }
            sb.append('\n');
            return;
        }

        for (int i = 0; i < n; i++) {
            if(!check[i]) {
                temp[depth] = arr[i];
                check[i] = true;
                dfs(temp, check, depth + 1);
                check[i] = false;
            }
        }
    }
}

핵심 로직 혹은 자료구조

시간 복잡도

• O( )

[nathan29849]

N과 M(3)

풀이 언어

• python

코드

# 중복 순열 4524ms
import sys
input = sys.stdin.readline
n, m = list(map(int, input().split()))

global numbers
global answer
numbers = [i for i in range(1, n+1)]
answer = list()
def comb(arr: list, r: int)->None:
    if len(arr) == r:
        answer.append(arr)
        return

    for i in range(len(numbers)):
        tmp = arr[:]
        tmp.append(numbers[i])
        comb(tmp, r)
            
comb([], m)
for i in range(len(answer)):
    for j in range(m):
        print(answer[i][j], end=" ")
    print()

핵심 로직 혹은 자료구조

• 백트래킹/중복순열

시간 복잡도

• O( )

[nathan29849]

N과 M(4)

풀이 언어

• python

코드

# 중복 순열
import sys
input = sys.stdin.readline
n, m = list(map(int, input().split()))

global numbers
global answer
numbers = [i for i in range(1, n+1)]
answer = list()
def comb(arr: list, r: int)->None:
    if len(arr) == r:
        answer.append(arr)
        return

    for i in range(len(numbers)):
        if arr:
            if arr[-1] > numbers[i]:
                continue
        tmp = arr[:]
        tmp.append(numbers[i])
        comb(tmp, r)
            
comb([], m)
for i in range(len(answer)):
    for j in range(m):
        print(answer[i][j], end=" ")
    print()

핵심 로직 혹은 자료구조

• 백트래킹/중복순열

시간 복잡도

• O( )

[nathan29849]

N과 M(5)

풀이 언어

• python

코드

import sys
input = sys.stdin.readline
n, m = list(map(int, input().split()))
global numbers
global result
numbers = list(map(int, input().split()))
visited = [0] * len(numbers)
result = []

def comb(arr: list, visited:list, r: int)->None:
    if len(arr) == r:
        result.append(arr)
        return

    for i in range(len(numbers)):
        if not visited[i]:
            visited[i] = 1
            tmp = arr[:]
            tmp.append(numbers[i])
            comb(tmp, visited, r)
            visited[i] = 0
comb([], visited, m)
result.sort()
for r in result:
    for i in r:
        print(i, end=" ")
    print()

핵심 로직 혹은 자료구조

• 백트래킹/순열

시간 복잡도

• O( )