백준 파이썬 숏코딩 팁 (Python Code Golf)

나는 백준을 풀다가 숏코딩 할만한 문제(최종 코드의 추정 길이가 대략 200 bytes 이하?)가 나오면 숏코딩을 한다.

적지 않은 문제를 하다보니 나름 내공이 쌓인 것 같아 내가 아는 한에서 그 팁들을 정리해 보고자 한다.

코드의 길이를 줄일 수 있는 방법이라면 떠오르는 대로 최대한 소개하겠다.

작성할 만한 내용이 떠오르는대로 틈틈이 쓸 예정이다.

혹시 내가 작성한 코드를 더 줄일 수 있는 방법을 아신다면 편하게 지적해 주시길 바란다.

 

1. 공백 제거와 세미콜론
2. 변수 이름 단축
3. 불필요한 변수 사용 줄이기
4. 알고리즘의 수정
5. open(0)을 이용한 입력 부분 간소화
6. 특수 문법의 이용
7. 수학의 이용
8. True==1, False==0
9. 별표(*, asterisk)의 이용
10. eval() 함수와 exec() 함수
11. 배열의 평면화
12. 자잘한 팁

1. 공백 제거와 세미콜론

숏코딩의 기본이자 누구나 알 수 있는 것이다.

공백이나 가독성을 위해 분리한 단락을 최대한 제거해 주자.

인덴트도 최소한으로 줄여주자.

또한 중의성이 발생하는 상황이 아니라면 세미콜론을 이용해 인덴트를 제거할 수도 있다.

피보나치 수를 출력하는 코드에 대한 예시이다.

n = int(input())

a = 0
b = 1
for _ in range(n-1):
    temp = a
    a = b
    b += temp

print(b)

n=int(input())
a=0
b=1
for _ in range(n-1):temp=a;a=b;b+=temp
print(b)

2. 변수 이름 단축

공백만 줄였을 뿐인데 벌써 가독성이 개똥이 되었다.

하지만 아직 이 코드가 무슨 기능을 하는지 바로 눈에 들어온다는 것은 코드를 줄일 여지가 더 많다는 것이다.

이제 성심성의껏(?) 지어 놓은 변수의 이름들을 한 글자로 줄여버릴 것이다.

웬만한 IDE에서는 f2키를 이용해 변수의 이름을 한번에 변경할 수 있다.

위의 피보나치 코드에서는 temp를 짧게 변경할 수 있다.

n=int(input())
a=0
b=1
for _ in range(n-1):t=a;a=b;b+=t
print(b)

3. 불필요한 변수 사용 줄이기

어떤 변수가 재사용되지 않는다면 그냥 그 변수를 사용하는 곳에 바로 넘겨버릴 수 있다.

이렇게 변수 n을 제거할 수 있다.

그리고 위의 피보나치 코드에서 사실 temp(혹은 t)는 필요가 없다.

파이썬은 하나의 문장으로 두 변수에 동시에 값을 할당할 수 있다.

a=0
b=1
for _ in range(int(input())-1):a,b=b,a+b
print(b)

함수에 전달되는 인자도 그 변수를 사용만 하는 것이라면 함수의 인자를 제거할 수 있다.

다음과 같이 1부터 입력한 수까지의 자연수의 합을 구하는 함수를 고려해보자.

def get_sum(n):
    return n * (n+1) // 2

n = int(input())
print(get_sum(n))

이 함수에서는 변수 n을 사용만 하므로 인자에 n을 주지 않아도 된다.

따라서 다음과 같이 수정이 가능하다.

def get_sum():
    return n * (n+1) // 2

n = int(input())
print(get_sum())

 

이를 이용하여 18251번에 숏코딩을 해보았다. 변수 s, e가 전역변수로 기능함을 이용해서 함수 F의 인자의 개수를 3개에서 1개로 줄였다.

● 인자 제거 전

