Pypy3 vs Python3
# 10989 수 정렬하기 3
import sys
input = sys.stdin.readline
n = int(input()) # 입력 (n개의 수)
NumIndex = [0] * 10001 # 최대 숫자 크기인 10000까지 인덱싱 처리
for _ in range(n): # 숫자에 해당하는 인덱스에 갯수 추가
NumIndex[int(input())] += 1
# 10000까지 반복
for i in range(10001):
if NumIndex[i] != 0: # i인덱스가 0이 아니라면 존재하는 수 -> 존재하는 만큼 출력해줌
for j in range(NumIndex[i]):
print(i)
백준의 10989번의 수정렬하기3의 경우 pypy3로 제출했을때 메모리 초과가 발생한다.
코딩테스트를 보면서 대체적으로 Pypy3가 무조건 좋다라고 생각하고 있었기때문에 조금 충격이였다.
Pypy3가 python3에 비해 속도가 빠르지만 그만큼 메모리를 사용한다고 한다.
결론은 pypy3를 쓰다 메모리부족이뜨면 Python3으로 시도하자!
재귀
def rec(n):
if n > 0:
rec(n-1)
print(n)
rec(n-2)항상 재귀를 사용하면서 제대로 이해하고 넘어가지 않았던 것 같다.
이번 기회로 제대로 이해해보려했고, 위의 코드가 가장 도움이 되었다.
위의 코드의 흐름은 어떻게 될까?
rec(4)일 경우 출력 값은
1 -> 2 -> 3 -> 1 -> 4 -> 1 -> 2 이런 흐름이 된다.
rec(n-1) - print(n) - rec(n-2) 를 그래프화해서 좌우로 퍼트려서 이해하니 도움이 많이 되었다.
재귀에 대한 이해는 어느 정도 되었다고 생각이 되고, 문제에 적용하는 것은 더 노력해야겠다.
"백트래킹"
모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다. 그냥 뇌없이 짤 수 있다는 것이 장점이다. - 나무위키
아직 배웠다고 하기에 완벽하지 않아서 설명글을 추가했다.
쉽게 이해하기에는 탐색하고, 조건에 맞지않으면 되돌아가서 다음 경우의수로 나아간다.
완전탐색시 수많은 경우의수가 있을 것이고, 막혔을때 되돌아가지않고 다시 나아갈 수 있게한다는게 가장 중요한 것같다.
이렇게 백트래킹에 관한 TIL을 남기면서도 자신이 없다.
더 깊이 알아보고 적용해봐야 할 것 같다.
내일의 나에게🥲
- 에라토스테네스의 체
- DFS,BFS 이해
- 백트래킹
