코테 대비 알고리즘 기본 내용 정리.

문제풀이 Tip

Python

input() 대신 sys.stdin.readline()을 사용하라.

문제 테스트 케이스를 입력받는 것이 풀이 과정에서 가장 먼저 해야 할 일임. 기본 내장함수 input() 대신 system 패키지 안의 readline()을 사용하는 것이 입력 속도에 우위를 점할 수 있다는데, 위 사항으로 인해 실행 속도가 차이나는 경험은 아직까지 해보지 못함.

보통 readline()을 사용하기 위해 lambda function과 map을 사용하는데, javascript 에서 화살표 함수와 비슷한 역할을 하는 듯. 단순 pythonic 기교이니, 깊게 이해하기보단 암기가 필요함.

import sys
input = lambda: sys.stdin.readline().rstrip()

# Single input
M = int(input())

# Double input
N, M = map(int, input().split())

# Multiple input with multiple lines
arr = [list(map(int, input().split())) for _ in range(N)] # with space

arr = [list(map(int, list(input()))) for _ in range(N)] # without space

가끔 가다 입력으로 들어오는 형식에 공백(space)이 없는 경우가 있는데, 이 때는 아래 경우로 입력받아야 함.

재귀함수의 경우, 최대 재귀 깊이를 설정해줘야 함.

DFS 문제풀이는 거의 모든 경우 재귀함수로 풀이하며, 이 때 최대 재귀 깊이를 설정해줘야함. python 의 경우, 최대 재귀 깊이는 1,000이며, 이는 매우 작으니, 반드시 늘려줘야 함.

import sys

sys.setrecursionlimit(10**8)

list / Queue / deque를 알맞게 사용하기

당연한 소리지만, 알맞은 자료구조를 사용해야함. 각 자료구조마다 장단점이 있고, 평소 무시하며 코딩하다간, 반복문 하나 때문에 시간 초과가 발생할 수 있는 경우가 허다함.

다 알겠지만, 배열은 단순히 생성 및 접근, 순회에 사용하며 배열 앞단 및 뒷단에 데이터를 조작하는 메모리 관련 조작이 필요할 경우, queue 및 deque를 사용해야 함.

사실, python의 경우 list는 append 명령의 경우 Queue 자료구조와 별 차이가 없음. 하지만 배열 중간에 데이터를 추가하는 과정은 다른 자료구조에 비해 매우 비효율적이므로, 사용하지 않는다.

반대로 queue, deque는 순회 작업으로 사용하면 안됨. C++, C와 같은 다른 언어야 순회 자체가 불가능 할 경우가 있지만, python 의 경우 for 순회가 가능하지만 사용하지 않는 것이 효율적임.

from collections import deque

Q = deque()

기타 자잘한 Tip

1. 깊은 복사는 되도록 하지 않기. (copy.deepcopy)
2. int형의 나눗셈은 float 이 반환됨.
3. 비교를 통한 최소값은, sys.maximize활용
4. 함수 내부 global사용
5. dx, dy 배열 선언으로 좌표 움직임 단순화
   dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0] # 상하좌우
6. 배열은 함수 인자로 받을 경우, Call by reference임.