'22. 1. 28. 알고리즘 스터디 회고
주제
- 중간에서 만나기
- Union-Find
- 정수론
중간에서 만나기 (백준 1208번 : https://www.acmicpc.net/problem/1208)
문제 : 시간 복잡도에서 2^40까지 완전탐색이 불가능함(비트마스킹).
해결 : 중간에서 만나기라는 알고리즘을 사용하였음.
리스트 중심에서 왼쪽을 모두 완전탐색하여 저장한 뒤, 오른쪽 부분에서 왼쪽과 결합하였을 때 합이 N임을 만족하는 경우의 수를 구하게 되면 최대 복잡도는 2^20 * 2^20 이므로 즉 2 ^ 21이 된다. TLE가 나오지 않음.
Union Find (백준 20040번 : https://www.acmicpc.net/problem/20040)
문제 : Union-Find 과정에서 시간복잡도를 줄일 수 있는가?
해결 : 경로압축 및 Union by Rank를 사용하면 O(log(n))으로 줄일 수 있음.(둘 다 사용 시 O(1))
경로압축은 find() 함수를 실행할 때, n의 부모노드를 찾은 부모노드로 설정을 하게되면, 트리의 깊이가 얕아져 찾을 때 더 빨리 찾을 수 있음.
Union by Rank는 두 노드를 union 시 더 높은 rank에 낮은 rank의 노드를 넣는 형식으로 이도 마찬가지로 트리의 깊이를 얕게 만들 수 있음.
참고 : https://bowbowbow.tistory.com/26
정수론 https://velog.io/@axiom0510/%EC%A0%95%EC%88%98%EB%A1%A0-%EA%B8%B0%EB%B3%B8%EA%B8%B0-%EC%9E%A1%EA%B8%B0
기본적인 정수론 및 에라토스테네스의 체에 대한 내용 회고
소수 판별 알고리즘에 대해 복습하였으며 기본적인 정수의 성질, 밀러-라빈 알고리즘과 페르마의 소정리를 공부하면서 정수론에 대해 공부하였음.
