[백준][파이썬]

문제 번호 : 17088
문제 출처 : https://www.acmicpc.net/problem/17088

Code

# 등차 수열이려면 첫 번째 차와 두 번째 차가 같은 경우여야 함

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

if n < 3:  # 숫자가 하나 또는 2개면 무조건 등차수열
    print(0)
else:
    diff = []   # 수열에서 한 칸당 차이를 저장
    for i in range(n - 1):
        diff.append(a[i] - a[i + 1])
    if len(set(diff)) == 0: # 차이가 모두 같으면 집합으로 했을 때 값이 하나밖에 없다.
        print(0)
        exit(0)

    op = (-1, 0, 1)     # 연산의 종류
    cases = []
    answer = n + 1      # 최소값을 찾을 거고 값은 연산횟수는 n을 넘어갈 수 없다.
    for i in op:
        for j in op:
            for k in op:
                count = abs(i) + abs(j) + abs(k)
                d1, d2 = diff[0] + i - j, diff[1] + j - k
                if d1 == d2:    # 0번와 1번, 1번와 2번의 차가 같은 경우 cases에 저장
                    cases.append((a[0] + i, d1, count))

    for case in cases:      # 저장된 케이스들만 생각
        start = case[0]
        sub = case[1]
        cnt = case[2]
        if n == 3:          # A3까지 모두 연산을 해봤기 때문에 길이가 3인 경우 답은 cnt일 확률이 높다.
                            # 아닌경우도 있을 듯
            answer = min(answer, cnt)
        for idx in range(3, n):
            tmp = a[idx] - (start - (sub * idx))    # idx 번째의 값이 예상 값보다 1 이상 차이나면
            if abs(tmp) > 1:                        # +-1 연산만으로 등차수열을 만들 수 없다.
                break
            elif abs(tmp) == 1:                     # 값이 1밖에 차이 안나면 +든 -든 연산을 해야된다.
                cnt += 1                            # 뭘할지 정할 필요는 없고 횟수만 세면 된다.
            if idx == n - 1:
                answer = min(answer, cnt)

    print(answer if answer <= n else -1)            # answer가 n+1이면 -1을 출력, 아니면 answer를 출력

Idea

1. 입력된 수가 2개 이하이면 항상 등차수열이 된다. 그런 경우 연산을 0번 진행하기 때문에 print(0)를 하고 프로그램을 종료한다.
2. 입력된 수가 3개 이상인 경우를 생각해보면 A1, A2, A3 에 각각 연산을 한 후 A1 - A2 과 A2-A3가 같아지는 경우들만 cases에 추가해준다. 이 때 연산 횟수는 -1, 1 은 각 한 번씩, 0은 연산을 하지 않은 것으로 생각하기 위해서 절대값을 취해줬다.
3. cases에 추가된 경우들에서 4번 째 수부터 첫 번째 수와 차를 이용해서 구한 예상값과 차이가 1보다 크면 등차수열이 만들어질 수 없다.
4. 예상값과 차이가 1이면 연산횟수를 1 더해주고 0이면 그냥 넘어간다. 마지막 수까지 예상값과 차이가 1 이하이면 answer에 cnt의 최소값을 넣어준다.
5. 처음에 answer = n + 1 로 정의했기 때문에 등차수열을 만들 수 있는 case가 존재하지 않으면 answer > n 이기 때문에 -1을 출력하도록 한다.

[백준][파이썬] 15683번 감시

문제 번호 : 15683
문제 출처 : https://www.acmicpc.net/problem/15683

Code

import sys


def watch(watched_set, index):              # index : count, cctv 개수 만큼 탐색
    if index == len(cctvs):
        result.append(len(watched_set))
        return
    else:
        for cctv in cctvs[index]:           # cctv[index] 에는 한 cctv의 경우의 수가 모두 저장
            new_s = set(watched_set)
            view(cctv, new_s)               # 각도에 따라서 cctv로 볼 수 있는 위치를 집합에 저장
            watch(new_s, index + 1)


def view(cc, viewd):
    x, y, cctv_type, angle = cc
    d = []
    for idx in range(4):
        d = direction[cctv_type][(idx + angle) % 4] # cctv type과 angle이 정해졌을 때 방향
        if d == 1:
            nx, ny = x + dx[idx], y + dy[idx]
            while -1 < nx < h and -1 < ny < w and office[nx][ny] != 6:
                if office[nx][ny] == 0:     # cctv 있는 위치는 저장 안하도록
                    viewd.add((nx, ny))
                nx = nx + dx[idx]
                ny = ny + dy[idx]


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

