재귀 반복 => 단위 반복 찾기 재귀 => 같은 처리 단위 찾기 하나의 큰 문제를 해결할 수 있는(해결하기 쉬운) 더 작은 문제로 쪼개고, 결과들을 결합 재귀 함수로 구현 재귀 함수 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수 일반적으로 재귀적 정의를 이용해서 재귀함수 구현 기본 부분(Basic part) & 간접 부분(Inductive part)로 구성 재귀적 프로그램 작성이 반복 구조에 비해 간결 & 이해가 쉬움 함수 호출은 프로그램 메모리 구조에서 STACK(스택) 사용 재귀 호출은 반복적인 스택의 사용을 의미, 메모리 및 속도에서 성능 저하 --> stack overflow Factorial (팩토리얼) 재귀 함수 팩토리얼: 그 수보다 작거나 같은 모든 양의 정수의 곱 publi..

배열이 주어졌을 때, 오른쪽, 왼쪽으로 배열을 이동하는 shift import java.util.Array public class ShiftTest{ public static void main(String[] args){ int[] arr = new int[] {1, 2, 3, 4, 5}; System.out.println(Arrays.toString(arr)); rightShift(arr); System.out.println(Arrays.toString(arr)); leftShift(arr); System.out.println(Arrays.toString(arr)); } //배열을 왼쪽으로 한 칸씩 이동하는 함수 private static void leftShift(int[] arr){ //맨 앞 수를..

Next Permutation: 한 순열에서 사전 순으로 다음 순열 생성 알고리즘 배열을 오름 차순으로 정렬한다 뒤쪽 부터 탐색하여 가장 큰 놈을 찾는다(꼭대기를 찾는다, i번째) -> 꼭대기 바로 앞이(i-1번쨰)이 교환 위치(a) 뒤쪽 부터 탐색하여 a와 교환할 a보다 큰 가장 빠른 곳(b)를 찾는다 a와 b를 교환한다 꼭대기 부터 맨 뒤까지 정렬한다 2~5번 과정을 반복 코드 //다음 큰 순열이 있으면 true, 없으면 false private static boolean np(int[] numbers) { //i, j, k 모두 맨 뒤에서 부터 시작 //비교하는 부분 모두 i-1부터, int N = numbers.length; //step1. 꼭대기를(i) 찾는다. 꼭대기를 통해 교환위치(i-1)찾..

신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 N개의 정점으로 이루어진 무향 그래프에서 N개의 정점과 N-1개의 간선으로 이루어진 트리 최소 신장 트리 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장트리 특징 간선의 가중치의 합이 최소여야 한다. n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다. 사이클이 포함되어서는 안된다. Prim 알고리즘 정점 중심 1. 임의의 한 정점을 선택 2. 선택한 정점과 인접한 정점 중에 최소 비용 간선이 존재하는 정점을 선택 3. n-1번 반복 Kruskal 알고리즘 간선 중심 1. 모든 간선을 가중치에 따라 오름차순 정렬 2. 가중치가 낮은 간선부터 선택하여 트리를 증가시킴 ..

생각할 수 있는 모든 경우의 수를 구하다. 상대적으로 빠른 시간에 문제 해결을 할 수 있다. Brute-force 또는 Generate - and - test 기법이다. 순열(Permutation) 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 서로 다른 n개 중 r개를 택하는 순열 : nPr = n*(n-1)*(n-2)*---*(n-r+1) 다수의 알고리즘 문제들은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련 N개의 요소들에 대해서 N!개의 순열들이 존재 알고리즘 n개 숫자에 대해서 시도, 앞에서 선택된 수는 배제, 해당 개수의 수 선택 import java.util.Scanner; public class Permutation { static int[] numbers, resul..

피보나치 수열이란? 수학에서, 피보나치 수(Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 단조 증가 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다. 반복(Iterative) 1. 코드 def fibo(x): if x O(n) 3. 특징 불필요한 연산을 계속 수행해야 한다. 재귀(Recursive) 1. 코드 def fibo(x): if x O(2^n) 함수가 한 번 호출되면 2번씩 호출되기 때문에 2^n 3. 특징 코드 구성이 간단하다. 시간 복잡도가 크다. 재귀의 특징에 따라 Stack Overflow가 발생할 수 있다. 불필요한 연산을 계속 수행해야 한다. 동적계획법(Dynamic ..