[알고리즘] 팩토리얼, 재귀, 피보나치 수열 bubble, selection(단순선택) 정렬

[재귀 (recursive)]

반복문을 간결하게 구하기 위해 사용 

모든 반복문 구조를 재귀함수로 만들수는 있으나 효율성에서 차이가 난다. 

=> 항상 재귀함수가 효율적인 것은 아니다.

if(n>0) { 
	System.out.println("자연수"); 
	n= n+1;
	is자연수(n)
}

main(){
	is자연수(1);
} //무한루트를 돌게됨 


// ==============================

if(n>0) { 
	System.out.println("자연수"); 
	n= n-1;
 	is자연수(n)
 	is(n==0) return;  //꼬리조건 : 무한루프를 끝낼 수 있는 종료 조건 
}

main(){
	is자연수(100);
} //100~1까지

 

---

 

 

 

[팩토리얼]

0! = 1

1! = 1

2! = 2

 

5! = 5*4*3*2*1

  = 5*4!

4! = 4*3!

3! = 3*2!

2! = 2*1;

1!=1*0;

if(0과 같으면) return1 

 

static int fact1(int su) {
int result = 1;
  for(int i =1 ; i<=5; i++){
   result = result*i;   //만약 i 가 4이면 누적된 1*2*3 에 4도 곱해주는 것으로 1*2*3*4 = 4! 이 된다. 
  } 
  System.out.println(result);
  return result; 
}

static int fact2(int su) {
  if(su == 0 || su ==1) return 1;
  return su*f2(su-1);  //만약 su 값이 4이면 4*(3) 
  System.out.println(result);	
}

 

 

Top-down 방식 [재귀호출]	Bottom-up 방식[반복문]
5! = 5*4! 4! = 4*3! 팩토리얼과 같이 이전 계산 메소드를 호출 결과를 적용해야 하므로 계산을 한번만 하는 구조가 적합함 -> 재귀함수 호출방법으로 구현하면 좋다.  ; 썼던 계산을 중복적으로 하지 않으므로	같은 항 계산하는 메서드가 ‘여러 번＇호출됨  (ex) 피보나치를 재귀함수로 돌린거) 피보나치 수열은 반복문 구조가 더 적합하다. 작은값을 계산하고 –~그 값을 저장해놨다가 다시 쓰는 경우 이므로

 

 

 

---

 

 

 

 

[fibonacci 수열 ] - 추후 공부하면서 업데이트하기 

 

int  first = 1; second =1; 

int third = first+second;

int fourth = second + third 

int k = third + fourth 

 

package algorithm;

public class FibonacciTest {
	public static void main(String[] args) {
		System.out.println(10 + "항의 수열값은 = " + fibo(10)  );
	}
    
	static int fibo(int su) {  // 피보나치를 재귀함수로 돌리면 불필요한 반복이 많음 
		System.out.println("===" + su + " 일 때 fibo 시작");
		if( su == 1 ||su ==2) return 1;
		System.out.println("===" + su + " 일 때 fibo 종료");
		return fibo(su-2) + fibo(su-1);
	}

 

참고사이트 :

https://bit.ly/32uxEbp

피보나치 수열 알고리즘을 해결하는 5가지 방법

 

 

 

---

 

 

 

 

[유클리드 호제법] 

: 두 정수의 최대공약수(greatest common divisor)를 재귀적으로 구하는 방법

 

[예시] 

12와 18의 최대 공약수 

(1) 약수 구하기 

12/a = > 0 

  a = 12의 약수 

 * 12를 1~12사이의 숫자로 나뉘어 0이 나오면 그 값이 12의 약수라고 함

 

12의 약수 > 1, 2, 3, 4, 6, 12

18의 약수 -> 1, 2, 3, 6, 9, 18

 

12와 18의 공통 약수

공약수들 ->1, 2, 3, 6     // 최대 공약수 => 6 

---

(2) 두 숫자의 뺄셈 값이 '0' 이 나올 때까지 반복하기 

18-12 = 6

=> 두 수 중 작은 숫자인 12와 6을 계산

12-6 = 0  // 0이 나오면 계산 중단  =  "큰수에서 작은수 빼고 나온 그 값으로 0이 나올때까지 계속 빼준다"

작은값이 최대 공약수가 된다. 

 

****참고*****

2+2+2 => 2*3 

덧셈을 계속하면 곱셈이 되듯이 

뺄셈을 계속하면 나눗셈이 됨 

18%12 == 0 

 

---

 

검색은 1개 값을 찾아오는 것

정렬은 순서대로 나열하는 것 

정렬을 하기 위해서는 '배열'이 우선적으로 필요함

 

 

---

[정렬]

데이터를 일정한 순서로 줄지어 늘어서도록 바꾸는 작업

 

 

 

[Bubble 정렬]

: 이웃한 두 요소의 대소 관계를 비교하면서 교환을 반복한다. 

package algorithm;

import java.util.Arrays;

public class BubbleSort {

	public static void main(String[] args) {
		int data [] = {4, 5, 2, 3, 1}; 
		bubble(data, data.length);
		
		System.out.println(Arrays.toString(data));
	}
	static void bubble(int [] a, int n) {
		int min = 100;
		for (int i = 0; i< a.length-1 ; i++) {           
			for(int  j = 0; j<a.length - i -1 ; j++) {   
				if(a[j] > a[j+1]) {                      
					int temp = a[j];   
					a[j] = a[j+1];
					a[j+1] = temp;                       
				}
			}
		}
	}	
}

 

 

[단순선택(Selection) 정렬]

:가장 큰/작은 요소부터 선택해 알맞은 위치로 옮겨서 순서에 따라 정렬한다.

package algorithm;

import java.util.Arrays;

public class SelectionSort {
	public static void main(String[] args) {
		int data [] = {4, 2, 3, 5, 1}; // 오름차순 {1, 2, 3, 4, 5}
		
		selection(data, data.length);
		//data같은 객체가 매개변수로 전달되면 bubble 메소드 내부에서 data 배열의 내부 값을 변경한다.  / 리턴을 받지 않더라도 ..
		
		System.out.println(Arrays.toString(data));
	}// main

	static void selection(int [] a, int n) {
		for (int i = 0; i < a.length-1 ; i++) {        
        // 0번하고, 다음에 1번 인덱스 하고 .....끝번호값이 정해졌으므로 하나씩 덜 비교함
        // 마지막값 옆의 값이 없으므로 범위를 끝까지 잡으면 오류가 날 수 있다. 그래서 -1 해줌
			int min = i ;  //위치임. 데이터값 x 
			for(int  j = i+1 /*i랑 다른 값을 비교해야 되니깐*/; j < a.length ; j++) {   // 오른쪽 데이터 각각을 비교  (0,1 비교 - > 1,2 비교 ->...)  			
				if(a[j] < a[min]) {       //2개의 데이터 정렬 // ****이 부분의 부등호  변경으로 오름차순, 내림차순 으로 변경 가능 
					min = j; 
				}//ic end
					int temp = a[i];
					a[i] = a[min];
					a[min] = temp;       //데이터 2개 맞교환 		
			}//inner for	
		}//outer for 
	}
}