2022.09.29 목 - 순열, 조합

📄 학습내용

알고리즘에서 자주 사용되는 수학적 개념

• 최대공약수(GCD) : 공약수 중 가장 큰 수(공약수 : 두 수의 공통된 약수)
  • 유클리드 호제법
    A>B인 두 자연수 A, B가 주어졌을 때, a%b = r이라고 한다면 A, B의 최대공약수 GCD(A, B)는 다음과 같다.
    이때 r=0 일 때 B가 GCD(A, B)의 값이다.

GCD(A, B) = GCD(B, r)

 

// 재귀 - 최대공약수
int GCD(int A, int B) {
    if(A%B == 0) return B;
    return GCD(B, A%B);
}

// 반복문 - 최대공약수
int GCD(int A, int B) {
    while(B != 0) {
        int r = A%B;
        A = B;
        B = r;
    }
    
    return A;
}

• 최소공배수(LCM) : 공배수 중 가장 작은 수(공배수 : 두 수의 공통된 배수)
  • 두 수의 곱 / 최대공약수

// 최소공배수
int LCM(int A, int B) {
    return (A*B) / GCD(A,B);
}

• 순열 : m개 중 n를 선택할 때 순서를 고려한 경우의 수

// m : resource.length, n : count
// resource : 집합
// list : 순열
// m개 중 n개 선택
ArrayList<String[]> permutation(ArrayList<String[]> list, String[] resource, int count, boolean[] visited, int depth, String[] str) {
    // Base Case :
    if(count == depth) {
        list.add(str);
        return list;
    }

    // Recursive Case :
    for(int i=0; i<resource.length; i++) {
        if(visited[i] == false) { // 방문하지 않은 경우
            visited[i] = true; // 방문
            String[] inputClone = str.clone(); // 깊은 복사
            inputClone[depth] = resource[i]; // // 방문한 것을 input에 넣기
            list = permutation(list, resource, count, visited, depth+1, inputClone);
            visited[i] = false; // 다시 방문할 수 있도록 원래 값으록 되돌리기
        }
    }

    return list;
}


// 사용 예시
String[] resource = {"A", "B", "C"};
boolean[] visited = new boolean[resource.length];
int count = 3;
ArrayList<String[]> list = new ArrayList<>();
list = permutation(list, resource, count, visited, 0, new String[count]);
list.stream().forEach(s -> System.out.println(Arrays.toString(s)));
/*
[A, B, C]
[A, C, B]
[B, A, C]
[B, C, A]
[C, A, B]
[C, B, A]
*/

• 조합 : m개 중 n를 선택할 때 순서를 고려하지 않은 경우의 수 

// m : resource.length, n : count
// resource : 집합
// list : 조합
// m개 중 n개 선택
ArrayList<String[]> combination(ArrayList<String[]> list, String[] str, int count, String[] resource) {
    // Base Case :
    if(count == 0) {
        list.add(str);
        return list;
    }
    if(resource.length == 0) return list;

    // Recursive Case :
    for(int i=0; i<resource.length; i++) {
        String[] subCards = Arrays.copyOfRange(resource, i+1, resource.length);
        String[] subStr = Arrays.copyOf(str, str.length+1);
        subStr[str.length] = resource[i];

        combination(list, subStr, count-1, subCards);
    }

    return list;
}

// 사용 예시
String[] resource = {"A", "B", "C"};
int count = 2;
ArrayList<String[]> list = new ArrayList<>();
list = combination(list, new String[]{}, count, resource);
list.stream().forEach(s -> System.out.println(Arrays.toString(s)));
/*
[A, B]
[A, C]
[B, C]
*/

• 멱집합 : 어떤 집합의 모든 부분 집합으로 구성된 집합

// resource : 집합
// list : 멱집합
ArrayList<String[]> powerSet(ArrayList<String[]> list, String[] str, String[] resource) {
    // Base Case :
    if(resource.length == 0) {
        list.add(str);
        return list;
    }

    // Recursive Case :
    for(int i=0; i<resource.length; i++) {
        String[] subSideDishes = Arrays.copyOfRange(resource, i+1, resource.length);
        String[] subStr = str.clone();
        if(resource[i] != null) {
            subStr = Arrays.copyOf(str, str.length+1);
            subStr[str.length] = resource[i];
        }
        powerSet(list, subStr, subSideDishes);
    }

    return list;
}

// 사용 예시
String[] resource = {"A", "B", "C", null};
ArrayList<String[]> list = new ArrayList<>();
list = powerSet(list, new String[]{}, resource);
list.sort((o1, o2) -> Arrays.toString(o1).compareTo(Arrays.toString(o2))); // 오름차순 정렬
list.stream().forEach(s -> System.out.println(Arrays.toString(s)));
/*
[A, B, C]
[A, B]
[A, C]
[A]
[B, C]
[B]
[C]
[]
*/

list.sort((o1, o2) -> o1.length < o2.length ? 1 : -1); // 크기순 정렬
list.stream().forEach(s -> System.out.println(Arrays.toString(s)));
/*
[A, B, C]
[B, C]
[A, C]
[A, B]
[C]
[B]
[A]
[]
*/

 

정규표현식

• 특정한 규칙을 통해서 문자열을 표현하는 형식 언어
• 생성한 정규표현식을 확인하는 웹페이지
  • https://www.regexplanet.com/advanced/java/index.html
  • https://regexr.com/

 

 

🧶 발생한 문제 및 해결방법

• 문제점) ArrayList<String[]>을 정렬하는 방법
• 해결방법) String 배열을 String으로 변경해서 비교하기

ArrayList<String[]> list = new ArrayList<>();
list.add(new String[]{"c", "a", "b"});
list.add(new String[]{"a", "b", "c"});
list.add(new String[]{"b", "c", "a"});
list.sort((o1, o2) -> Arrays.toString(o1).compareTo(Arrays.toString(o2))); // 오름차순 정렬
list.stream().forEach(str -> System.out.println(Arrays.toString(str))); // 출력

/*
[a, b, c]
[b, c, a]
[c, a, b]
*/

 

⭐ 공부 난이도

조합, 순열 구현 ☆☆★★★

 

🎡 페어리뷰

 

🌕 느낀점

  이번 페어 활동에서는 코드리뷰하는 형식으로 진행하였다. 시간 계산을 잘못 계산해서 1시간30분 동안 코드리뷰하는 것이 아니라 30분밖에 코드리뷰하지 못했다. 상대방이 어떻게 문제를 풀었는지 궁금했고, 그 풀이과정을 듣는 것이 상당히 흥미로웠는데 너무 아쉬웠다. 한 문제에 빠지면 그 문제를 풀 때까지 시간을 온전히 쓰는 것이 상당히 문제인 것 같다. 적당히 해결하고 나와야하는데 몰입되면 빠져나오는 것이 쉽지 않다.