def F(i,s,e):return F(i*2,s,e)+[t[i]]*(i>=s)+F(i*2+1,s,e)if i<e else[]
n,a,*_=t=[*map(int,open(0).read().split())]
e=1
while e<n:
 s=e=e*2
 while~-s:
  s//=2;c=0
  for i in F(1,s,e):a=max(a,c:=max(i,i+c))
print(a)

● 인자 제거 후

def F(i):return F(i*2)+[t[i]]*(i>=s)+F(i*2+1)if i<e else[]
n,a,*_=t=[*map(int,open(0).read().split())]
e=1
while e<n:
 s=e=e*2
 while~-s:
  s//=2;c=0
  for i in F(1):a=max(a,c:=max(i,i+c))
print(a)

4. 알고리즘의 수정

알고리즘을 수정하자.

결과적으로는 같은 결과가 나오지만 그 중간에 행동은 미세하게 다를 수 있게 말이다.

다음은 피보나치 코드를 교묘하게 변경한 두 가지 예시이다.

a=1
b=0
for _ in range(int(input())):a,b=b,a+b
print(b)

a=b=1
for _ in range(int(input())-1):a,b=b,a+b
print(a)

변수 n을 다시 사용하면 더 짧게 할 수 있다.

위의 두 코드보다 한 글자 짧다.

n=int(input())
a=1
b=0
while n:a,b=b,a+b;n-=1
print(b)

아예 시간복잡도를 증가시킬 수도 있다.

문제의 주어진 시간 안에 통과만 가능하다면 이런 덜떨어진 방법도 code golf의 능력 중 하나이다(?).

백준 5582번이 좋은 예시이다.

최적의 알고리즘을 이용하면 133 bytes 정도로 해결되지만 무식한(?) 알고리즘을 사용하면 91 bytes까지 줄일 수 있다.

● 효율적이고 정석적인 알고리즘을 통한 5582번의 숏코딩

d=[0]*8**8
a,b=open(0)
x=len(b)-1
for i in range(len(a)-1):
 for j in range(x):
  if a[i]==b[j]:d[-~i*x+j+1]=d[i*x+j]+1
print(max(d))

● 비효율적인 알고리즘을 통한 5582번의 숏코딩

a,b=open(0)
s=e=r=0
while-~s<len(a)>e:r,s=[r,max(r,e-s),s+1,s][a[s:e]in b::2];e+=1
print(r)

5. open(0)을 이용한 입력 부분 간소화

반복된 input()의 사용을 한 줄로 처리할 수 있다면 얼마나 좋을까?

파이썬은 감사하게도 open(0)을 통해 표준 입력을 한번에 받을 수 있다.

또한 많은 input()으로 인해 시간초과가 발생할 때 sys.stdin.readline()을 사용하는 대신 이것을 이용할 수도 있다.

open(0)에 대한 근본적인 설명은 이 글을 참고하자

자주 사용되는 두 가지 예시이다.

● open(0).read()

EOF 이전까지의 모든 입력을 하나의 문자열로 리턴한다.

# input() 이용
a,b,c=map(int,input().split())
x,y,z=map(int,input().split())

# open(0).read() 이용
a,b,c,x,y,z=map(int,open(0).read().split())

● open(0)

표준 입력을 newline으로 구분하여 iterable한 형태로 사용할 수 있게 해준다.

'''
[example input]
3
123
346
832
'''

# input()만을 이용한 경우
n=int(input());k=[int(input())for _ in' '*n]

# *open(0)을 이용한 경우
n,*k=map(int,open(0))

위 코드에서 *k의 문법에 의문이 든다면 9번 단락을 참고하자.

6. 특수 문법의 이용

● 연달은 등호의 이용

위의 알고리즘의 수정 단락에서 a=b=1과 같은 형태의 코드를 보았을 것이다.

이러한 문법은 사용할 때마다 무려 1 byte의 코드를 줄여줄 수 있다.

