[JAVA] 점화식과 재귀함수, 최대공약수 재귀함수로 구현하기, 정렬의 종류
점화식(Recurrence)
어떤 수열의 일반항을 그 이전의 항들을 이용해 정의한 식
ex. 피보나치 수열
1 ,1 ,2, 3, 5, 8, 13...
재귀함수
어떤 함수가 자신을 다시 호출하여 작업을 수행하는 방식
종료조건이 무조건 존재한다!
코드 구현:
public class Main {
static int recursion1(int n){
if (n == 1){ //종료조건
return 1;
}
return 3* recursion1(n-1); //자기자신을 불러온다
}
static int recursion2(int n){
if (n ==1){
return 1;
}
return n+ recursion2(n-1);
}
static int recursion3(int n){
if (n < 3) {
return 1;
}
return recursion3(n-2)+ recursion3(n-1);
}
public static void main(String[] args) {
//점화식 -> 반복문, 재귀함수
System.out.println("== 점화식/재귀함수 연습1 ==");
//1,3,9,27.... 의 n번째 수
int n = 4;
int result = 1;
for (int i = 0; i < n; i++) {
if (i == 0){
result =1;
}else {
result *= 3;
}
}
System.out.println(result);
System.out.println("== 점화식/재귀함수 연습2 ==");
//1,2,3,4,5,6,....의 n번째까지의 합
n = 5;
result = 0;
for (int i = 0; i < n+1; i++) {
result+=1;
}
System.out.println(result);
System.out.println("== 점화식/재귀함수 연습3 ==");
//1,1,2,3,5,8,13...의 n번째 수 피보나치 수열
n = 6;
result = 0;
int a1 = 1;
int a2 = 1;
if(n<2){
result =1;
}else {
for (int i = 2; i < n; i++) {
result = a1+a2;
a1 = a2;
a2 = result;
}
}
System.out.println(result);
}
}
많이 구현되는 최대공약수 재귀함수로 구현하기
//최대공약수를 재귀함수로 구현하시오
public class Practice2 {
static int gcd(int a, int b){
if (a % b ==0){
return b;
}
return gcd(b, a%b);
}
public static void main(String[] args){
//Test code
System.out.println(gcd(3,5));
System.out.println(gcd(2,6));
System.out.println(gcd(8,12));
}
}정렬
특정 값을 기준으로 데이터를 순서대로 배치하는 방법
*구현 난이도는 쉽지만, 속도는 느린 알고리즘:
-버블 정렬: 인접한 데이터를 비교하며 자리 바꾸는 방식
알고리즘 복잡도: O(n^2)
-삽입 정렬: 앞의 데이터를 정렬해가면서 삽입 위치를 찾아 정렬하는 방식
알고리즘 복잡도: O(n^2)
-선택 정렬: 최소 또는 최대값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식
알고리즘 복잡도: O(n^2)
*구현 난이도는 조금 더 어렵지만, 속도는 빠른 알고리즘
-합병 정렬: 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하며 합병하는 방식
알고리즘 복잡도: O(nlogn)
-힙 정렬: 힙 자료구조 형태의 정렬 방식, 기존 배열을 최대 힙으로 구조변경 후 정렬 진행
알고리즘 복잡도: O(nlogn)
-퀵 정렬: 임의의 기준값(pivot)을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식
알고리즘 복잡도: O(n^2)
-트리 정렬: 이진 탐색 트리를 만들어 정렬하는 방식
알고리즘 복잡도: O(nlogn)
*기타 정렬
-기수 정렬: 낮은 자리 수부터 정렬하는 방식
각 원소 간의 비교 연산을 하지 않아 빠른 대신, 기수 테이블을 위한 메모리 필요
알고리즘 복잡도: O(dn) -> d: 최대 자릿수
-계수 정렬: 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식
카운팅을 위한 메모리 필요
알고리즘 복잡도:O(n+k) -> k: 정렬 대상 데이터 중 최대값
-셸 정렬: 삽입 정렬의 약점을 보완한 정렬 방식
(삽입 정렬의 약점:
오름차순, 내림차순으로 구성된 데이터에 대해 앞의 데이터와 하나씩 비교해 모두 교환 필요)
이전의 모든 데이터와 비교하지 않고 일정 간격(length/2 에서 1/2씩 하며)을 두어 비교
알고리즘 복잡도: O(n^2)
아직까지 재귀함수 구현이 쉽지 않고,
오히려 헷갈린다.(편의성을 모르겠다!)
먼저 코테에서 아주 쉬운 문제로 출제될 수 있다는 최대공약수의 구현은 암기해두어야겠다.
재귀함수는 매우 빈번히 사용될테니 조급함을 가지지말고,
사용될 때마다 다시 코드를 작성해 이해해보며 익숙해져야겠다.
정렬의 종류가 너무 많아 헷갈린다.
거기에 구현도 너무 어렵다.
다시 구현을 차근히 해보며 개념에 대한 숙지를 우선시 해야겠다.