[백준] N과 M 시리즈 풀이 모음

풀이 리스트

저의 N과 M 시리즈 풀이 모음입니다.

1. N과 M (1) - Python, C++
   • 순열(permutation)
2. N과 M (2) - Python
   • 조합(combination)
3. N과 M (3) - Python
   • 중복 순열(product)
4. N과 M (4) - Python
   • 중복 조합(combinations with replacement)
5. N과 M (5) - Python (정렬 후 순열)
6. N과 M (6) - 정렬 후 조합
7. N과 M (7) - 정렬 후 중복 순열
8. N과 M (8) - 정렬 후 중복 조합
9. N과 M (9) - Python
   • 같은 것이 있는 순열(permutations with repetitions)
10. N과 M (10) - Python
    • 같은 것이 있는 조합(combinations with repetitions)
11. N과 M (11) - Python
    • 같은 것이 있는 중복 순열(같은 것 제거 후 중복 순열)
12. N과 M (12)

5 ~ 6은 1 ~ 4에 정렬만 추가한 것이어서 따로 글로 작성하진 않았습니다.

11 ~ 12역시  9 ~ 10에 입력의 같은 것을 제거하는 로직만 추가하면 됩니다.

 

요약

- 순열(permutations)

def permutations(pool: list[int], n: int, r: int):
    if r == 0 or r > n:
        return []
    if r == 1:
        return [[x] for x in pool]

    result = []
    for x in pool:
        nextPool = [y for y in pool if y != x]
        for p in permutations(nextPool, n - 1, r - 1):
            result.append([x] + p)
    return result

`n`개의 원소가 있는 `pool`에서 `r`개를 뽑는 순열은, pool에서 원소를 하나씩 뽑아 r개의 자리에 배치하는 문제와 같다.

1. `pool`에서 원소를 하나 뽑아 제일 앞자리에 채운다. (방금 뽑은 원소를 `x`라 하자.)
2. 남은 r-1개의 자리와 `x`가 제거된 `nextPool`에 대해 재귀적으로 문제를 해결한다.
   • 종료 조건은 채울 자리가 없거나 (r==0), 채워야 할 자리가 원소의 총량보다 많으면(r > n) 만들 수 있는 경우가 없으므로 빈 리스트를 반환
   • 채울 자리가 하나면(r==1) pool의 모든 원소로 자리를 채워 반환
3. 재귀적으로 구해진 r-1개의 자리들 앞에 `x`에 이어붙여 최종적으로 r개의 자리를 채운다.

 

- 조합(combinations)

def combinations(pool: list[int], n: int, r: int):
    if r == 0 or r > n:
        return []
    if r == 1:
        return [[x] for x in pool]

    result = []
    for i, x in enumerate(pool):
        nextPool = pool[i+1:]
        for c in combinations(nextPool, n - 1, r - 1):
            result.append([x] + c)
    return result

`n`개의 원소가 있는 `pool`에서 `r`개를 뽑는 조합은, 형제(sibiling) 노드의 자식 수가 줄어드는 트리로 생각할 수 있다.

순열과의 차이는 순열 단순히 자신을 제외한 pool을 자식 노드로 전달하기 때문에 형제 노드끼리의 자식 수는 같다.

하지만 조합은 형제끼리도 순서에 따라 입력으로 받는 pool이 줄어든다.(중복을 제거하기 위해)

따라서 조합의 트리는 부모에서 자식(상에서 하), 형제 노드(좌에서 우) 두 방향으로 자식이 줄어든다.

참고로 순열은 부모에서 자식(상에서 하) 방향으로만 자식이 줄어든다.

 

- 중복 순열(products)

def product(pool: list[int], r: int):
    if r == 0:
        return []
    if r == 1:
        return [[x] for x in pool]

    result = []
    for x in pool:
        for p in product(pool, r - 1):
            result.append([x] + p)
    return result

중복 순열과 순열의 차이는 중복을 허용하기 때문에 `pool`에서 현재값 `x`를 제외하지 않고 자식 노드로 넘겨준다. 따라서 자식 노드에서도 부모와 같은 `x`를 뽑을 수 있다.