같은 값의 변수를 여러개 만들어 두어야 할 때 사용하면 된다.

같은 값의 변수가 없다면 알고리즘을 수정하여 달랐던 변수들의 초깃값을 동일하게 만드는 트릭을 사용할 수도 있다.

(알고리즘의 수정 단락의 2번째 코드처럼)

# a=1; b=1
a=b=1

# c=(1,2); d=1; e=2
c=d,e=1,2

● 바다코끼리 연산자 (:=)

파이썬 3.8에 도입된 이 연산자를 처음 듣는 사람도 있을 것이다.

그만큼 대부분의 정상적인 코드에서는 사용할 이유가 거의 없다.

이 연산자는 우측의 값을 좌측 변수에 할당하는 동시에 리턴한다. C언어의 =연산자와 비슷한 역할을 한다고 볼 수 있다.

다음은 사용 예시이다. 무려 한 글자가 줄었다!

a=[1]*10
b=1
print(sum(a)+b)

a=[b:=1]*10
print(sum(a)+b)

7. 수학의 이용

● bitwise negation의 활용

어떤 수에 1을 더한 값을 다른 값과 곱해야 할 때 괄호 두 개를 더 쓰는 게 왠지 모르게 상당히 억울하다.

그럴 땐 다음을 이용하자.

a=3
b=5
print((a-1)*(b+1))
print(~-a*-~b)

실행시켜 보면 둘 다 12가 출력될 것이다.

~는 bitwise negation 연산자이고 -는 우리가 아는 sign negation 연산자이다.

이를 이용해서 어찌저찌하니 1을 더하거나 뺀 값을 내놓는다.

또한 아래처럼 여러 수식을 짧게 쓸 수 있다.

(x+1)**2
~x*~x

x=x*2+1
x-=~x

공백도 없앨 수 있다.

if a+1:do_something()
if-~a:do_something()

while a-1:do_something()
while~-a:do_something()

-10, -100 등을 표현할 때도 bitwise negation을 활용하자. (이건 거의 창의력 대회 같다)

print(-10 == ~9)
print(-100 == ~90)
print(-1000 == ~999)
print(-10000 == ~9999)

 

사실 ~x == -x-1이다. 이를 응용해서 적절히 잘 사용하자.

이를 이해하기 위해서 2의 보수를 알아야 하는데 컴공 공부하러 온 게 아니니 일단 넘어가자.

● 논리 연산

조건문에서 논리 연산을 잘 이용해 보자.

서로 동치인 논리 연산은 적극적으로 이용하자.

for a,b in ((True,True),(True,False),(False,True),(False,False)):
    print(not(a or not b))
    print(not a and b)
    print(a|b-1==0)
    print(~a&b)
    print()

매 loop에 대해 같은 결과가 나온다.

8. True==1, False==0

Boolean type을 숫자로 이용할 것이다. True나 False는 수처럼 연산이 가능하고 인덱싱도 된다. 삼항연산이나 조건문에서 코드의 길이를 줄일 수 있다.

● Boolean type을 수로 이용하는 예시

100까지의 수 중에서 3의 배수의 개수를 세는 코드이다.

num=[i for i in range(1,101)]
print(sum(i%3==0 for i in num))

● 인덱싱으로 사용하는 예시

입력한 문자열이 수 형태인지 판단하는 코드이다.

두 출력 결과는 항상 같으나 아래 코드가 더 짧다.

a=input()
print("alphabet"if a.isalpha()else"numeric")
print(["numeric","alphabet"][a.isalpha()])

9. 별표(*, asterisk)의 이용

파이썬에서 별표 연산자는 사용 위치에 따라 다양한 기능이 있다. 그중 unpacking은 숏코딩에서 매우 유용하다. 사용 예시도 다양하다.

● 공백을 사이로 두고 출력

아직도 공백을 사이로 두고 출력을 할 때 ' '.join()을 사용하면 매우 유감이다.

