My Tips for Python Codes - Hongjae Nam
Tip1: Use Dictionary for Search (e.g. x in dictionary). Time Efficient by Hash Function! - 2023.11.21 after Baekjoon 10815 (List vs Dictionary or Set)
Tip2: 나누기보다는 덧셈 ( '+' is better than '/')
Tip3: 함수화 (Funtionalization): Python에서 반복되는 기능을 함수로 만들면 실제로 빠르다! (지역 변수 vs 전역 변수) - 2023.11.24 Baekjoon 17103
Tip4: 메모리 vs 시간 (Memory vs Time trade-off) : 컴파일러 Python3 vs PyPy3 비교 - 2023.11.24 Baekjoon 17103 Goldbach Partition
Tip5: DFS (Depth-First Search ∈ Brute Force & Back-tracking ∉ Brute Force - 2023.12.23 Baekjoon 15649, N과 M (1).
(1) 상태(state, 수열의 길이 등 숫자로 가능한 것)를 시정하고 트리(tree)를 그려본다.
(2) 종료 조건 확인
(3) 반복되는 dfs(n,....) 함수 선언.
Tip6: 고민을 깊게해도 안풀렸을 때는 커뮤니티를 적극적으로 활용해볼 것. - 2023.12.25 Baekjoon
RGB2 문제에서 사소한 print/return 출력 문제에서 약 일주일간 헤맸음. 아무리 생각해도 알고리즘에 틀린 것은 없는 것 같아서 게시판에 첫질문을 올렸고, 내가 print 출력 구문을 빼먹은 것을 확인함 =). colab은 return 값을 자동으로 출력하여서 전혀 알지 못했음. 사소한 실수에서 얼마나 오래 헤맬 수 있는지, 커뮤니티를 통해서 잘 해결할 수 있는지 체감해볼 수 있는 기회였음! 성탄절 선물로 생각됨 =)
Tip7: BFS (Breadth-First Search). - 2024.01.15 Baekjoon Basic Algorithms 2/2
Tip8: 자연수값 이분 탐색 종료조건 및 중간탐색 범위 - 2024.05.31 Baekjoon 2343 기타 레슨
whlie low <= high: high = mid -1, low= mid +1 로 바꾸어 항상 low>high가 되는 상황을 만드는 잡기술 존재.
출력단에서 low, high 각각 쟈확인 필요없이, print(low) 한번만 출력.
Tip9. heapq, 우선순위 큐의 동작원리와 greedy algorithm 에서 활용 - 2024.06.10 - Baekjoon 2109 순회강연
Python import heapq 에서 사용되는 heapq는 최소힙. heapq.heappop(h) 에서 최솟값이 pop().
heapq (최소힙)은 list의 최솟값을 O(nlogn)으로 정렬해주어서, greedy algorithm을 간결하게 구현할 수 있음.
heap은 완전 이진트리의 일종으로, 여러 값 중 최대/최소 값을 빠르게 찾기 위해 만들어진 반정렬 상태.
Tip10. visited tuple set() vs visited True/False list[:] - 2024.07.01 Baekjoon 17141 연구소 2
visited tuple set() vs True/False list 자료구조만 바꾸어 메모리/시간 비교해봄.
visited tuple set() : Python3 시간초과, PyPy3 {209640 KB, 2248ms}
visited True/False list[]: Python3 {34132, 480ms}, PyPy3 {115996 KB, 284ms} = visited set() 결과의 약 1/8 시간단축. 메모리도 1/2 적게사용.
visited True/False list를 미리 선언해두는 편이 계속 set()의 크기를 변화시키면서 tuple을 저장하는 것 보다 메모리를 적게 사용하고, 접근속도도 빠르다는 결론
visited 는 tuple set() 보다는 True/False list로 선언하자!
Tip11. Brute-force(BFS, DFS)로 보이는 문제도 DP로도 가능할 때가 있음. 2024.07.06 - Baekjoon 1890 점프