본문 바로가기

RecursiveAlgorithm

Recursive Algorithm - Binomial theorem Binomial theorem(이항계수) - 이항계수(binomial theorem) 알고리즘 : 조합론에서 사용되며, n개의 서로 다른 원소에서 r개의 원소를 선택하는 경우의 수를 계산 - 이항계수 : 조합론에서 등장하는 개념으로 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수 / 2를 상징하는 ‘이항’이라는 말이 붙은 이유는 하나의 아이템에 대해서는 ‘뽑거나, 안 뽑거나’ 두 가지의 선택만 존재 (ex)4개의 집합 중에서 2개를 순서없이 고르는 조합의 수는 ‘4! / 2! / 2!’, 즉 6 nCk = n! / k!(n-1)! = (4*3*2*1) / (2*1)(2*1) = 3*2*1 = 6 1. r이 0이거나 n과 같으면 함수는 1을 반환 2. 그렇지 않으면 k-1과 n-1인자로하.. 더보기
Recursive Algorithm - GCD(최대공약수) GCD - 유클리드 호제법/알고리즘(Euclidean Algorithm) : 두 수의 “최대공약수(GCD)”를 찾기 위한 알고리즘 - 큰 수를 작은 수로 나누어 떨어지게 하여 수를 반복적으로 취하여 나머지 0이 될 때까지 작동하는 방법 / 작은 수가 최대공약수 Java예시 - m = 작은 수, n = 큰 수를 입력으로 받고, n=0이 될 때까지 recursive 실행 - 큰 수와 작은수를 큰 수로 나눈 나머지를 구하는 연산을 계속 하면서, m의 값을 갱신 - main함수에서 실행한 결과 C예시 - 추가 예정 더보기
Recursive Algorithm - Fibonacci Fibonacci - 피보나치 수열 : 이전 두 항의 합이 다음 항이 되는 수열 - 첫째 항과 둘째 항이 1이고 이후 모든 항은 모든 항은 바로 앞 두항의 합으로 이루어지는 수열을 의미 - 피보나치 수열의 예시 - [1, 1, 2, 3, 5, 8, 13, 21, 34,...] Java예시 - parameter로 들어온 값이 0 이거나 1이면 0, 1 return - 첫 번째와 두 번째 값은 1, 세 번째부터는 현재 위치 기준 앞에 있는 2개의 합으로 구성(세 번째 값 = 두 번째 값 + 첫 번째 값, 네 번째 값 = 세 번쩨 값 + 두 번째 값, ...) - main함수에서 실행한 결과 C예시 - 추가예정 더보기
Recursive Algorithm - Recursive Function Recursive Function - Recursive(재귀) : 어떤 문제를 해결하기 위해 알고리즘을 설계할 때 동일한 문제의 조금 더 작은 경우를 해결함으로써 그 문제를 해결하는 것 - 팩토리얼, 거듭제곱, 문자열 반대로 출력 등의 문제에 적용 가능 Java 예시1 - Factorial - Factorial : 자연수 n에 대해서 1부터 n까지의 모든 자연수를 곱한 값 - factorial() 함수에 파라미터로 값을 넘길 경우 재귀함수로 반복하여 결괏값을 반환해 주는 함수 - factorial(5) = 5 * factorial(4) / factorial(4) = 4 * factorial(3) / factorial(3) = 3 * factorial(2) / factorial(2) = 2 * factor.. 더보기

티스토리툴바