조합 알고리즘

Seokwon Han·2021년 1월 26일
0

알고리즘 공부

목록 보기
4/5

문제유형

완전탐색 문제에서 사용하는 조합 알고리즘
프로그래머스의 "메뉴 리뉴얼" 문제를 풀때 사용하였다.

설명

재귀함수를 이용하여 구현할 수 있다.

함수를 재귀적으로 계속 호출하면서
현재 인덱스의 요소를 선택했을때와 선택하지않았을때로 계속 분기하고
원하는 갯수만큼 선택을 했을때는 함수호출을 종료시키는 방식으로 찾는다.

예제코드

class Solution {
    
    public String[] solution(String[] orders, int[] course) {
    	String[] str = {"a", "b", "c"};
        boolean[] visited = new boolean[str.length]
    
    	// str 중 2개만 뽑는경우
    	combination(str, visited, 0, str.length, 2);
    }
    
    // 조합 알고리즘
    public void combination(String[] str, boolean[] visited, int idx, int n, int r) {
        // 조합을 찾았을때
        if (r == 0) {
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    System.out.print(str[i]);
                }
            }
            
            return;
        }
        
        // 또 다른 리턴 조건
        if (idx == n) {
            return;
        }
        
        // 현재 인덱스의 숫자를 선택했을때
        visited[idx] = true;
        combination(str, visited, idx+1, n, r-1);
        
        // 현재 인덱스의 숫자를 선택 안했을때
        visited[idx] = false;
        combination(str, visited, idx+1, n, r);
    }
profile
개발하면서 새로 배우거나 경험한 내용을 정리하고 그 외의 공부한 내용을 기록하는 곳입니다.

0개의 댓글