그리디, 순열, 조합 숙제

[jonggking]

그리디 문제

• https://www.acmicpc.net/problem/11047
• https://www.acmicpc.net/problem/1931
• https://www.acmicpc.net/problem/11399
• https://www.acmicpc.net/problem/1541
• https://www.acmicpc.net/problem/13305

순열과 조합

• N과 M(1) https://www.acmicpc.net/problem/15649
• N과 M(2) https://www.acmicpc.net/problem/15650
• N과 M(3) https://www.acmicpc.net/problem/15651
• N과 M(4) https://www.acmicpc.net/problem/15652
• N과 M(5) https://www.acmicpc.net/problem/15654

이론 : 10월 18일
숙제 : 10월 23일

[kdomo]

그리디(탐욕스러운)

• 탐욕법이란?
  • 전체가 아닌 현재 상태에서 최선의 선택을 하는 알고리즘
  • 전체 탐색보다 빠르지만 반드시 정답을 도출하지 않는다
• 탐욕법의 조건
  • 각 부분에서의 선택이 다른 부분에게 영향을 주지 않는다.
  • 각 부분에서의 최적 해결이 최종 해결방법이다.
• 주의사항
  • 탐욕법이 적용 가능한 문제인지 아닌지를 판별할 수 있어야 한다.
  • 대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
  • 어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지 재차 고민하자.
• 한계
  • 탐욕 알고리즘은 근사치 추정에 활용
  • 반드시 최적의 해를 구할 수 있는 것은 아니다
  • 최적의 해에 가까운 값을 구하는 방법 중의 하나임
    

순열과 조합

• 순열
  • 서로 다른 n개 중 r개를 뽑아서 나열한 것
  • 1~4 중 2개를 뽑는다고 할 때

import java.util.Arrays;

public class Main {
    private static int n, r;
    private static int[] arr; // 원소를 저장할 배열
    private static boolean[] visited; // 중복을 제거하기 위한 방문 처리

    public static void main(String[] args) {
        n = 4;
        r = 2;
        arr = new int[r];
        visited = new boolean[n + 1];
        permutation(0);
    }
    // 순열
    private static void permutation(int cnt) {
        if (cnt == r) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[cnt] = i;
                permutation(cnt + 1);
                visited[i] = false;
            }
        }
    }

    // 중복 순열 - 중복 제거하는 visited를 쓰지 않음
    private static void repeatedPermutation(int cnt) {
        if (cnt == r) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = 1; i <= n; i++) {
            arr[cnt] = i;
            permutation(cnt + 1);
        }
    }
}

// 순열
[1, 2]
[1, 3]
[1, 4]
[2, 1]
[2, 3]
[2, 4]
[3, 1]
[3, 2]
[3, 4]
[4, 1]
[4, 2]
[4, 3]

// 중복 순열
[1, 1]
[1, 2]
[1, 3]
[1, 4]
[2, 1]
[2, 2]
[2, 3]
[2, 4]
[3, 1]
[3, 2]
[3, 3]
[3, 4]　　　　
[4, 1]
[4, 2]
[4, 3]
[4, 4]

• 조합
  • 서로 다른 n개 중 r개를 순서 없이 골라낸 것
  • 1~4 중 2개를 뽑는다고 할 때

import java.util.Arrays;

public class Main {
    private static int n, r;
    private static int[] arr; // 원소를 저장할 배열
    private static boolean[] visited; // 중복을 제거하기 위한 방문 처리

    public static void main(String[] args) {
        n = 4;
        r = 2;
        arr = new int[r];
        visited = new boolean[n + 1];
        combination(0, 1);
    }
    private static void combination(int cnt, int start) {
        if (cnt == r) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = start; i <= n; i++) {
            arr[cnt] = i;
            combination(cnt + 1, i + 1); // 오름차순으로 구하면 중복 체크하지 않아도 됨
        }
    }

    // 중복 조합
    private static void repeatedCombination(int cnt, int start) {
        if (cnt == r) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = start; i <= n; i++) {
            arr[cnt] = i;
            combination(cnt + 1, i); // 중복 허용하니까 비내림차순
        }
    }
}

