테페리넷

사용자 도구

사이트 도구

현재 위치: 테페리넷 » Problem Solving » 튜토리얼 » 스니펫/템플릿 모음
ps:tutorial:snippet

목차

스니펫/템플릿 모음

  • 관련된 내용들이 여러 문서에 막 흩어져있다. 이제 여기로 모두 모으자..

기본 제어문

리스트 순회

  • 값을 얻기
    • 인덱스 접근을 하지 않는 것이 파이써닉하고 훨씬 빠르다. 여러개의 리스트를 함께 순회할때도 zip을 사용하면 여전히 인덱스 접근이 필요없다
  • 인덱스와 값을 동시에 얻기
    • enumerate를 사용하는 것이 기본으로 알려져 있지만, 그 주된 이유는 pythonic 하기 때문이지, 속도면에서는 별 차이가 나지 않는다는 것을 알아두자.
    • 모든 원소에 대해서 인덱스와 값을 얻을때 ⇒ enumerate르 쓴다
      • for i, val in enumerate(seq):
    do_something(i, val)
    • 특정 인덱스에 대해서만 값을 얻어야 할 경우라면, 값을 얻어야하는 인덱스의 수가 적다면 그냥 range를 쓰는 것이 더 효율적이다
      • for i in range(len(seq)):
    if is_valid(i):
       do_something(i, seq[i])
    • 두개의 리스트를 동시에 순회하면서 값도 얻고 싶을때:
      • [결정] 인덱스기반으로 처리한다
        • (0) 
          for i in range(len(seq1)): func(i, seq1[i], seq2[i])
      • [근거] 다른 가능한 후보들은 다음의 4가지정도 였는데
        1. for i, (val1, val2) in enumerate(zip(seq1, seq2)): func(i, val1, val2)
        2. for i, val1, val2 in zip(range(len(seq1), seq1, seq2)): func(i, val1, val2)
        3. for i, val1 in enumerate(seq1): func(i, val1, seq2[i])
        • 가독성 순위는 1>2=0>3, 속도 순위는 3>0>2»1. (1)은 속도가 유의미하게 느려서 탈락시키고, (3)은 가독성이 넘 별로라 탈락시키고 나니 남은 것중에서는 그냥 (0)를 쓰기로 결정했다.
  • 앞의 n개 원소에 대해서만 순회
    • [결정] 슬라이싱을 쓴다
      • for val in l[:n]: func(val)
    • [근거] 다른 가능한 후보들은 다음과 같다.
      1. for i in range(n): func(l[i])
      2. for i, val in enumerate(l):
    if i == n:
        break
    func(val)
      3. for i, val in zip(range(n), l): func(val)
      • 슬라이싱이 가독성과 속도 모두 다른 후보들보다 낫다.
  • 앞의 n개 원소에 대해서만 순회하되, 값과 인덱스를 모두 사용
    • [결정] 인덱스기반으로 처리한다
      • for i in range(n): func(i, l[i])
    • [근거] 값만 사용하는 경우와는 다르게 슬라이싱만으로는 처리가 안된다. 아래처럼 슬라이싱과 enumerate를 같이 쓰는 방법도 있겠는데 
      • for i, val in enumerate(l[:n]): func(i, val)
      • 이 경우는 속도가 너무 느려진다. 이 방법을 제외한 나머지 중에서는 인덱스 기반으로 처리하는 것이 가독성과 속도면에서 보두 낫다.

입력 처리

한개의 테스트 케이스를 처리하기

  • 정수 N 을 입력받기
    • N = int(input())
  • 공백으로 구분된 2개의 정수 N, M 을 입력받기
    • N, M = [int(x) for x in input().split()]
  • 공백으로 구분되어 한 줄에 주어지는 정수 배열 A를 입력받기
    • A = [int(x) for x in input().split()]
  • N줄에 걸쳐 1개씩 주어지는 정수 배열 A 를 입력받기
    • A = [int(input()) for _ in range(N)]
  • N줄에 걸쳐 주어지는 정수 배열 A와 B를 입력받기 (i번째 줄에 A[i]와 B[i]가 들어옴)
    • 가능하다면, A[i]와 B[i]를 리스트로 묶어서 리스트의 리스트 형태로 저장해서 사용하는 것이 좋다.
      • 입력 처리도 깔끔하고, 많은 경우에 이렇게 저장해두는 것이 실제 사용할때도 편리하다
      • A_and_B = [[int(x) for x in input().split()] for _ in range(N)]
    • 만약 정말로 A와 B를 각각의 리스트에 따로 나눠서 저장해야만 한다면, 그냥 A_and_B에 입력받은 다음에 다시 A와 B로 분리하는 방법을 사용하자.그냥 loop을 이용하자.
      • A_and_B = [[int(x) for x in input().split()] for _ in range(N)] 
A, B = zip(*A_and_B)
      • 위의 방법이 코드가 깔끔하기는 하지만, 성능(메모리/속도)면에서는 그냥 루프를 쓰는게 더 효율적이다. 10만줄의 데이터를 읽는 문제에서 테스트한 결과 40ms정도의 차이를 보였는데, 이 정도면 코드의 깔끔함을 위해서 감수할만한 차이이다. 하지만, 데이터의 양이 더 많아진다면 (50만줄 이상?) 이제는 효율성이 문제가 된다. 이런 상황이라면 그냥 루프를 쓰자.
        • A, B = [], []