newline을 사이로 두고 출력을 요구할 때 아래와 같이 사용해도 통과가 가능하다.

단, 요구 출력에 공백과 newline이 섞여있다면 먹히지 않는다.

nums = [i for i in range(10)]

# output: "0 1 2 3 4 5 6 7 8 9"
print(' '.join(map(str,nums)))
print(*nums)

● 함수에 인자 넘기기

from math import pow
to_power = [3,4]

# output: "81 81"
print(pow(to_power[0],to_power[1]), pow(*to_power))

● 리스트로 입력받기

# example input: "5 1 3 5 7 9"
n,*nums = map(int, input().split())
print(sum(nums))

● 리스트로 입력받기 고급

# input:
# 1 2
# 3 4
# 5 6
# 7 8

[n,m],*a=[map(int,i.split())for i in open(0)]
for x,y in a:print(x,y)

n과 m에는 1과 2가 각각 저장되고 a에는 둘 째 줄부터의 map object들이 저장된다.

입력이 예시와 같은 상황에서, 첫째 줄의 정보를 저장하며 둘째 줄부터 반복해야 할 때 (내가 알기로는) 가장 짧게 작성할 수 있는 방법이다.

아래에서도 사용 예시를 볼 수 있다.

10. eval() 함수와 exec() 함수

파이썬에서 eval() 함수와 exec() 함수는 매우 특이한 기능을 한다.

eval()은 인자로 들어온 문자열을 마치 수식처럼 계산하여 그 결과를 내놓고,

exec()는 인자로 들어온 문자열을 파이썬 코드로 실행해 준다.

아래의 코드는 이 두 함수를 이용해 변수 a에 3과 4를 더한 값을 할당한다.

a = eval("3 + 4")
exec("a = 3 + 4")

이 두 함수 또한 숏코딩에 활용할 수 있다.

단, 반복 횟수가 많아 eval이나 exec를 자주 실행하게 되면 time out이 발생할 수 있다.

때문에 두 함수의 실행 횟수를 최소화 하면서 숏코딩을 해야한다.

● eval()

백준의 기본 문제 1000번 'A+B'의 숏코딩에 사용될 수 있다.

print(eval('+'.join(input())))

7490번에서 사용한 경험이 있다.

def M(i,s):[M(i+1,s+a+str(i+1))for a in" +-"]if i-int(n)else eval(s.replace(" ",""))==0and print(s)
for n in[*open(0)][1:]:M(1,"1");print()

● exec()

같은 횟수의 동일한 코드를 반복할 때 사용하면 코드의 길이를 줄일 수 있다.

n = int(input())

for _ in' '*n:do_something()
exec('do_something();'*n)

2133번에서 사용한 경험이 있다.

그렇게 잘한 숏코딩은 아니다. 더 줄일 수 있다.

a=1,0,3,0
exec('a+=4*a[-2]-a[-4],;'*27)
print(a[int(input())])

 

굳이 반복이 아니라 같은 내용의 코드를 여러번 사용할 때도 유용하다.

아래는 각각 2024번의 exec를 사용하지 않은/사용한 두 코드이다. (187 bytes -> 184 bytes)

m,*v=map(int,open(0).read().split())
v=sorted(zip(v[::2],v[1::2]))
a=c=i=0
while i<len(v)and v[i][e:=0]<=c<m:
 while i<len(v)and v[i][0]<=c:e=max(e,v[i][1]);i+=1
 c=e;a+=1
print(a*(c>=m))

m,*v=map(int,open(0).read().split())
v=sorted(zip(v[::2],v[1::2]))
a=c=i=0
s='while i<len(v)and v[i][0]<=c'
exec(s+'<m:\n e=0\n '+s+':e=max(e,v[i][1]);i+=1\n c=e;a+=1')
print(a*(c>=m))

● 복합사용

5052번에서 둘 다 사용하며 코드의 길이를 줄였다. (123 bytes -> 118 bytes)

