I am an experimenter, and here is my brief digital experimental report. Best, 2023.11.04 - Hongjae Nam
My Sudoku?
Try1: 2023.11.06 ~ 2024.09.24 (Consecutive 200-Day)
[Official] End of BOJ Service, Apr. 28. 2026
My Programming Stack - Hongjae Nam
My Baekjoon YYYY - Hongjae Nam
2024.09.24 - Achieve consecutive 200-Day stacks (1st Try Baekjoon - DONE.)
My Programming Level - Hongjae Nam
https://www.acmicpc.net/school/ranklist/526 (Baekjoon, Purdue University)
2024.09.24 - Achieve consecutive 200-Day stacks (1st Try Baekjoon - DONE)
2024.08.18 - Daily > Weekly (162 stacks, or achieve 200 stacks)
2024.06.17 - Achieve BOJ Gold I (Top 10%)
2024.06.14 - Begin Intermediate Algorithm 2/3 (알고리즘 중급 2/3)
2024.06.03 - 810 정렬 (Sort) DONE, Merge Sort = O(nlogn) vs Bubble Sort = O(n^2), memory/time trade-off
2024.05.24 - 711 그리디 알고리즘 (연습) Greedy Algorithm (Practice) DONE.
2024.03.23 - Achieve BOJ Gold II (Top 15%)
2024.02.22 - Achieve Purdue & Top 7. Over 300 Puzzles (realized when I solved 321 Puzzles)
2024.02.03 - Begin Intermediate Algorithm 1/3 (알고리즘 중급 1/3)
2024.01.22 - Achieve Solved.ac Class 3 & Purdue Top 8 !
2024.01.14 - 2023.12.15 - Achieve BOJ Gold III
2024.01.06 - Begin Graph, BFS, Tree (Basic Algorithm 2/2, 60X) ~
2023.12.26 - Achieve Purdue Top 9. Over 200 Puzzles
2023.12.24 - Achieve BOJ Gold IV, Complete Basic Algorithm 1/2 (DP)
2023.12.22 - Begin Brute Force, DFS, Recursive, Permutation (Basic Algorithm 2/2, 50X) ~ 2024.01.06 DONE
2023.12.15 - Achieve BOJ Gold V
2023.12.14 - Begin Dynamic Programming (Basic Algorithm 1/2, 40X) ~ 2023.12.25 DONE.
2023.12.02 - Achieve Purdue Top 10.
2023.11.06 - Baekjoon Start !!!
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 '/')
특정 범위 숫자들의 소수 판별에는 덧셈을 활용한 Sieve of Eratosthenes 이 빠르다.
하나의 숫자 소수 판별에는 N^0.5 까지 비교하는 square root method 이 빠르다.
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
Baekjoon 문제 풀이에 한정하여, 시간초과가 문제가 된다면 Python3 대신 PyPy3로 컴파일 해보는 것도 속도를 1/2~1/3 배로 단축 시킬 수 있다. PyPy3는 Python보다 메모리를 약 2배~3배 더 많이 쓴다. 컴파일러에 따른 memory vs time trade-off 를 보여준다고 생각된다.
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
(1) que에 초기값 (여러개 가능)
(2) while q: node = q.popleft() ~ algorithms~
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 점프
Brute-force (BFS) 로 보이는 문제에서 규칙을 찾아서 Dynamic Programming (DP) 으로 풀 수 있다는 것은 꽤 흥미로운 결론.
메모리/속도 차원에서 큰 성능향상.
<Problems>
https://code.plus/course/44 (intermediate algorithm 2/3: 2024.06.14 ~)
https://code.plus/course/43 (intermediate algorithm 1/3 50X, 60X, 70X Greedy, 80X Divide-and-Conquer: 2024.02.03 - 2024.05.03 [45/75=60%] ~ 2024.06.13 [52/75=70%] )
https://code.plus/course/42 (basic algorithm 2/2: 60X Graph, BFS, Tree: 2023.01.06 - 2023.02.23 [13/12=62%] ~ )
https://code.plus/course/42 (basic algorithm 2/2: 50X DP, DFS, Recursive: 2023.12.22 ~ 2023.01.06 DONE. )
https://code.plus/course/41 (basic algorithm 1/2: 2023.12.01 ~ 2023.12.25 DONE.)
https://www.acmicpc.net/step (step 1 - 16: 2023.11.06 ~ 2023.11.30 DONE.)
<Tips>
https://baactree.tistory.com/52
https://www.youtube.com/watch?v=H6z1_tnyhp0 (Step 13, 정렬 까지 단계별로 진행, 이후에는 알고리즘 초급 1/2, 초급 2/2, 중급의 문제들을 푸는 것을 추천) ---> (나는 (1) 절취선이 있는 Step 16, 스택, 큐, 덱 까지 풀고, (2) 알고리즘 진행, (3) 단계별 풀이로 복귀하거나 처음에 목표한 하루 스도쿠처럼 자율적 풀이로 진행하는 구성으로 우선 계획)
