수학 알고리즘 - 순열과 조합 알고리즘(재귀, 반복문)

순열이란 집합의 요소들을 중복없이 특정한 순서로 나열하는 것을 말합니다. 예를 들어 {1, 2, 3}으로 집합이 주어져있을 때 2개를 순열로 만들면 {1,2},{1,3},{2,1},{2,3},{3,1},{3,2}이 됩니다. 서로 다른 n개의 원소에서 r개를 선택하여 나열하는 경우의 수를 말합니다. 조합이란 집합의 요소들 중에서 중복없이 일부를 선택하여 순서에 상관없이 나열하는 것을 말합니다. 예를 들어 {1,2,3}으로 집합이 주어져있을 때 2개를 조합하면 {1,2},{1,3},{2,3}이 됩니다. 서로 다른 n개의 원소에서 r개를 선택하는 경우의 수를 말합니다. 반복문을 이용한 조합 코드 예시 function combination(arr) { const result = [] for(let i = 0; ..

• format_list_bulleted 알고리즘/초급 알고리즘
• · 2024. 4. 3.
• textsms

수학 알고리즘 - 거듭제곱 알고리즘(반복문, 분할정복)

거듭 제곱이란 거듭 제곱은 한 수를 다른 수의 거듭제곱으로 나타내는 것을 말합니다. 2의 3승은 2 * 2 * 2 = 8입니다. 반복문을 이용한 거듭 제곱 코드 예시 function power(n, m) { let result = 1 for(let i = 1, i > 1, r) } return fastPower(n, m, 1) } 숫자와 지수를 받아서 거듭제곱하는 함수입니다. 재귀를 통해 r에 현재 계산 결과를 가지고 있습니다. 만약 지수가 0이면 현재 계산 결과를 반환합니다. 지수가 홀수이면 숫자를 한번더 곱합니다. 2^5이면 2^2 * 2^2 * 2이 계산이기때문에 홀수일 때 숫자를 더 곱해야됩니다. 지수가 짝수면 지수는 반으로 줄이고 숫자를 제곱하여 넘겨줍니다. 2^4 = 2^2 * 2^2 2^2 ..

• format_list_bulleted 알고리즘/초급 알고리즘
• · 2024. 4. 2.
• textsms

수학 알고리즘 - 소수 판별 알고리즘(브루트 포스, sqrt, 에라토스테네스의 체)

소수란 소수는 1과 자기 자신으로만 나누어지는 양의 정수입니다. 예를 들어 2, 3, 5, 7, 11등이 있습니다. 브루트 포스를 이용한 소수 판별(n -1까지) 코드 예시 function isPrime(num) { for(let i = 2; i < num; i++) { if(num % i === 0) return false } return true } 2부터 시작하여 num - 1까지 나머지를 검사하면서 0이 있으면 소수가 아니고 나머지가 0이 하나라도 없으면 소수입니다. 브루트 포스를 이용한 소수 판별(sqrt 까지) 코드 예시 function isPrime(num) { for(let i = 2; i

• format_list_bulleted 알고리즘/초급 알고리즘
• · 2024. 4. 1.
• textsms

수학 알고리즘 - 최소 공배수(LCM) 알고리즘

최소 공백수란 최소 공백수는 두 개 이상의 정수를 나누어 떨어지게 하는 가장 작은 양의 정수를 말합니다. 예를 들어 6와 8의 최소 공배수는 24입니다. 최소 공백수 알고리즘 서로소 x 최대 공약수 = 최소 공백수가 나옵니다. (두 개의 정수 곱) / 최대 공약수 = 최소 공백수가 나옵니다. 유클리드 호제법을 이용한 최소 공백수 코드 예시 function gcd(a, b) { while(b !== 0) { let r = a % b a = b b = r } return a } function lcm(a, b) { return (a*b) / gcd(a, b) }

• format_list_bulleted 알고리즘/초급 알고리즘
• · 2024. 4. 1.
• textsms

수학 알고리즘 - 최대 공약수(GCD) 알고리즘(유클리드 호제법)

최대 공약수 개요 최대 공약수는 두 개 이상의 정수를 나누어 떨어지게 하는 가장 큰 양의 정수를 말합니다. 예를 들어, 12와 18의 최대 공약수는 6입니다. 소인수 분해를 이용한 최대 공약수 동작원리 두 수를 소인수분해합니다. 공통된 소인수들을 찾아냅니다. 공통된 소인수들의 곱이 최대 공약수입니다. 소인수 분해를 이용한 최대 공약수 코드 예시 // 소인수 구하기 function getPrimeFactors(n) { const factors = [] let divisor = 2 while(n >= 2) { if(n % divisor === 0) { factors.push(n) n /= divisor } else { divisor++ } } } // 최대공약수 구하기 function gcd(a, b) { ..

• format_list_bulleted 알고리즘/초급 알고리즘
• · 2024. 4. 1.
• textsms

재귀 알고리즘 - 하노이 탑 이해와 효율적인 구현 방법

하노이 탑이란? 이 문제는 세 개의 기둥과 한 기둥에 쌓여 있는 원반들로 구성되어 있습니다. 원반의 크기는 모두 다르며, 규칙에 따라 큰 원반이 작은 원반 위에 있어서는 안 됩니다. 목표는 최소 이동 횟수로 한 기둥에 쌓여 있는 원반들을 다른 기둥으로 모두 옮기는 것입니다. 하노이 탑 규칙 한 번에 한 개의 원반만 이동할 수 있습니다. 원반은 세 개의 기둥 중 하나에만 있을 수 있습니다. 큰 원반이 작은 원반 위에 있어서는 안 됩니다. 모든 원반을 다른 기둥으로 모두 옮기면 끝입니다. 하노이 탑 문제 해결 방법 n-1개의 원반을 시작 기둥에서 보조 기둥으로 옮깁니다. 남은 한 개의 원반을 시작 기둥에서 목표 기둥으로 옮깁니다.(+1) 보조 기둥에 있는 n-1개의 원반을 목표 기둥으로 옮깁니다. 이 때의 ..

• format_list_bulleted 알고리즘/초급 알고리즘
• · 2024. 3. 28.
• textsms