승봉's 블로그

[JAVA] 조합(Combination)

부르트포스 유형의 알고리즘을 풀다보면 n개 중에 r개를 뽑아 일일이 함수를 실행해서 결과값을 찾는 문제가 자주 나온다. 이때 조합 함수를 정의하여 사용하며, 기본 형식은 아래와 같다.

void combination(int arr[], int index, int n, int c, int target);

위 함수는 조합의 아래의 기본 공식을 이용한다.

​ = ​ + ​

예를 들어 ​ 인 경우, (1,2) (1,3) (1,4) / (2,3) (2,4) (3,4) 의 경우가 존재하는데

1을 선택하는 경우와 1을 선택하지 않은 경우로 나눌 수 있다.

• 1을 선택하는 앞의 경우에는 1을 이미 선택했으므로, 나머지 3개 중 1개를 고르는 ​ 이 남은 것이고,

• 1을 선택하지 않은 경우는 1을 선택하지 않았았으므로, 나머지 중에 2개를 고르는 ​가 남는 것이다.

즉, ​ = ​ + ​ 가 된다.

위 공식을 이용해 조합의 개수를 구하는 함수는 아래와 같다.

int combi(int n, int r){
  if(r==0 || r==n)
      return 1;
   else
       return combi(n-1, r-1) + combi(n-1, r);
}

조합의 개수를 구하는 것이라 경우의 수 각각을 구하는 함수는 아래와 같다.

java

    static void combi(int[] arr, int index, int n, int r, int target) {
        if(r==0) {
            for(int i=0; i<arr.length; i++)
                System.out.print(arr[i] + " ");
            System.out.println();
        }else if(target == n) {
            return;
        }else {
            arr[index] = target;
            combi(arr, index+1, n, r-1, target+1);
            combi(arr, index, n, r, target+1);
        }
    }

arr[] 은 조합으로 고른 원소가 들어가 있는 배열이다. 배열의 크기는 r과 동일해야 한다.

• 예를 들어 ​의 경우는 arr[] 이 {1, 2}, {1, 3} , ... , {3, 4} 의 원소를 갖고 있을 때 if(r==0) 부분이 실행된다. 해당 조합을 가지고 어떤 기능을 수행할 때에는 arr을 인자로 보내는 함수를 여기서 수행하면 된다.

• int n, int r 은 ​ 의 n, r이 들어가면 된다.

• index는 구한 원소의 개수를 의미한다. 즉, 위처럼 해당 원소를 선택한 경우는 하나의 원소가 선택되었으므로 idnex+1로 인자를 보내주고, r-1개를 뽑으면 되므로 , r-1을 인자로 보내준다. 해당원소를 선택하지 않은 경우는 Index가 그대로 유지되며, r도 그대로 유지된다. (이때는 target만 1 증가한다.)

• target은 몇부터 원소를 선택할지를 의미한다. 예를 들어 ​의 경우를 예로 들 때 target = 1은 (1,2) (1,3) (1,4) 를 말하며, target=2일 경우에는 (2,3) (2,4) .. 를 말한다. index의 원소를 선택하거나 안하거나를 결정했으므로, target을 1 증가시켜준다.

• 
  

combination 함수에서는 (0,1,2) (2,3,4).. 등과 같이 자연수 n의 조합을 출력하므로, 2차원 배열의 좌표와 같은 경우에는 (x,y)를 갖는 객체 리스트를 만들어 놓은 다음 combination 함수를 이용해 자연수 조합을 배열 arr로 받은 다음 이 배열을 리스트에 접근하는 원소로 사용할 수 있다.

소스코드 :

