Itertools 순열 조합 라이브러리

알고리즘 문제를 풀다보면 순열이나 조합을 사용해서 문제를 풀 때 더 간단하게 풀 수 있는 경우가 많다. 그럴 때에는 itertools 라이브러리를 사용한다.
itertools 라이브러리에는 사실 순열과 조합 외에도 iterable 자료형을 처리하는 다른 함수들이 존재하지만 가장 자주 쓰이는 것이 순열과 조합이기 때문에 여기서는 순열, 조합을 사용하는 법만 확인한다.
다른 기능을 알고 싶으면 https://docs.python.org/ko/3/library/itertools.html 를 확인하길 바란다.

1. 순열 Permutation

itertools.permutations(iterable, r = None)
순열은 iterable 자료형에서 r 개의 데이터를 뽑아 순서가 있는 형태로 나타낸다.
각각의 sub sequence는 길이가 r 이고 튜플로 이루어진다. 반환형태는 클래스이기 때문에 사용하기 힘들 수 있기 때문에 주로 리스트로 변환을 해주는 것이 편하다. (필수는 아니다.)

from itertools import permutations

data = ['a', 'b', 'c']

result = list(permutations(data))
result2 = permutations(data)
# 두 번째 인자를 넣어주지 않으면 자동으로 r = len(data) 가 된다.
print(result)
print(result2)
for i in result2:
    print(i, end=' ')

