Algorithm (18) 썸네일형 리스트형 recursive(1) Recursion - 자기 자신을 호출하는 함수(메서드) - 통제를 통해 무한루프에 빠지지 않게 할 수 있다 무한통제 방지 구조 - 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야한다 -> base case - Recursion을 반복하다보면 결국 base case로 수렴해야한다 대표적인 예시 1) 팩토리얼 2) 피보나치수열 3) 최대공약수 M>=N인 두 양의 정수 M과 N에 대해서 M이 N의 배수이면 gcd(M,N) = N이고, 그렇지 않으면 gcd(M,N) = gcd(n,M%N)이다. 코드) Public static double gcd(int m, int n){ If(m 길 1-> 벽 2-> 가봤지만 목표지점까지 갈 수 없는 곳임이 확인된 곳 3-> 가봤지만 목표지점까지 갈 수 있는지 .. Heap Heap - 우선 순위 큐 및 대기열을 만드는데 사용되어진다 (우선순위 큐를 구현할 때 가장 효율적이다) - 완전 이진 트리의 일종이다(가질 수 있는 노드의 최댓값은 2^(k+1) - 1이다) - 반정렬 상태를 유지한다 - 삽입/삭제는 O(logN)으로 매우 빠르다 - 배열의 자료구조로 저장된다 - 첫 index인 0은 사용되지 않는다 - Heap 정렬은 선택정렬의 원리를 가진다 종류 최대heap - 부모노드가 자식노드보다 크다 최소heap - 부모노드가 자식노드보다 작음 삽입 Heap에 데이터가 추가 되는 경우는 크게 2가지로 나뉜다. 1. Comparator가 nul이 아닐 때 2. Comparator가 null일 때 기본적으로 맨 밑 자식 노드에 값이 하나 추가되는 경우를 생각해보자. 1. 삽입된 .. 단순 삽입 정렬 단순 삽입 정렬 선택한 요소를 더 앞쪽의 알맞은 위치에(오름차순이든, 내림차순이든) 삽입하는 작업을 반복하여 정렬한다 2번째 요소. index[1] 값부터 진행한다 요소들이 서로 뒤바뀌지 않아 안정적이다 교환 횟수는 n^2/2 이다 시간복잡도가 O(n^2)라서 효율성이 떨어진다 코드예시 for(int i=1; i0 && a[j-1] > tmp; j--) { //값을 교환함 a[j] = a[j-1]; } //j--에 따라서 한 칸 앞에 a[i]인 tmp 값을 삽입해줌 a[j] = tmp; } } 10 4 2 11 3 20 15 과정 1) tmp = a[1]인 4가 된다 2) 조건이 맞기에 a[1] = a[0]인 10이 된다 3) j를 1 감소시켜 j=0이 된다 4) a[0] 은 타겟값 4가 된다 결과 4 .. 정렬 - 단순 선택 정렬 단순 선택 정렬은 가장 작은 요소를 선택하고 그에 맞는 위치에 있는 값과 서로 교환하는 과정을 계속한다 ex) 최소값 탐색 : 1 1을 index[0]에 위치 시킨다 최소값 탐색(이미 탐색한 index[0]의 1은 제외) : 3 3을 index[1]에 위치 시킨다 코드예시 for(int i = 0; i 정렬(Sort)-버블정렬 버블정렬 붙어 있는 두 값을 검사하여 정렬한다 오름차순으로 정렬할 때는 왼쪽의 값이 오른쪽의 값보다 작아야하고, 이에 맞지 않다면 값을 서로 교환한다 내림차순으로 정렬할 때는 오른쪽의 값이 왼쪽의 값보다 작아야하고, 이에 맞지 않다면 값을 서로 교환한다 ex) 오름차순 정렬 6 4 3 7 1 9 8 1. 9와 8을 비교하고 왼쪽 값이 오른쪽 값보다 작아야하기에 8과 9를 교환한다 6 4 3 7 1 8 9 2. 8과 1을 비교하고 왼쪽 값이 오른쪽 값보다 작기 때문에 1과 8은 교환하지 않는다 6 4 3 7 1 8 9 3. 1과 7을 비교하고 왼쪽 값이 오른쪽 값보다 작아야하기에 7과 1를 교환한다 6 4 3 1 7 8 9 4. 1과 3을 비교하고 왼쪽 값이 오른쪽 값보다 작아야하기에 1과 3을 교환한다 .. Greedy 탐욕 알고리즘은선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법 정렬기법과 함께 이용된다 가장 좋아보이는 것을 선택해도 최적의 해를 구할 수 있는지 검토한다 최소공배수와 최대공약수 최대공약수를 푸는 방법에는 유클리드 호제법이 있다. 유클리드 호제법 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다 - 유클리드 호제법 코드 static int gcd(int x, int y){ if(y==0) return x; else{ return gcd(y, x%y); } } 이렇게 재귀적인 코드를 통해 최대공약수를 쉽게 구할 수 있다 최소공배수 구하기 최소공배수를 구하는 방법은 매우 쉽다. 두 수의 곱에 최대공약수를 나눠주면 되기 때문이다 최소공배수.. 스택으로 재귀함수를 비재귀적으로 구현하기 스택이란? - 자료를 임시적으로 저장하며 First In Last Out 구조를 가지고 있다 코드 static void recur(int n){ IntStack s = new IntStack(n); while(true){ if(n>0){ s.push(n); n=n-1; continue; } if(s.isEmpty() != true){ n=s.pop(); System.out.println(n); n = n -2; continue; } break; } } 과정 n=4 4를 푸쉬>3을 푸쉬>2를 푸쉬>1을 푸쉬> 1을 팝&출력>2를 팝&출력>3을 팝&출력>1을 푸쉬>1을 팝&출력> 4를 팝&출력 > 2를 푸쉬>1을 푸쉬> 1을 팝&출력 > 2를 팝&출력 이전 1 2 3 다음