MancityBallboy 흔적 남기기

CodingTest에 도움 될수 있는 Python 토막 지식

22 Nov 2020

Python을 이용한 Coding Test에 도움이 될 수 있는 몇 가지

제가 경험한 바에 의하면 python 코딩 테스트는 아무래도 구현보다는 최적화에서 많은 사람들이 어려움을 겪는 것 같습니다.

코드를 어떤식으로 빠르게 바꿀 수 있는가에 대한 방법은 2가지 정도 인것 같습니다.

  1. 문제에 알맞은 알고리즘을 이용한다.
    • 문제에 알맞는 알고리즘을 이미 알고 있다면 아마 굉장히 빠르게 해결 할 수 있습니다.
  2. 알려진 보다 빠른 방법을 숙지하고 이용한다.
    • 이 부분은 사실 좀 과대평가 되었다고 볼 수 도 있습니다. 왜냐하면 대부분 1번에서 해결이 될 수 있는 문제이기 때문입니다.
    • 그저 알려지지 않은 알고리즘이나 빡빡한 시간제한 때문에 고통받는 사람에게 도움이 되고 싶은 마음입니다.

일단 이번 포스팅은 2번에만 국한 되어 있는 포스팅입니다. 적지 않은 문제를 풀어오면서 저에게 문제를 푸는데 많은 도움을 준 방법들을 이야기 해 보겟습니다.

  1. 문자열을 concat할 때는 string에서 +를 이용해 직접 합치기 보다는 list에 append하여서 ''.join()으로 출력하는 것이 빠릅니다.

  2. 조합이나 순열문제가 나올 때는 재귀 보다는 import itertools를 적극적으로 이용하자.

    • 단 재귀를 이용해 풀 수 있는 사람만 이 방식을 추천드립니다.
    • 재귀가 익숙하지 않은 사람은 재귀를 이용해서 푸는 방법부터 충분히 익힌 후에 이용하시기를 추천드립니다.

  3. input()을 이용해 굉장히 많은 값을 입력받아야하는 경우

    import sys
input = sys.stdin.readline
   
N = int(input())
array = [int(input()) for _ range(N)]

    sys.stdin.readline을 이용하여 입력 받도록 합시다. 그냥 raw_input()으로 받는거보다 상당히 향상된 속도를 보장합니다.

  4. 정렬된 배열에서 어떤한 값을 찾을 때는 이진탐색을 이용하는 것이 좋습니다.

    • 사실 문제를 풀다보면 값을 찾는 문제가 굉장히 많습니다.
    • 이진탐색이 생각보다 이용할 수 있는 부분에 굉장히 많습니다.

시간 초과가 아닌 오류에 대응할 수 있는 방법

많이 겪어보지 못한 경우이므로 많은 해결 방안이 존재 하진 않습니다.

  1. 재귀를 이용하여 문제를 풀 경우 재귀 깊이가 충분하지 않아 생기는 RecursionError

    import sys
sys.setrecursionlimit(10^8)

    이와 같은 경우처럼 재귀의 깊이를 충분하게 조절 할 수 있습니다.

    하지만 이것이 무조건적인 해결 방안이 될 순 없습니다. 단순히 재귀 깊이를 깊게 조절 하는 것 뿐이지만 본인이 잘못 설계한 재귀에서 생기는 RecursionError는 해결 할 수 없습니다.

  2. 그래프를 이용한 문제를 풀 경우 생기는 메모리 초과 에러

    '''
input
10 8
1 2
3 4
2 3
4 5
6 7
8 9
9 10
1 10
'''
N, E = list(map(int, input().split()))
graph = [[0] * (N + 1) for _ in range(N + 1)]
for _ range(E):
    a, b = list(map(int, input().split()))
    graph[a][b] = 1
    graph[b][a] = 1                           ## 행렬을 이용한 그래프 저장 방법
       
graph = [[] for _ in range(N + 1)]
for _ range(E):
    a, b = list(map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)                        ## 인접 리스트로 저장

    무방향 그래프를 저장하는 방법은 대표적으로 행렬을 이용한 방법 인접리스트를 이용한 방법이 있습니다.

    행렬을 이용했을때 메모리초과에러가 날 경우 인접리스트를 이용해 구현 한다면 에러를 피할 수 있었습니다.

사실 이런 글을 써도 될지 모르겠을 정도로 많이 부족하다고 생각합니다. 저의 개인적인 경험으로 엮어 낸 것이다 보니 정확하지 않을 수 있다는 점 고려 부탁 드립니다. 더 나은 방법이나 바뀐 정보가 있다면 업데이트 하도록 하겠습니다.

Related posts