위와 아래는 eval()과 exec()의 사용 전 후 코드이다.

I=input
for _ in' '*int(I()):s=sorted(I()for _ in' '*int(I()));print('YNEOS'[any(i==j[:len(i)]for i,j in zip(s,s[1:]))::2])

I=input
exec("s=sorted(eval('I(),'*int(I())));print('YNEOS'[any(i==j[:len(i)]for i,j in zip(s,s[1:]))::2]);"*int(I()))

 

11. 배열의 평면화

2차원 이상의 배열을 1차원으로 평면화 하는 것이다.

배열을 선언할 때 길이를 크게 줄일 수 있다.

경험적으로 다이나믹 프로그래밍이나 격자형 그래프 관련 문제에서 이득을 보는 경우가 많았다.

n,m=map(int,input().split())

# (n,m)의 2차원 배열
a=[m*[0]for _ in' '*n]
dynamic_programming()
print(a[-1][-1])

# (n*m,)의 1차원 배열
b=[0]*n*m
dynamic_programming()
print(b[-1])

다만 배열의 요소에 접근할 때는 다음과 같이 길이가 늘어날 수 있다.

print(a[i][j])

print(b[i*m+j])

그럼에도 불구하고 잘 사용하면 이득을 볼 수 있다.

다음은 10942번에서의 예시이다.

# 2차원 배열: 187 bytes
(n,),a,_,*q=[[*map(int,i.split())]for i in open(0)]
d=[n*[1]for _ in' '*-~n]
for i in range(n):
 for j in range(n-i):d[j][j+i]=(a[j]==a[j+i])*d[j+1][j+i-1]
for s,e in q:print(d[s-1][e-1])

# 1차원 배열: 177 bytes
(n,),a,_,*q=[[*map(int,i.split())]for i in open(0)]
d=-~n*n*[1]
for i in range(n):
 for j in range(n-i):d[j*n+j+i]=(a[j]==a[j+i])*d[-~j*n+j+i-1]
for s,e in q:print(d[~-s*n+e-1])

12. 자잘한 팁

이외의 자잘한 팁들이다.

• 특정 횟수만큼 반복하지만 몇 번째 반복인지 알 필요는 없을 때 in range(n) 대신 in‘ ‘*n을 이용하자. 혹은 n의 값을 1씩 줄이면서 while n:과 같은 형식을 이용하는 게 더 좋을 때도 있다. 여러 가지를 고려하자.
• 리스트에 원소를 추가할 때 append는 쳐다보지도 말자. a.append(1)과 a+=1,은 같은 기능을 한다.
• 마찬가지로 세트에 원소를 추가할 때는 a.add(1) 대신 a|={1}을 사용하자.
• range나 print 따위가 빈번하게 쓰인다면 r=range 혹은 p=print와 같이 새로운 변수를 이용해 코드의 길이를 줄일 수 있다. 하지만 이러한 코드는 애초에 근본적으로 길이를 줄일 수 있는 경우가 많다.
• 큰 공간의 리스트를 선 할당할 필요가 있을 경우 공간의 크기를 그대로 쓰기보다 제곱을 이용하여 크기를 여유롭게 작성하자. 예를 들어 최소 1천만 개의 0이 들어있는 리스트를 만들어야 할 때 a=[0]*8**8과 같이 사용하면 좋다.
• 충분히 큰 수가 필요한 경우 큰 수를 직접 쓰는 것보다 1e9 등의 표현을 이용하는 것이 좋다. 단, 표현은 float type이므로 큰 리스트를 만드는 행위 등에는 적합하지 않다.
• if대신 and, if not 대신 or을 이용하면 코드의 길이가 줄어들 수 있다. (특히 loop이나 함수 내에서)

# 24자
def f():
 if foo():bar()
# 22자
def f():foo()and bar()

# 26자
def g():
 if not foo():bar()
# 21자
def g():foo()or bar()