// 조합
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

// 중복 조합
[1, 1] - 중복
[1, 2]
[1, 3]
[1, 4]
[2, 2]
[2, 3]
[2, 4]
[3, 3]
[3, 4]
[4, 4]

[josuehyeon]

• 탐욕법
  현재 상황에서 가장 좋은 것을 고르는 알고리즘
  순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 수집해서 최정적인 해답을 만들었다고 해서 최적이라는 보장은 없다.

• 순열 - Permutation
  서로 다른 n개에서 r개를 뽑아서 정렬하는 경우의 수

• 중복 순열
  서로 다른 n개에서 중복이 가능하게 r개를 뽑아서 정렬하는 경우의 수

• 조합 - Combination
  서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수

• 중복 조합
  서로 다른 n개에서 순서 없이, 중복이 가능하게 r개를 뽑는 경우의 수

[jonggking]

Greedy Algorithms(탐욕법, 탐욕 알고리즘)

그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식

순열(permutation)과 조합(combination)

순열: 서로 다른 n개 중 r 개를 골라 순서를 고려해 나열한 경우의 수(nCr)

import itertools

arr = ['A', 'B', 'C'] 
nPr = itertools.permutations(arr, 2)
print(list(nPr))

결과 : [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

중복순열: 서로 다른 n개중 중복을 허용해 r개를 골라 순서를 고려해 나열한 경우의수 (n​πr)
product(반복 가능한 객체, repeat=1)

from itertools import product

for i in poduct([1,2,3], 'ab'):
  print(i, end=" ")

결과: [(1, 'a') (1, 'b') (2, 'a') (2, 'b') (3, 'a') (3, 'b') ]

조합: 서로 다른 n개 중 r 개를 골라 순서를 고려하지않고 나열한 경우의 수(nCr)

import itertools

arr = ['A', 'B', 'C']
nCr = itertools.combinations(arr, 2)
print(list(nCr))

결과 : [('A', 'B'), ('A', 'C'), ('B', 'C')]

중복조합: 서로 다른 n개중 중복을 허용해 r개를 골라 순서를 고려하지 않고 나열한 경우의 수(nHr)
conbination_with_replacement(반복 가능한 객체, r)

from itertools import combinations_with_replacement 

for cwr in combinations_with_replacement([1,2,3,4], 2): 
     print(cwr, end=" ")

결과[(1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)]

combinations, permutations, product 세 메소드 모두 generator이기 때문에 list()로 캐스팅하여 다른 곳에 저장 해두지 않으면 한 번의 루핑 이후 사라지게 된다.

from itertools import combinations

_list = range(4)
combi = combinations(_list, 2)
print(list(combi))		# [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
print(list(combi))		

[jiyun828]

그리디 알고리즘

*매 선택에서 "지금 이 순간 당장 최적인 답"을 선택하여 적합한 결과를 도출하자.

단, 그리디 알고리즘을 사용하면 매 선택이 '그 순간에 대해서는' 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심.

• 어떤 경우에 잘 동작하는가

한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 하는 경우

순열과 조합

조합과 순열은 매우 비슷. 문제 위주로 유형 잘 익혀둘 것.
차이: 순열은 순서가 중요하고, 조합은 순서가 중요하지 않다

순열 (permutations)

서로다른 n개에서 r개를 선택할때 순서를 고려하여, 중복없이 뽑을 경우의 수

nPr = n! / (n-r)!
예를 들어, A B C D 에서 순서에 상관있이, 중복없이 2가지를 뽑는 모든 경우의 수는?

AB/AC/AD

BA/BC/BD

CA/CB/CD

DA/DB/DC

총 12가지가 된다.

이때 순서를 고려하기 때문에 AB와 BA는 다른경우로 본다.

사용법 :
Python에는 순열과 조합을 손쉽게 만들어주는 모듈 itertools가 있다.

형식 : permutations(객체, r) 반복가능한 객체(리스트,튜플,문자열)안에서 r개를 선택한다

조건 : from itertools import permutations를 처음에 선언해야한다.
리턴값 : 객체가 되며 경우의 수에 대한 쌍을 튜플형식으로 반환한다.

예시
permutations(객체, r) 자체가 객체가 된다. 그래서 반복문으로 print할때 각 쌍들을 튜플형식으로 가지고 있음

import itertools

arr = ['A', 'B', 'C']
nPr = itertools.permutations(arr, 2)
print(list(nPr))

결과 : [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

총 갯수를 구하기 위해 permutations객체의 쌍을 list로 변환해 그 길이를 구하면 된다.

>>> print(len(list(permutations(arr,2))))
12

조합 (combinations)

: 서로다른 n개에서 r개를 선택할때 순서를 고려하지 않고, 중복없이 뽑을 경우의 수

nCr = n! / r! (n-r)!
예를 들어, A B C D 에서 순서를 고려하지 않고, 중복없이 2가지를 뽑는 모든 경우의 수는?

AB/AC/AD

BA/BC/BD

CA/CB/CD

DA/DB/DC

총 6가지가 된다.

이때 순서를 고려하지 않기 때문에 AB와 BA는 같은 경우로 본다.

사용법
Python에는 순열과 조합을 손쉽게 만들어주는 모듈 itertools가 있다.

형식 : combinations(객체, r) 반복가능한 객체(리스트,튜플,문자열)안에서 r개를 선택한다
조건 : from itertools import combinations를 처음에 선언해야한다.
리턴값 : 객체가 되며 경우의 수에 대한 쌍을 튜플형식으로 반환한다.

예시
combinations(객체, r) 자체가 객체가 된다. 그래서 반복문으로 print할때 각 쌍들을 튜플형식으로 가지고 있음

import itertools

arr = ['A', 'B', 'C']
nCr = itertools.combinations(arr, 2)
print(list(nCr))

결과 : [('A', 'B'), ('A', 'C'), ('B', 'C')]

[jinjinhee]

그리디 알고리즘

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 설계 기법

그리디 알고리즘은 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.

그리디 알고리즘은 100% 최적해를 보장해주지 않는다. 다만, 어느 정도 적합한 수준의 해답을 알려준다. 따라서, 최적이 아닌 "되는가" 또는 "적당히 괜찮은 방법"을 찾을 때에는 사용할 수 있다. 특히, 계산속도가 정확한 알고리즘에 비해서 빠른 경우가 많기 때문에 실용적으로 사용이 가능하다. 허나 이게 정말로 "적당히" 괜찮은지에 대해서 알려면 정확한 증명이 수반될 수 있다. 또한, 해답을 찾아가는 과정에 있어서 그리디로 구한 값을 비교값으로 설정할 수가 있다.

---

순열과 조합, 중복순열과 중복조합

순열

반복 가능한 객체에 대해서 중복을 허용하지 않고 r개를 뽑아서 나열한다.

서로 다른 n개에서 r개를 택하여 일렬로 나열하는 경우

from itertools import permutations

for i in permutations([1,2,3,4], 2):
    print(i, end=" ")

#(1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3) 

조합

서로 다른 n개에서 순서를 생각하지 않고 r개를 택하는 경우

n개 중 r개를 뽑음

from itertools import combinations

for i in combinations([1,2,3,4], 2):
    print(i, end=" ")

#(1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) 

중복순열

중복 가능한 n개에서 r개를 택하여 일렬로 나열하는 경우

from itertools import product

for i in product([1,2,3,4], repeat=2):
    print(i, end=" ")

#(1, 1) (1, 2) (1, 3) (1, 4) (2, 1) (2, 2) (2, 3) (2, 4) (3, 1) (3, 2) (3, 3) (3, 4) (4, 1) (4, 2) (4, 3) (4, 4)

중복조합

중복 가능한 n개에서 순서를 생각하지 않고 r개를 택하는 경우

from itertools import combinations_with_replacement

for i in combinations_with_replacement([1,2,3,4], 2):
    print(i, end=" ")

#(1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)