ArrayList<Pos> virus_list = new ArrayList();
for(int i=1; i<=N; i++)
    for(int j=1; j<=M; j++)
        if(map[i][j] == 2) {// 바이러스일 경우 바이러스리스트에 넣기 
            virus_list.add(new Pos(i, j));
            
/*....*/
//virus_list 중 3개를 선택하는 경우
combination(new int[3], 0, virus_list.size(), 3, 0);
    

static void combination(int arr[], int index, int n, int r, int target) {
        if(r == 0) {
            // 좌표 조합 (x,y) 출력
            for(int i=0; i<arr.length; i++) 
                System.out.print("(" + virus_list.get(arr[0]).x + "," 
                                 +  virus_list.get(arr[0]).y + ")");
            System.out.println();
        }else if(target == n) {
            return;
        }else {
            arr[index] = target;
            combination(arr, index+1, n, r-1, target+1 );
            combination(arr, index, n, r, target+1);
        }
    }

ArrayList를 배열로 바꾸는 방법.

이때 타입을 int 가 아니라 Integer로 선언해주어야 한다.

ArrayList<Integer> int_list = new ArrayList();
Integer arr[] = int_list.toArray(new Integer[int_list.size()]);
​
ArrayList<String> string_list = new ArrayList();
String arr_2[] = string_list.toArray(new String[string_list.size()]);
​

[JAVA] 입력 클래스

입력의 범위가 주어지지 않은 경우

백준 5639 문제(https://www.acmicpc.net/problem/5639)를 풀다 입력의 개수가 주어지지 않고 입력이 끝날 때 까지 입력을 받아 처리해야하는 경우를 보았다.

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
for(int i=0; i<N; i++){
    /*입력받는 코드*/
}

대부분 Scanner를 이용한 위와 같은 방법으로 입력을 처리했기 때문에 java에서 입력을 처리하는 다른 방법을 알아야할 필요성을 느끼게 되었다.

java의 키보드 입력받는 방법

자바에서 키보드의 입력을 받아 처리하는 방법은 크게 두 가지가 있다.

1) Scanner를 이용하는 방법

2) BufferedReader를 이용하는 방법 - 한 줄 단위로 버퍼에서 읽을 수 있는 readLine() 함수가 있으므로, 공백 단위로 입력이 들어올 때에는 StringTokenizer를 이용하여 각각의 문자열을 처리한다.

-> Scanner는 이용은 편리하나, 입력이 여러개가 되면 그 때마다 sc.next~() 함수를 실행해줘야하므로 시간이 많이 소요된다는 단점이 있다.

Scanner의 hasNext() 메소드

• boolean hasNext() 메소드는 읽어들일 요소가 있는 여부를 반환한다.

  • hasNext()로 읽어들일 수 있는 입력이 있다면 true를, 그렇지 않다면 false를 반환한다.

  • 예제는 아래와 같다.

  Scanner sc = new Scanner(System.in);
  ArrayList<Integer> arr = new ArrayList<>();
  ​
  while(sc.hasNext()){
      arr.add(sc.nextInt());
  }
  ​
  for(int i=0; i<arr.size(); i++)
      System.out.println(arr.get(i));

BufferedReader을 이용한 입력 처리

• BufferedReader는 문자(char)단위로 읽어들이는 InputStreamreader에 버퍼링 기능을 추가한 것으로, 한 번에 입력을 받아들여 버퍼에 저장한 후 사용자가 요구할 때 버퍼에서 읽어온다.

• 예외를 던질 수 있는 BufferedReader를 사용하기 위해서는 예외를 처리해 주어야한다. (try-catch문 사용 / throw IOException)

백준 15552 : 빠른 A+B 문제

BufferedReader를 이용해 입력을 받고 BufferedWriter를 이용해 결과를 출력하는 문제

1) 먼저 두 객체를 생성해준다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

2) BufferedReader를 이용하면 전체의 입력이 버퍼에 저장되므로, 버퍼에서 한 줄씩 읽어오는 readLine() 메소드를 이용한다.

해당 문제에서는 A+B 2개를 입력받기 때문에 String으로 읽고, split함수를 이용해 나눠주었다.

String line = in.readLine();
nums = line.split(" ");
int result = Integer.parseInt(nums[0]) + Integer.parseInt(nums[1]);

3) 결과값을 버퍼에 쓴다.

버퍼에 String 값을 쓰는 wirte() 메소드와 개행문자(\n)를 입력하는 newLine() 메소드를 이용하였다.

out.write(String.valueOf(result));
out.newLine();

4) 버퍼에 쓴 값을 콘솔에 출력하고, BufferedReader와 BufferedWrite를 닫아준다.

out.flush();
in.close();
out.close();

[전체코드]

import java.io.*;
​
public class Main {
​
    public static void main(String[] args) throws IOException {
​
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int testcase = Integer.parseInt(in.readLine());
​
        while(testcase > 0){
            String nums[] = new String[2];
            String line = in.readLine();
            nums = line.split(" ");
​
            int result = Integer.parseInt(nums[0]) + Integer.parseInt(nums[1]);
            out.write(String.valueOf(result));
            out.newLine();
​
            --testcase;
        }
​
        out.flush();
        in.close();
        out.close();
    }
}

---

Scanner를 입력하는 것과 BufferdReader를 이용하는 것의 시간차이가 많으므로 앞으로는 BufferedReader를 이용하는 방법으로 코드를 짜야겠다!

[JAVA] 이진 탐색 트리

이진 탐색 트리란?

이진 탐색 트리(Binary Search Tree)란 부모노드의 값을 기준으로하여 더 작은 값은 왼쪽 자식노드에, 더 큰 값은 오른쪽 자식노드에 이어지는 트리의 형태를 말한다. 탐색하고자 하는 값이 있을 때에는 현재 노드를 중심으로 더 가까운 값들만 골라서 탐색하게 되므로 시간복잡도에서 유리한 시간을 갖는다.

