알고리즘/Algorithm (7) 썸네일형 리스트형 Dynamic Programing 피보나치 import java.util.ArrayList; import java.util.Arrays; public class Fibonacci { public static void main(String[] args) { Fibonacci fb = new Fibonacci(); int fib_naive = fb.fib_naive(10); int fib_recur_dp = fb.fib_recur_dp(10); int fib_dp = fb.fib_dp(10); System.out.println("fib_naive = " + fib_naive); System.out.println("fib_recur_dp = " + fib_recur_dp); System.out.println("fib_dp = " + fib_dp); }.. Recursion의 응용 - 미로찾기 현재 위치에서 출구까지 가는 경로가 있으려면 1. 현재 위치가 출구이거나 2. 이웃한 셀들 중 하나에서 현재의 위치를 지나지 않고 출구까지 가는 경로가 있거나 미로찾기(Decision problem) 1 2 3 4 5 6 7 8 9 10 public boolean findPath(x,y) { if(x, y) is the exit return true; else for each neighbouring cell(x', y') of (x, y) do if(x', y') is on the path way if findPath(x', y'); return true; return false; } Colored by Color Scripter cs 위 코드의 경우 (x, y)와 (x', y')가 서로 왔다갔다 하면서.. 2진검색 알고리즘 데이터가 크기순으로 배열에 저장되어 있다고 가정. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public static int binarySearch(String[] items, String target, int begin, int end) { if(begin > end) return -1; else { int middle = (begin+end)/2; int compResult = target.compareTo(items[middle]); //target이 크면 1 작으면 -1 같으면 0 if(compResult == 0) return middle; else if (compResult Recursion(순환)-3 - 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다. - 모든 case는 결국 base case로 수렴해야 한다. 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라. 0 ~ n-1 -> 암시적 begin ~ end -> 명시적 순차탐색 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public int search(int[] data, int n, int target) { for(int i = 0; i end) return -1; else if(target == data[begin]) return begin; else return search(data, begin+1, end, target); } Color.. Recursion(순환)-2 문자열의 길이 계산 알고리즘 1 2 3 4 5 6 7 public static int lenghth(String str){ if(str.equals("")) return 0; else return 1+lenghth(str.substring(1)); } Colored by Color Scripter cs 가장 앞에 존재하는 문자 하나를 제거하고 1을 더하는 작업을 반복하여 총 문자열의 길이를 구한다. 문자열의 프린트 하는 알고리즘 1 2 3 4 5 6 7 8 public static void printChars(String str){ if(str.equals("")) return 0; else System.out.print(str.charAt(0)); printChars(str.substring(1)); .. 선형 시간 알고리즘 알고리즘의 시간복잡도란 알고리즘의 속도는 코드에 반복문이 수행되는 횟수로 측정한다. 이때 반복문의 수행 횟수는 입력의 크기에 대한 함수로 표현한다. 선형 시간 알고리즘이란 코드의 수행시간이 입력의 크기에 정비례하는 코드로 대게 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘인 경우가 많다.(입력 전체를 한번은 확인해야 한다.) 이동평균을 이용하여 선형시간 알고리즘을 이해해 보았다. 이동평균이란 하루에 마시는 믹스커피 개수를 예로 들어 보면 1일 2일 3일 4일 5일 6일 7일 8일 3개 4개 5개 3개 4개 3개 3개 4개 M-이동평균에서 M을 3이라고 한다면 3일에 : (1일+2일+3일)/3 4일에 : (2일+3일+4일)/3 5일에 : (3일+4일+5일)/3 . . . 을 모두 계산하여 나타내는 .. Recursion(순환)-1 Recursion vs Iteration 모든 순환함수는 반복문으로 변경 가능하다. 모든 반복문은 recursion으로 표현 가능하다. 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다 함수 호출에 따른 오버헤드가 존재한다.(매개변수 전달, 액티베이션 프레임 생성 등) 자기 자신을 호출하는 함수(메서드)를 Recursion이라고 한다. 1 2 3 4 5 6 7 8 9 10 11 public class Code01{ public static void main(String [] args){ func(); } public static void func(){ System.out.println("Hello...."); func(); } } Colored by Color Scripter c.. 이전 1 다음
