☁️ Algorithm10 소수 구하는 방법 (Java) 약수 알고리즘 (Java) 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 hyeon-z.tistory.com 이전에 작성했던 약수 알고리즘을 바탕으로 설명할 것이다. 방법 1 소수는 1과 자기 자신만을 약수로 가지기 때문에 2부터 자기 자신 - 1까지 반복문을 돌면서 나누어 떨어지는 수가 없다면 소수이고, 나누어 떨어지는 수가 있다면 소수가 아니다. boolean solution(int num) { // 1은 소수 x if (num == 1) { return false; } // 2부터 자기 자신-1.. 2023. 5. 18. 최대공약수, 최소공배수 (feat. 유클리드 호제법) 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 위의 문제를 구현하다 더 쉽게 최대공약수와 최소공배수를 구하는 방법을 알게 되어 작성한다. 최대공약수 구하는 방법 방법 1: 각 수의 약수를 구한 후 공통되는 최대값 찾기 위의 문제를 풀면서 처음 생각한 방법이다. 예를 들어 18과 24의 최대공약수를 구해야한다. 18의 약수: 1, 2, 3, 6, 9, 18 24의 약수: 1, 2, 3, 4, 6, 8, 12, 24 이들의 공약수는 1, 2, 3, 6이고 가장 큰 값인 6이 최대공약수가 된다. 약수 알고리즘 (Java) 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때.. 2023. 5. 18. 약수 알고리즘 (Java) N의 약수의 개수을 구하려면 어떻게 해야 할까? 방법 1 1부터 N까지 모든 수를 돌며 나누어 떨어지는 수의 개수를 더한다. int N = 16; int result = 0; for (int i = 1; i [N/3] 7 이하의 자연수 중에서 4를 약수로 가지는 수의 개수: 1 (4) => [N/4] 7 이하의 자연수 중에서 5를 약수로 가지는 수의 개수: 1 (5) => [N/5] 7 이하의 자연수 중에서 6을 약수로 가지는 수의 개수: 1 (6) => [N/6] 7 이하의 자연수 중에서 7을 약수로 가지는 수의 개수: 1 (7) => [N/7] 약수가 아닌 수들을 계산하지 않고 확실히 약수인 개수만 찾기 때문에 빠르게 구할 수 있다. int N = 7; int result = 0; for (int i.. 2023. 5. 17. 이진 탐색 트리(Binary Search Tree) (Java) 트리에 대해 정리한 게시글이다. 해당 게시글을 읽기 전 참고하면 좋을 것 같다. 트리(Tree) (Java) 트리(Tree)란? 트리 구조란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다. 용어 트리 구조를 보며 알아야 할 용어들이 몇 개 있다. 부모 노드(parent node) : 자기 자신(노드)과 연결된 hyeon-z.tistory.com 이진 탐색 트리(Binary Search Tree)란? 이진 + 탐색 + 트리 즉, 이분화된 탐색을 위한(혹은 특화된) 트리 자료구조이다. 이진 트리 (Binary Tree) 모든 노드의 최대 차수를 2로 제한한 트리. 각 노드는 자식 노드를 최대 2개까지 가질 수 있다. 탐색에 특화된 트리 ❓위의 이진 트리의 각 노드가 갖고 있는 값이 규칙이 없다면 .. 2023. 5. 3. 트리(Tree) (Java) 트리(Tree)란? 트리 구조란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다. 용어 트리 구조를 보며 알아야 할 용어들이 몇 개 있다. 부모 노드(parent node) : 자기 자신(노드)과 연결된 노드 중 자신보다 높은 노드를 의미 (ex. F의 부모노드 : B) 자식 노드(child node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 낮은 노드를 의미 (ex. C의 자식노드 : G, H) 루트 노드 (root node) : 일명 뿌리 노드라고 하며 루트 노드는 하나의 트리에선 하나밖에 존재하지 않고, 부모노드가 없다. 위 이미지에선 녹색이 뿌리노드다. 단말 노드(leaf node) : 리프 노드라고도 불리며 자식 노드가 없는 노드를 의미한다. 위 이미지에서 주황색 노드가 단말노.. 2023. 5. 3. 이진 탐색(Binary Search) (Java) 이진 탐색이란? "정렬된 배열"에서 특정한 값을 찾아내는 알고리즘 배열의 중간 값과 찾고자 하는 값을 비교하면서 탐색한다. 찾고자 하는 값이 X라고 하면, X가 중간 값보다 작으면 좌측 데이터를 대상으로, X가 중간 값보다 크면 우측 데이터들을 대상으로 다시 탐색한다. 해당 과정을 X를 찾을 때까지 반복한다. 시간 복잡도 전체 데이터 수를 N이라고 하자. 1) 첫 번째 탐색 후 절반만 남아 남은 수가 N/2개 2) 두 번째 탐색에서 다시 절반만 남아 남은 수가 N/2 ×1/2개 3) 세 번째 탐색에서 다시 절반이 남아 남은 수가 N/2 ×1/2 ×1/2개 ... k) 규칙을 찾아보면 k번째 탐색에서 남은 데이터 수는 (1/2)^k * N이 된다. 최고의 경우 중간 값이 찾고자 하는 값인 경우에는 한 번에.. 2023. 5. 3. 이전 1 2 다음
