알고리즘 (22) 썸네일형 리스트형 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); }.. [LeetCode] Add Two Numbers 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051public class AddTwoNumbers { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode answer = new ListNode(); ListNode node = answer; int carry = 0; while (l1 != null || l2 != null){ int sum = carry; if(l1 != null){ sum += l1.val; l1 = l1.next; } if(l2 != null){ sum += l2.val; l2 = l2.next; } .. 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.. [백준 2445번] 별 찍기 - 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import java.util.Scanner; class MainClass{ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int num = scanner.nextInt(); for(int i = 0; i [백준 - 1316] 그룹 단어 체커 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 import java.util.ArrayList; import java.util.HashMap; import java.util.Iterator; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int test = scanner.nextInt.. 예제 : 수열의 빠른 합 1 2 3 4 5 6 7 8 9 10 11 12 13 public class FastSum { public static void main(String[] args) { System.out.println(fastSum(10)); } public static int fastSum(int n) { if(n == 1) { return 1; } if(n%2 == 1) return fastSum(n-1) + n; return 2*fastSum(n/2)+n/2*n/2; } } Colored by Color Scripter cs 1 + 2 + 3 + 4 + 5 + ... + n 을 반으로 나누어서 계산해 보자 1 + 2 + 3 + ... n/2 + (n/2+2) + (n/2+3) + (n/2+4) + (n/2+n/2).. 이전 1 2 3 다음 목록 더보기