n^r 로, 모든 경우의 수다. 높이가 r이며 모든 노드의 자식의 수가 n이다.

 

- 중복 조합(combinations_with_replacement)

def combinations_with_replacement(pool: list[int], r: int):
    if r == 0:
        return []
    if r == 1:
        return [[x] for x in pool]

    result = []
    for i, x in enumerate(pool):
        nextPool = pool[i:]
        for cwr in combinations_with_replacement(nextPool, r - 1):
            result.append([x] + cwr)
    return result

중복 조합과 조합의 차이는 현재값 `x`를 포함하느냐 안 하느냐의 차이다. 중복을 허용하기 때문에 현재값을 포함한 `pool`을 자식 노드에 넘겨준다.

중복 조합과 중복 순열의 차이는 현재값 `x` 원소들을 포함하느냐 안 하느냐의 차이다. 중복 순열은 모두 포함하여 넘기지만 순열은 현재값 이전 원소들을 제거하고 자식에게 넘긴다. `x` 이전 원소들을 넘겨주지 않는 것은 중복을 막기 위해서다.

트리에서 좌에서 우로 형제 노드를 보면 자식의 수가 하나씩 줄어들지만 가장 왼쪽 가지를 상에서 하로 보면 루트의 입력부터 리프의 입력까지 같다. 

 

- 같은 것이 있는 순열(permutations_with_repetitions)

def permutations_with_repititions(pool: list[int], n: int, r: int):
    if r == 0 or r > n:
        return []

    keys = []
    for x in pool:
        if x not in keys:
            keys.append(x)

    if r == 1:
        return [[x] for x in keys]

    result = []
    for x in keys:
        nextPool = pool[:]
        nextPool.remove(x)
        for pwr in permutations_with_repititions(nextPool, n - 1, r - 1):
            result.append([x] + pwr)
    return result

같은 것이 있는 순열은 같은 자식이 없는 트리로 생각할 수 있다. 따라서 입력의 중복을 제거해 자식을 만든다.

이때 자식의 입력은 그냥 순열과 같이 현제값만 제거하고 자식 노드에 넘겨준다.

위와 같이 `set`을 사용하지 않고 중복을 제거하면 `pool`의 순서를 유지하며 중복을 제거할 수 있다. set을 이용한다면 다시 정렬 해줘야 한다.

 

- 같은 것이 있는 조합(combinations_with_repetitions)

def combinations_with_repetitions(pool: list[int], n: int, r: int):
    if r == 0 or r > n:
        return []

    keys = []
    for x in pool:
        if x not in keys:
            keys.append(x)

    if r == 1:
        return [[x] for x in keys]

    result = []
    for x in keys:
        nextPool = []
        once = True
        for y in pool:
            if y < x:
                continue
            elif once and y == x:
                once = False
                continue
            nextPool.append(y)
        for cwr in combinations_with_repetitions(nextPool, n - 1, r - 1):
            result.append([x] + cwr)
    return result

같은 것이 있는 조합은 같은 것이 있는 순열과 조합의 스킬을 합쳐서 구현한다.

조합은 형제(좌에서 우) 노드의 자식 수가 줄어든다.

같은 것이 있는 순열은 중복되지 않게 자식을 생성한다. (자식 노드에 중복이 없다.)

이 두가지를 합쳐 중복되는 자식을 생성하지 않으면서 형제 노드의 자식의 수가 줄어들게 구현하면 된다. 

재귀 부분 전에 `nextPool`을 생성하는 과정을 조금 설명하자면 현재값 `x`보다 앞의 값은 모두 제거하고(`nextPool`에 포함시키지 않는다.) `x`값과 같은 값은 하나만 제거한다.

중복을 허용하지 않기 때문에 현제 노드에서 사용하는 `x`는 제거해야한다. 

`중복을 허용`하는 것은 하나의 원소를 두번 이상 사용하는 것이고 `같은 것이 있는 것`은 값이 같은 원소가 2개 이상인 것이다.