![]()
출처 : 효욜적인 약수 개수 구하기 알고리즘 :: 마이구미 :: 마이구미의 HelloWorld (tistory.com) 효욜적인 약수 개수 구하기 알고리즘 :: 마이구미 이번 글은 약수를 구하는 알고리즘을 다뤄본다.약수 구하는 방법은 어렵지 않다.하지만 조금만 응용된 약수 관련 문제라면 순수한 방법으로는 시간이 너무 오래걸린다.더 효율적인 방법을 알아 mygumi.tistory.com 약수 어떤 수를 나누었을 때 나머지가 0인 수 글을쓰게된 이유 보통 소수를 구할 때는 에라토스테네스의 체를 사용하여 효율적으로 소수를 구할 수 있다. 하지만 약수에 대해서는 여태까지 여러문제를 풀면서 효율적으로 구하는 방법을 모르고 있었다. 그래서 좋은 알고리즘을 알려주신 블로그의 코드를 참고하여 추가적으로 설명하고자 한다..
시간복잡도 순서 : O(1) -> O(log n) -> O(n) -> O(nlogn) -> O(n^2) 1. O(1) print와 단순 변수 대입의 경우에 O(1)의 복잡도를 가진다. 단, 특수 케이스로 for문이 if문으로 감싸고 있다면 그건 O(n)이 아닌 O(1)로 취급한다. why? 조건에 따른 변수 대입으로 가정하기 때문이다. 2. O(logn) 예를 들어 2의 제곱을 계속 진행했을 경우 n의 값에 도달한다면 log2n, 제곱수로 목표에 도달하기 때문에 O(n)보다 훨씬 빠르다 . 3. O(n) for문이 하나가 있을 경우에 O(n)의 복잡도를 가진다. 4. O(nlogn) logn을 n번만큼 하는 복잡도, O(n^2)대신 O(nlogn)을 만들 수 있다면 엄청난 성능향상을 기..
그래프를 기반으로 하는 알고리즘은 DFS, BFS, Dijikstra등이 있다. 정해진 틀 안에서 최소 거리를 구하고싶다 = BFS(너비 우선 탐색) 최소 거리를 구하지만 가중치를 부여하여 특정한 최소 거리를 구하고 싶다 = Dijikstra(다익스트라) 모든 경로를 탐색하고 싶다 = DFS(깊이 우선 탐색)
일반적인 큐에서 값을 정렬(내림차순)하고 싶을 때 쓸 수 있는 방법이 우선순위큐다. 이 우선순위큐의 작동 방식은 이진트리의 힙알고리즘으로 진행된다. 삽입 : 가장 끝 자식 노드에 삽입 되어 부모와 자신의 값을 비교하여 크다면 올라가고 작다면 그 곳에 머무른다. 삭제: 부모노드를 먼저 pop한 후(최대값), 큐의 가장 끝 노드를 부모에 삽입 후 역으로 값을 자식과 비교하며 내려간다. 부모의 값보다 자식노드의 값이 클 경우 교체를 한다. 만약 부모노드보다 자식노드 두개가 더 클 경우 자식 노드 중 큰 값과 부모노드가 교체된다. 힙 알고리즘의 개념을 잘 알수있다면 우선순위큐의 작동방식을 이해하기 쉽다.