angles = [4, 2, 4, 4, 1]        # type별로 가능한 각도 수
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
direction = [[0, 0, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1,], [1, 1, 1, 1]] # 각도 별로 shift할 리스트

cctvs = []
answer = 0
result = []

for i in range(h):
    for j in range(w):
        if 0< office[i][j] <6:  # cctvs 에 하나의 cctv에서 가능한 각도를 하나의 리스트에 모두 저장
            cctvs.append([[i, j, office[i][j] - 1, angle] for angle in range(angles[office[i][j] - 1])])
        if office[i][j] == 0:   # 0의 개수 세기기
            answer+= 1
watched = set([])

watch(watched, 0)
answer = answer - max(result)   # 0의 개수에서 cctv로 본 위치의 수 빼서 답 구하기
print(answer)

Idea

1. cctv 종류 별로 가능한 각도 수가 다르다.
2. 처음에는 cctv로 본 곳을 #으로 표시했는데 시간이 많이 걸렸다.
3. 입력받은 이차원 리스트를 수정하지 않고 cctv가 본 위치를 저장하는 집합을 만들었다.
4. cctv가 본 위치가 가장 많은 상황에서 0의 개수에서 집합의 길이를 빼면 사각지대를 구할 수 있다.

[백준][파이썬]

문제 번호 : 16637
문제 출처 : https://www.acmicpc.net/problem/16637

Code

from itertools import combinations


def disable(tu):    # 괄호를 둘 수 있는가 판별
    if len(tu) > 1:
        tmp_li = list(combinations(tu, 2))

        for tmp in tmp_li:  # 2개를 골라와서 그 차이가 1이면 괄호를 둘 수 없다.
            if max(tmp) < min(tmp) + 2:
                return True

        return False

    else:
        return False


def calc(expr):
    result = 0
    old_op_idx = -1
    old_op = '+'
    op1 = 0
    for i in range(len(expr)):
        if expr[i] == '+' or expr[i] == '*' 
                or expr[i] == '-' and i - old_op_idx != 1:
            op1 = result
            op2 = expr[old_op_idx+1:i]
            result = eval(str(result) + old_op + expr[old_op_idx+1:i])
            old_op = expr[i]
            old_op_idx = i
    result = eval(str(result) + old_op + expr[old_op_idx+1:])
    return result


n = int(input())
expression = input()    # 수식 입력
num_op = n//2           # 연산자 개수 = 수식 길이 // 2
answer = - 2**31        # -2**31 < ANSWER < 2**31
maximum = 2**31

if n == 1:      # 길이가 1 ==> 숫자 하나 입력
    print(int(expression))
elif n == 3:    # 길이가 3 ==> 연산자 하나를 가지는 수식 입력
    print(eval(expression))
else:
    for br in range(1, num_op//2+1):    # br : 괄호 갯수, 괄호의 최대 개수는 연산자 수 // 2
        cases = list(combinations(range(num_op), br))   # 괄호 br 개를 넣을 수 있는 경우의 수를 모두 찾아냄
        for case in cases:
            if disable(case):   # 괄호를 넣을 수 있는지 판별
                continue
            else:
                ex = expression # 수식을 잠깐 저장
                for i in range(len(case)-1, -1, -1):                # 수식을 뒤에서 부터 수정
                    i = case[i]                                     # 앞에서부터 수정하면 뒷 부분의 index값이 변함
                    ex_li = list(ex) # 수식의 중간을 수정하기 위해 list 형으로 잠시 변환
                    ex_li[i*2: i*2+3] = str(eval(ex[i*2:i*2+3]))    # 수식의 중간 부분 수정
                    ex = ''.join(ex_li)                             # join()함수로 list를 다시 str으로 변환
                answer = min(max(calc(ex), answer), maximum)        # 계산 결과와 원래 값 중 최대값을 비교
                                                                    # 문제에서의 최대값을 넘어가지 않도록 비교
    print(answer)

Idea

1. 입력 예시 1을 기준으로 설명하겠다. 재귀 함수를 사용하면 더 쉬울 듯 하다.
   예를 들어 3+8*7-9*2 가 입력되면 3+8을 한 후 7-9*2를 재귀함수의 입력으로 넣고 다시 2를 입력으로 넣는 방식으로 풀어도 괜찮을 듯 한데 재귀함수를 많이 접하지 않아서 만들지 못했다.
2. 그래서 단순 반복으로 했는데 괄호가 들어갈 수 있는 위치의 모든 경우의 수를 구해야 했다. 우선 괄호의 최대 개수는 입력된 수식에서 연산자 개수를 2로 나눈 몫이다.
3. 괄호가 1개인 경우부터 최대 개수까지 반복해서 연산자의 개수에서 괄호 개수 만큼 가능한 모든 조합을 뽑아서 조건을 확인한다. 괄호 연산이 가능한 조건은 한 가지 뿐이다. 괄호 연산을 할 연산자가 붙어 있으면 안 된다.
4. 괄호 계산을 먼저 한 후 문자열에서 3글자를 한 숫자로 바꾸어주어야 했는데 str 형에서 문자를 대체하는 replace()함수로 구현을 하게 되면 바꾸려는 문자열과 같은 문자열이 더 앞에 존재하면 원하는 위치가 아니라 엉뚱한 문자열을 바꾼다.
   ex) 예제 입력 6에서 수식은 1-9-1-9-1-9-1-9-1-9 일 때
   1-9-1-9-(1-9)-1-9-1-9, 1-9-1-9-1-9-1-9-(1-9) 두 경우 모두 -8-1-9-1-9-1-9-1-9로 바뀐다.
   그래서 문자열로 표현된 수식을 잠깐 리스트로 바꿔서 원하는 위치의 문자들을 바꾼후 다시 str로 변환한다. 문자열로 바꿀 때는 전에 사용했던 ''.join()을 사용했다.
   ( 문자열은 튜플 같이 요소들의 직접적인 변경이 허용되지 않는다. ex) str[0] = 'a' error