for _ in range(N):
    A_i, B_i = [int(x) for x in input().split()]
    A.append(A_i)
    B.append(B_i)

여러개의 테스트 케이스를 처리하기

  • 한 입력데이터 안에서 여러개의 테스트 케이스를 처리해야 하는 경우이다.
  • 첫번째 줄에 테스트 케이스의 갯수를 먼저 주는 경우.
    • 가장 사용자 친화적인 형태이며 대부분의 문제가 여기에 해당한다. 다음처럼 코드 작성이 가능하다.
    • def main():
    T = int(input())
    for _ in range(T):
        # Read test data and solve
        n = int(input())
        ...
    • 출력할 때에 테스트 케이스의 번호를 같이 출력해야 하는 경우는 루프 변수를 언더바 대신에 케이스 번호로 적어주면 된다
      • 대표적으로 구글 코드잼 문제들이 이런 형태이다
  • 종료 문자가 들어올때까지 인풋을 받는 경우
    • 한줄을 문자열로 읽어서, 종료 문자열과 같으면 종료하고 그렇지 않으면 파싱해서 변수에 저장하는 식으로 쓰자.
      • 종료 문자열은 상수로 따로 저장해놓기로 했다. 문자열에 '\n'을 붙여서 저장하면 rstrip()을 매번 호출하는 것을 생략하는 아이디어도 있었지만, 지금 구조가 깔끔해서 패스.
    • END_OF_INPUT = '0'

def main():
    while (line := sys.stdin.readline().rstrip()) != END_OF_INPUT: 
        n = int(line)
        k = int(input())
        ...
  • 입력이 끝날때까지 계속 인풋을 받는 경우
    • 파일 끝에 도달했을때의 작동 방식은 input() 함수를 이용해서 입력을 받을 때와, sys.stdin.readline() 함수를 이용해서 입력을 받을 때가 다르다.
      • input()은 EOFError을 발생시킨다. sys.stdin.readline()은 빈 문자열을 리턴한다.
    • 처리하는 것은 빈문자열을 리턴하는 sys.stdin.readline() 쪽이 좀더 간단하다. 그리고 보통 이런 데이터들은 테스트의 최대 갯수가 주어지지 않는 경우가 많은데, 이럴때에는 입력량이 많을 경우에 대비해서 어차피 sys.stdin.readline()을 쓰는 쪽이 정석이기도 하다.
    • 이런 경우에는 항상 sys.stdin.readline()을 이용해서 입력을 받도록 하자!
    • def main():
    while line := sys.stdin.readline(): 
        n = int(line)
        k = int(input())
        ...

출력 처리

  • TBD

EAFP vs LBYL

  • 파이썬의 권장 스타일은 EAFP 이다. 하지만, 예외처리를 많이 쓰면 성능이 느려진다.
  • 적당한 밸런스를 잡아보자.

스택

  • 루프 안에서, 스택의 top을 확인해서 조건에 맞으면 pop 하는 로직은 매우 많이 쓰인다. 그리고 이때, 스택이 비어있는 것도 가능해서 그것을 고려해야 하는 경우도 많다.
    • (1) EAFP로 쓴다면 이렇게 될것이다
      • for i in range(x):
  try: 
    if stack[-1] == 'XX':
      stack.pop()
  except IndexError:
    pass   
  ...
      • 컴팩트하지도 않고, 속도도 느리다.
    • (2) 그래서 일반적으로는 LBYL로 이런식으로 쓴다
      • for i in range(x):
    if stack and stack[-1] == 'XX':
        stack.pop()
    ...
    stack.append(val)
      • try로 예외처리 하는 것보다는 빠르지만, 매번 if 문에서 스택이 비어있는지를 체크하는 것이 약간은 비효율적이긴 하다
    • (3) 스택이 비어있는지 체크를 하지 않아도 되도록, 스택이 항상 1개 이상의 원소를 갖고 있도록 하는 방법이 있다. pop 되는 조건을 절대 만족하지 않을 원소 한개를 스택에 처음에 넣어두는 방법이다.
      • stack = [None]
...
for i in range(x):
    if stack[-1] == 'XX':
        stack.pop()
    ...
    stack.append(val)
      • 속도가 조금 더 빨라진다. 코드도 더 컴팩트해진다. 가독성이 떨어지나? 별로 이것때문에 코드 이해 난이도가 올라갈것 같지는 않은데..
      • 이 방식을 사용하자
    • (4) 앞에 코드에서 매번 stack[-1] 이라는 인덱스 연산을 하는 것도 성능상 마음에 안들수가 있다. top 값을 다른 변수에 저장해두고 비교함으로서 인덱스 접근 연산을 최소화시켜보려고 생각할 수도 있다
      • stack = []
top = None
...
for i in range(x):
    if top == 'XX':
        top = stack.pop()
    ...
    stack.append(top)
    top = val
      • 속도는 매우 조금 빨라지긴 하는데, 이쯤 되면 가독성이 확실히 안좋아진다. append 할때마다 써야되는 코드도 더 길어진다. 이건 하지 말자..
    • 루프가 최대 백만번 돌아가는 30191 문제에서의 실행시간은 아래처럼 걸렸다 (python 3.11 기준)
      • (1): 324ms, (2): 204ms, (3): 168ms, (4): 160ms

토론

댓글을 입력하세요:
O Q B Q K
 
ps/tutorial/snippet.txt · 마지막으로 수정됨: 2024/03/13 14:49 저자 teferi