알고리즘 문제풀이 Tip
코테 대비 알고리즘 기본 내용 정리.
문제풀이 Tip
Python
input()
대신 sys.stdin.readline()
을 사용하라.
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
- 깊은 복사는 되도록 하지 않기. (
copy.deepcopy
) int
형의 나눗셈은float
이 반환됨.- 비교를 통한 최소값은,
sys.maximize
활용 - 함수 내부
global
사용 - dx, dy 배열 선언으로 좌표 움직임 단순화
dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0] # 상하좌우
- 배열은 함수 인자로 받을 경우, Call by reference임.
Author And Source
이 문제에 관하여(알고리즘 문제풀이 Tip), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@chlrbtlr30/알고리즘-문제풀이-Tip저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)