28일차: 알고리즘 with Math(순열, 조합)

❯ 순열(Permutation)과 조합(Combination)

알고리즘 문제를 풀기 위해서는, 일부 수학적인 개념이 필요하다.

순열이란, 요소 n개 중에서 m개를 선택하여 순서에 상관있게 뽑는 경우의 수를 말한다.

조합이란, 순서에 상관 없이 요소 n개 중에서 m개를 뽑는 경우의 수를 말한다.

순열과 조합은 반복문의 중첩을 통해 구현할 수 있으나 뽑아야하는 경우의 수가 많아지면

반복문을 사용하는것이 비효율적이다.

 

따라서 재귀함수를 통해서 구현할 수 있다.

다만, 재귀함수를 작성할때는 필요한 매개변수가 어떤것이 있을지 잘 생각해보는것이 중요하다.

(재귀함수를 재호출하면서 변수가 초기화 되지 않도록)

 

<예시> 순열을 사용해 뽑은 숫자 중 소수 개수 계산하기

import java.util.ArrayList;

// n 개의 숫자카드중에서 m개를 뽑아서 m자리 숫자들을 만들고
// 해당 숫자들 중 소수가 몇개인지 찾아내는 알고리즘 작성하기
public class Permutation {
    public static void main(String[] args) {
        int[] numbers = new int[]{1,2,3,4,5};
        System.out.println(countPrime(numbers,3));
        // 결과는 7개 (241,251,421,431,521,523,541)
    }

    private static int countPrime(int[] numbers, int picks) {
        boolean[] used = new boolean[numbers.length];
        ArrayList<Integer> answers = new ArrayList<>();
        Integer items =0;
        int count = 0;

        ArrayList<Integer> list = permutation(answers, items, numbers, picks, used);

        for (int i = 0; i < list.size(); i++) {
            if (isPrime(list.get(i))) {
                count++;
            }
        }
        return count;
    }


    // 깊이우선탐색으로 수행
    private static ArrayList<Integer> permutation(ArrayList<Integer> answers, Integer items, int[] numbers, int picks, boolean[] used) {
        if (picks == 0) {  // 재귀함수 탈출조건 설정
            answers.add(items);
            return answers;
        }

        // 해당 숫자들 목록 구해서 answers에 넣기
        for (int i = 0; i < numbers.length; i++) {
            if (!used[i]) {
                Integer addNum = numbers[i];
                used[i] = true;
                Integer changedItems = items * 10 + addNum;
                answers = permutation(answers, changedItems, numbers, picks - 1, used);
                used[i] = false; // 다음 반복문으로 돌아갈때는 사용여부를 다시 리셋해주어야함
            }
        }
        return answers;
    }
    // 소수인지 판별하는 메서드
    private static boolean isPrime(Integer n) {
        if (n == 2) return true;
        if (n % 2 == 0 || n == 1) return false;
        for (int i = 3; i < Math.sqrt(n); i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

▼ countPrime 을 별도로 작성하지 않고 premutation 에 넣어서 바로 계산도 가능하다.

public class Permutation {
    public static void main(String[] args) {
        int[] numbers = new int[]{1,2,3,4,5};
        System.out.println(permutation(0, numbers,3, new boolean[numbers.length], 0));
        // 결과는 7개 (241,251,421,431,521,523,541)
    }


    // 깊이우선탐색으로 수행
    private static int permutation(Integer items, int[] numbers, int picks, boolean[] used, int count) {
        if (picks == 0) {  // 재귀함수 탈출조건 설정
            if(isPrime(items)){
            count++;
            return count;}
        }

        // 해당 숫자들 목록 구해서 count에 넣기
        for (int i = 0; i < numbers.length; i++) {
            if (!used[i]) {
                Integer addNum = numbers[i];
                used[i] = true;
                Integer changedItems = items * 10 + addNum;
                count = permutation(changedItems, numbers, picks - 1, used, count);
                used[i] = false; // 다음 반복문으로 돌아갈때는 사용여부를 다시 리셋해주어야함
            }
        }
        return count;
    }
    // 소수인지 판별하는 메서드
    public static boolean isPrime(Integer n) {
        if (n == 2) return true;
        if (n % 2 == 0 || n == 1) return false;
        for (int i = 3; i < Math.sqrt(n); i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

---

알고리즘과 관련해서 순열, 중복순열, 최소공배수/최대공약수, 멱집합과 관련된 문제들을 풀어보았다.

확실히 '수학적 사고'가 필요하다는게 느껴졌고 문제의 요구사항을 정확히 파악하는것이 중요하다는걸 깨달았다.

해당 부분은 꾸준히 문제들을 풀어보면서 키워나가야겠다.