| [('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]
<itertools.permutations object at 0x0000020AD7E80EA0>
('a', 'b', 'c') ('a', 'c', 'b') ('b', 'a', 'c') ('b', 'c', 'a') ('c', 'a', 'b') ('c', 'b', 'a') |
| --- |

코드에서 처럼 for 문에서 튜플을 하나씩 가져와서 사용하는 것은 가능하지만 result2[0]같이 직접적으로 객체에 접근하는 것은 불가능하다. 그래서 list로 변환을 해주는 것이 편하다는 것이고 앞으로 나올 combinations, product, combinations_with_replacement 에서는 설명을 생략한다.

2. 조합 Combination

itertools.combinations(iterable, r =None)
조합은 순열은 iterable 자료형에서 r 개의 데이터를 뽑아 순서가 없는 상태로 나열한다.

from itertools import combinations

data = ['a', 'b', 'c']
result = list(combinations(data, 2))    # r = 2 로 설정

print(result)

3. 데카르트 곱(cartesian product)

itertools.product(iterable, repeat = 1)
데카르트 곱은 iterable 자료형에서 repeat 개 만큼을 중복을 허용해서 순열을 만든다고 책에 쓰여져 있기도 하지만 사실 product는 여러개의 iterable 자료형을 입력으로 받아서 가능한 모든 곱을 나타내는 것이다. 다음은 3가지 예시를 보여준다.

from itertools import product

data = ['a', 'b', 'c']
data2 = ['x', 'y']
data3 = range(2)    # [0, 1]
result = list(product(data, repeat=2))

print(result)
print(list(product(data, data2)))
print(list(product(data3, repeat=3)))

| [('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'b'), ('b', 'c'), ('c', 'a'), ('c', 'b'), ('c', 'c')]
[('a', 'x'), ('a', 'y'), ('b', 'x'), ('b', 'y'), ('c', 'x'), ('c', 'y')]
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)] |
| --- |
| 'product(data, repeat=2) 는 사실 product(data, data) 이다. 두 번째 예시에서 보듯이 data에서의 값과 data2에서의 값으로 만들 수 있는 모든 순열을 만들어 내는 것이다. |
| 세 번째 예시는 나중에 이진수를 만들어 낸다면 유용하게 쓰일 것 같아서 적어봤다. |

4. 중복 조합

** itertools.combinations_with_replacement(iterable, r = None)**
중복 조합은 말 그대로 중복을 허용해서 조합을 완성시키는 것이다. 바로 예시로 넘어간다.

from itertools import combinations_with_replacement

data = ['a', 'b', 'c']

result = list(combinations_with_replacement(data, 2))

print(result)

마무리

파이썬 개념 정리는 처음으로 글을 썼다. 백준닷컴 문제를 풀다보니 순열, 조합을 사용하는 것이 많아서 정리가 필요해서 글을 썼다. 파이썬 라이브러리를 직접 찾아보면서 글을 적다보니 시간이 많이 걸렸지만 대충 알고 있던 정보도 올바르게 알게 되어서 시간이 날 때면 라이브러리를 찾아 봐야할 것 같다.
오늘 공부한 내용 중에서 중요했던 것을 되짚어보면서 마무리 하겠다.

• itertools를 import해서 만들어져있는 순열, 조합 함수를 쓰면 쉽게 코드를 작성할 수 있다.
• 순열, 조합의 반환형은 class이기 때문에 list로 변환하면 편하게 쓸 수 있다. 하지만 필수는 아니다.
• product는 단순히 중복 순열만을 위한 함수가 아니지만 알고리즘 상 중복 순열을 만들어내는 능력이 있는 것이다.
• 함수를 제대로 공부하고 싶으면 라이브러리를 참고하자.

문제 번호 : 16938

문제 출처 : https://www.acmicpc.net/problem/16938 

Code

import itertools


def diff(num):
    return max(num) - min(num)


n, l, r, x = map(int, input().split())
a = list(map(int, input().split()))
count = 0

for i in range(2, n+1):
    numbers = list(itertools.combinations(a, i))
    for number in numbers:
        if l <= sum(number) <= r:
            if diff(number) >= x:
                count += 1

print(count)

Idea

1. N개의 난이도를 2개 이상으로 조합해서 조건에 맞는지 확인한다.
2. combination한 후 list의 요소는 iterable한 튜플 형으로 모든 난이도의 합은 sum 함수로 구현이 가능하다.
3. 차를 구하는 함수는 최대값에서 최소값을 빼주는 형태로 가능했다.
4. 두 조건을 모두 만족하면 count 값을 1씩 증가시키고 마지막에 출력한다.

이전의 문제들보다 난이도가 낮은 편이었다. 처음에는 n이 1인 경우에 print(0)을 먼저 하는 경우를 생각했었는데 print를 2번하게 되어서 채점중(99%)에서 "틀렸습니다"가 나왔다. 아무래도 마지막 입력에서 n이 1인 듯하다. n이 1이면 2개 이상을 조합으로 뽑아올 수 없다.

문제 번호 : 16936

문제 출처 : https://www.acmicpc.net/problem/16937

Code

import sys


def able(height, width, row, col):
    if row <= height and col <= width:
        if row <= width and col <= height:
            return 3
        else:
            return 1
    elif row <= width and col <= height:
        return 2
    else:
        return 0


h, w = map(int, input().split())
n = int(input())
stickers = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
result = 0

for i in range(len(stickers)):
    r, c = stickers[i][0], stickers[i][1]
    way = able(h, w, r, c)
    if way > 0:
        if way == 1:
            new_hw = [h-r, w, h, w-c]
        elif way==2:
            new_hw = [h-c, w, h, w-r]
        else:
            new_hw = [h-r, w, h, w-c, h-c, w, h, w-r]

        for sticker in stickers[i+1:]:
            new_r, new_c = sticker[0], sticker[1]
            for j in range(0, len(new_hw), 2):
                if able(new_hw[j], new_hw[j+1], new_r, new_c) > 0:
                    result = max(r*c + new_r * new_c, result)
print(result)

Idea

1. 스티커의 한 변의 길이가 모눈종이의 높이보다 작거나 같고 다른 한 변의 길이가 모눈종이의 너비보다 작거나 같으면 스티커를 모눈 종이에 붙일 수 있다.
   단순히 붙일 수 있는지 확인하는 것은 max(r, c) < max(h, w) and min(r, c) < min(h, w) 로 구현하면 된다.
2. 붙일 수 있는 스티커면 일단 붙인다.
   

   

3.  1번 영역에 스티커가 붙어 있으면 2번 영역 + 4번 영역, 3번 영역 + 4번 영역 두 가지 위치에 붙일 수 있다.
   따라서 이 때 새로운 크기를 가진 모눈 종이가 생긴다고 생각한다.
   이 새 모눈 종이들의 높이와 너비를 new_hw 리스트에 저장한다.
4. 현재 붙은 스티커 이후의 스티커들이 새 모눈 종이에 붙일 수 있는지를 판별하고 그 때의 넓이가 더 커지면 result를 갱신한다. 

처음에는 stickers를 넓이를 기준으로 내림차순으로 정렬한 후 두 스티커가 붙게 되면 무조건 최대값이니까 break문을 사용해서 최대한 반복문을 덜 돌게 하려고 노력했고 입력 예제 입력들은 모두 통과가 되는데 코드 제출하니까 "틀렸습니다."라고 나왔다. 

[백준][파이썬] 16936번 - 나3곱2

문제 번호 : 16936

문제 출처 : https://www.acmicpc.net/problem/16936

Code

n = int(input())
B = list(map(int, input().split()))
x = min(B)
old_power = 0

for b in B:
    i = 3
    power = 0
    while i <= b:
        if b % i == 0:
            power += 1
        i *= 3
    if power > old_power or (power == old_power and b < x):
        x = b
        old_power = power
        
A = []
A.append(x)
count = 1
while count < n:
    if x * 2 in B:
        x = x * 2
        A.append(x)
        count += 1
    else:
        x = x // 3
        A.append(x)
        count += 1

for a in A:
    print(a, end=' ')

Idea

1. 가장 큰 수가 짝수이면 얘는 절대 x는 아니다?    False
   
   • 예제 2번에서 보듯 가장 큰 수가 짝수여도 x일 수 있다.
2. 오른쪽으로 갈수록 수의 2^n배 증가하고 3^-n배로 감소한다.
3. 3의 n승을 약수로 가질 때 n이 클수록 왼쪽에 위치한다.
4. 같은 지수를 가지는 수 중에서 가장 작은 수가 x가 된다.
5. x를 시작으로 법칙대로 수를 A 리스트에 삽입한다.

처음에 생각할 때에는 한 노드에서 2 가지를 모두 탐색한 후 다시 되돌아와서 다른 방향으로 가야 될거라 생각했다.

다른 사람들의 풀이에는 재귀함수를 사용한 경우도 많아 보였다. 나는 x를 찾은 후 문제의 알고리즘대로 A 수열을 만들었는데 다른 사람의 코드에서는 이차원 리스트와 lambda를 사용해서 정렬을 하기도 했다.

n = int(input())
b = list(map(int, input().split()))

a = []

for num in b:
    can3 = 0
    num_origin = num
    while True:
        if num % 3 == 0:
            can3 += 1
            num //= 3
        else:
            break
    a.append([can3, num_origin])

a.sort(key= lambda x: (-x[0], x[1]))
for i in range(n):
    print(a[i][1], end=' ')

이 코드가 훨씬 간결해보인다. key = lambda x: (-x[0], x[1])로 정렬한 것은 -x[0] 즉 3으로 나누어지는 수가 큰 것으로 정렬한 후 원래 값이 작은 순으로 정렬한다. 정렬의 기본 순서는 오름차순이므로 -x[0]를 기준으로 하면 큰 수가 앞으로 온다.

반복문을 진행하면서 모든 과정을 끝내는 것을 연습해야 된다고 생각이 들었다.

[백준][파이썬] 16924번 - 십자가 찾기

문제 번호 : 16924

문제 출처 : https://www.acmicpc.net/problem/16924

Code

import sys

n, m = map(int, input().split())
board = [list(sys.stdin.readline().strip()) for _ in range(n)]
answer =[]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

if board[0][0] == '*' or board[0][m-1] == '*' or board[n-1][0] == '*' or board[n-1][m-1]=='*':
    print(-1)
    # 각 모서리에 * 이 있으면 십자가는 찾을 수 있어도 십자가로 그 별을 커버하지 못한다.
else:
    for i in range(1, n-1):
        for j in range(1, m-1):
            if board[i][j] == '*':
                max_size = min(i, j, n-i-1, m-j-1)
                # 십자가의 최대 크기는 상하좌우의 공백길이의 최소값
                for k in range(1, 1 + max_size):
                    count = 0
                    for idx in range(4):
                        nx = i + k * dx[idx]
                        ny = j + k * dy[idx]
                        if board[nx][ny] != '*':
                            break
                        else: count += 1
                    if count == 4:
                        answer.append((i, j, k))
                    else:
                        break
    # board에서 찾은 십자가 위치를 모두 . 으로 바꾼다.
    for pos in range(len(answer)):
        row = answer[pos][0]
        col = answer[pos][1]
        board[row][col] = '.'
        for idx in range(4):
            nr = row + dx[idx] * answer[pos][2]
            nc = col + dy[idx] * answer[pos][2]
            board[nr][nc] = '.'
    # sum(board, [])를 하면 1차원 배열로 바뀌고 그 안 * 이 있는지 찾는다.
    if '*' not in sum(board, []) and len(answer) != 0:
        print(len(answer))
        for ans in answer:
            print(ans[0] + 1, ans[1] + 1, ans[2])
    else:
        print(-1)

Idea

1. 각 모서리에 * 이 있으면 십자가만으로 해당 격자판을 만들 수 없다.
2. 문제에서는 시작을 (1, 1)로 규정했지만 코드를 짤 때는 (0, 0) 에서 시작하는 것으로 한다.
3. 십자가를 찾을 때 최대 크기는 (i, j) 에서 상하좌우 공백 중 가장 짧은 것을 기준으로 한다.
4. size가 1인 십자가가 아닌 경우에는 더 큰 size의 십자가는 만들어 질 수 없다.
5. 찾은 십자가로 격자판을 만들 수 있는가는 두 가지 방법으로 할 수 있다.
   1. 같은 크기의 새로운 배열을 만들어 십자가를 찾을 때마다 해당 위치의 배열 값을 바꾸어준다.
   2. 찾은 십자가 위치를 모두 *이 아닌 다른 문자(여기서는 . )로 바꾸어주고 마지막에 * 이 존재하는지 확인한다.
6. sum(이차원 리스트, []) 를 하게 되면 일차원 리스트로 변환되어서 in 연산자를 사용하기 편해진다.

      ex) li1 = [[1, 2], [2, 4], [4, 8]] 인 경우에 li2 = sum(li1, [])를 하게 되면

           li2 = [1, 2, 2, 4, 4, 8] 이된다.