또한 루트노드를 기준으로 자식노드가 연결되므로, 노드가 입력되는 순서에 따라 트리의 모양이 달라진다는 특징을 가진다.

트리 구현

먼저 처음 입력값으로 루트노들르 만들고 그 뒤부터는 노드와의 값을 비교해 탐색하는 노드보다 값이크면 오른쪽 자식노드를, 값이 작다면 왼쪽 자식 노드를 탐색한다. 해당 자식노드가 비어있다면 새로운 노드가 그 위치에 들어가게 되고, 그 노드가 존재한다면, 그 자식노드를 중심으로 함수를 재귀호출하는 방법이다. 코드는 아래와 같다.

소스코드

static class TreeNode{
    int value;
    TreeNode left;
    TreeNode right;
    public TreeNode(int v) {value = v;}
}
​
// 자식노드와 부모노드 연결 함수
static void link_node(TreeNode parent, int value){
    // 현재 값이 탐색하고 있는 노드(parent)보다 크다면
    // 오른쪽 자식 노드를 탐색
    if(value > parent.value){
        // 오른쪽 자식 노드가 null 이라면 해당 노드로 연결
        if(parent.right == null){
            TreeNode newNode = new TreeNode(value);
            parent.right = newNode;
        } // 오른쪽 자식 노드가 있다면 해당 노드를 탐색노드로 하여 재귀
        else{
            link_node(parent.right, value);
        }
    }else{ // 값이 더 작다면 왼쪽 자식 노드 탐색
        if(parent.left == null){
            TreeNode newNode = new TreeNode(value);
            parent.left = newNode;
        }else{
            link_node(parent.left, value);
        }
    }
}

트리의 순회

1) 전위순회

• 루트노드 - 왼쪽자식노드 - 오른쪽 자식노드 순으로 탐색하는 방법이다.

• 루트노드를 탐색하고 왼쪽자식노드를 탐색하면 그 단계에서는 왼쪽 자식노드가 루트노드(부모노드)가 되고 그 밑에 있는 자식노드들이 왼쪽자식노드, 오른쪽자식노드가 된다.

// 전위순회 (루트 - 왼 - 오)
static void preorder(TreeNode node){
    System.out.print(node.value);
    if(node.left != null)
        preorder(node.left);
    if(node.right != null)
        preorder(node.right);
}

2) 중위순회

• 왼쪽자식노드 - 루트노드 - 오른쪽자식노드 순으로 탐색하는 방법이다.

// 중위순회 (왼 - 루트 - 오)
static void inorder(TreeNode node){
    if(node.left != null)
        inorder(node.left);
    System.out.print(node.value);
    if(node.right != null)
        inorder(node.right);
}

3) 후위순회

• 왼쪽자식노드 - 오른쪽자식노드 - 루트노드 순으로 탐색하는 방법이다.

// 후위순회 (왼 - 오 - 루트)
static void postorder(TreeNode node){
    if(node.left != null)
        postorder(node.left);
    if(node.right != null)
        postorder(node.right);
    System.out.print(node.value);
}

입력을 받아 트리를 만들고 트리를 순회하는 메인함수는 아래와 같다.

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
​
    TreeNode root = new TreeNode(sc.nextInt());
    for(int i=0; i<N-1; i++)
        link_node(root, sc.nextInt());
​
​
    preorder(root);
    System.out.println();
​
    inorder(root);
    System.out.println();
​
    preorder(root);
    System.out.println();
}

Scanner함수 next(), nextLine() 차이

알고리즘을 풀다보면 예상했던것과 다르게 입력을 받는 경우가 발생한다. 그 중 개행문자('\n')를 먼저 읽어들여 입력한 문자열을 읽어들이지 못하는 경우가 발생한다.

예를 들어,

Scanner sc = new Scanner(System.in);
​
int a = sc.nextInt();
String b = sc.next();
String c = sc.nextLine();
​
System.out.println(a);
System.out.println(b);
System.out.println(c);

위 코드에서의 입력과 출력은 아래와 같다.

그 이유는 next() 함수는 문자단위로 입력을 받으며, nextLine() 함수는 개행문자('\n')가 나올 때 까지의 한 줄을 입력받기 때문이다. 즉, b에서는 문자 그대로 '1234'를 입력받지만, c에서는 1234를 입력하기 전에 입력한 개행문자가 저장이 되는 것이다.

또한 next()는 '문자' 단위로 공백을 입력받지 않고 공백 앞뒤의 문자를 입력받는다. 입출력 예시는 아래와 같다.