메모리 사용량 : 사전 > 리스트 → 메모리 초과 날 경우, 사전으로 구현한 그래프를 리스트로 바꿔보기. → 백준 1967 트리의 지름 문제
deque를 통할 경우 메모리가 초과가 날 경우 → deque에는 중복된 값들이 들어갈 수도 있기 때문에, 같은 동작을 반복할 우려가 있다! → 이 경우 set을 이용해서 반복된 로직을 없앨 수 있다. → 집합에서 pop은 임의의 수를 꺼낸다 -> 어차피 bfs 돌리면 큐 안에 있는 모든 지점에서 돌아가기 때문에 상관이 없어짐. → 백준 1987 알파벳 문제
파이썬 string에 접근할때, 아래처럼 string 그대로 접근하는 것이 아닌, list화 해서 인덱스로 접근하는것이 시간 측면에서 빠르다. → 백준 1987 알파벳 문제
str = "abcd"
str_lst = list(str)
print(str[1])
print(str_list[1])
최단경로를 구할 때, visit 배열? → bfs 탐색할 때 visit 배열을 생성하는 것이 아닌, 한개만 생성하고 사용해도 된다. → 최단 경로이기 때문에! 한번 방문 한 곳에 다시 방문하는 것은 최단 경로가 될 수 없다. → 최단경로와 도달 가능 경우의 수를 구하는 것의 차이.
파이썬 set의 시간 복잡도
→ 파이썬에서 집합은 해시로 이루어지기 때문에 in 판별 시간 복잡도가 O(1)이다! → 하지만, 메모리적인 측면에서 배열 보다 크다. → visit 배열을 배열로 관리할 것인가, 집합으로 관리할 것인가?
for 문에서의 효율성
→ 밑의 코드에서 case1 처럼 하면 반복문을 돌 때마다 len을 계산한다. → 하지만, case2 처럼 하게 된다면 len을 계산하는 과정을 계속하지 않기 때문에 훨씬더 효율적이다. → 백준 12015 가장 긴 증가하는 부분 수열2
g = [1,2,3,4]
n = len(g)
# case 1
for i in range(len(g)):
~~~~
# case 2
for i in range(n):
~~~~
마지막에 특정 n으로 나누시오. 왜?
이 문제와 같이 "~로 나눈 나머지를 출력한다"는 문제는 거의 대부분 전체 답을 먼저 구하고 마지막에 나머지 연산을 한 번 하라는 것이 아니라, 연산 과정에서 모듈로의 성질을 이용하여 수를 계속 작게 유지할 수 있도록 배려를 해주는 것입니다. 안 그러면 수가 너무 커져서 계산 시간도 오래 걸릴 뿐만 아니라 파이썬처럼 bigint를 지원하지 않는 언어에서는 구현하는 것 자체가 매우 까다롭기 때문입니다.
부동소수점 오류의 문제
흔히 코딩 테스트는 실수형 데이터를 비교할 때 소수점 다섯 번째 자리에서 반올림한 결과 같으면 정답으로 인정한다.
비트 마스킹
동적 계획법 (DP) 과 비트 마스킹 (Bit Masking)
소수 판별
이진 탐색
# upper bound
while(left <= right):
if mid <= k:
left = mid + 1
else:
right = mid - 1
return right
# lower bound
while(left <= right):
if mid < k:
left = mid + 1
else:
right = mid - 1
return left