5. 수식을 계산하는 함수 calc()를 살펴보면 연산자의 위치를 찾고 연산자가 나타날 때까지의 수를 operand로 사용해서 그 전의 값과 old_op에 해당하는 연산을 수행한다. 만약 연산자 뒤에 바로 -가 나오면 그건 음수를 뜻하는 것으로 if 문에서 False가 되어 동작하지 않는다.
6. 수식의 길이가 1인 경우와 3인 경우에는 괄호의 최대 개수가 0으로 되어 동작하지 않아서 처음에 예외 처리를 해두었다.

이번 코드는 재귀함수로 여러 번 시도하다가 안 돼서 시간이 오래 걸렸다. 이 문제에서 처음으로 사용한 함수는 eval()이라는 함수이다. 어떤 책에서는 괄호 안의 수식을 계산해주는 함수라고만 설명이 되어 있다. 하지만 eval()은 괄호 안에 파이썬 명령어를 써 넣으면 명령어에 해당하는 동작을 수행하고 그 값을 반환해준다.

s = "\"Hello World\""
eval("print(" + s + ")")

# 결과
# Hello World

내가 봐도 코드가 이해가 안 될 수 있는 부분들이 많아서 설명이 길어졌다. 더 클린한 코드를 짜도록 노력해야겠다.

[백준][파이썬] 16943번 숫자 재배치

문제 번호 : 16943
문제 출처 : https://www.acmicpc.net/problem/16943

Code

from itertools import permutations

def to_int(t):
    if t[0] != '0':
        pos = 10 ** (len(t)-1)
        tmp = 0
        for i in t:
            tmp += int(i) * pos
            pos = pos // 10
        return tmp
    return -1


a, b = input().split()
b = int(b)
c = -1

numbers = list(permutations(a)
for number in numbers:
    if number[0] == '0':
        continue
    num = int(''.join(number)) # to_int(number)
    if num < b:
        c = max(num, c)

print(c)

Idea

1. a를 순열을 사용해서 만들기 편하게 하기 위해서 int형으로 변환하지 않고 문자열로 입력받는다. (문자열도 iterable이기 때문에)
2. b는 미리 int형으로 형변환을 한다.
3. permutations(a) r 이 생략되었으므로 a의 길이를 인자로 갖는다.
4. 문자로 이루어져 있는 튜플을 숫자로 변환한다.
5. b와 비교해서 작으면 다시 max()로 비교한 후 저장한다.

for 문에서 number 가 튜플 자료형이기 때문에 int(number)를 사용할 수 없어서 처음에는 to_int()라는 함수를 만들어서 사용했다. 그러다가 튜플을 문자열로 바꾸는 방법이 있어서 적용해봤다. 내가 만든 to_int()로 프로그램을 돌렸을 때 시간이 1288ms 가 나왔고 int(''.join(number))를 사용했을 때 432ms 가 나왔다.

''.join(iterable) 은 iterable 자료형의 값들을 모두 이어붙여서 반환해준다. 값들 사이에 문자를 넣고 싶다면 따옴표 사이에 넣으면 된다. 예를 들어'-'.join(['a', 'b','c']) 라는 함수가 있으면 'a-b-c'를 반환한다.

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는 단순히 중복 순열만을 위한 함수가 아니지만 알고리즘 상 중복 순열을 만들어내는 능력이 있는 것이다.
• 함수를 제대로 공부하고 싶으면 라이브러리를 참고하자.