Baekjoon Online Judge (BOJ)

My Programming Stack - Hongjae Nam

My Baekjoon YYYY - Hongjae Nam

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://blog.naver.com/kks227

https://blog.encrypted.gg/category/%EA%B0%95%EC%A2%8C/%EC%8B%A4%EC%A0%84%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://baactree.tistory.com/52

https://www.youtube.com/watch?v=H6z1_tnyhp0 (Step 13, 정렬 까지 단계별로 진행, 이후에는 알고리즘 초급 1/2, 초급 2/2, 중급의 문제들을 푸는 것을 추천) ---> (나는 (1) 절취선이 있는 Step 16, 스택, 큐, 덱 까지 풀고, (2) 알고리즘 진행, (3) 단계별 풀이로 복귀하거나 처음에 목표한 하루 스도쿠처럼 자율적 풀이로 진행하는 구성으로 우선 계획)