2022 02 07

2022-02-07

이분탐색

• O(N)의 탐색을 O(logN)으로 줄이는 방법
  • 특정 범위 내에서 만족하는 답이 있으리라 판단하면 써보자
    • 만족하는 답인지 판단하기 위해 "결정 알고리즘"을 사용하여 check
  • 범위를 lt/rt/mid로 나누어 mid 값이 알맞은 값인지 판단하는 방식

    private int solution(int[] array, int horse) {
        Arrays.sort(array);
        int lt = 0;
        int rt = (array[array.length - 1] - array[0])/ (horse - 1);
        int mid = (lt + rt) / 2;
    
        int answer = 0;
        while (lt <= rt) {
            int possibleHorse = possible(mid, array);
            if (possibleHorse >= horse) {
                answer = mid;
                lt = mid + 1;
            } else {
                rt = mid - 1;
            }
            mid = (lt + rt) / 2;
        }
        return answer;
    }
    

알고리즘 문제풀이 - 재귀

• 스택 프레임
  • 매개변수 정보, 지역변수 정보, 복귀할 주소를 스택 프레임에 저장함!
  • 복귀할 주소를 생각하면서 출력 순서등을 조정할 수 있음

• 메모이제이션
  • 재귀를 통해 얻은 결과를 static 배열에 저장해두자!
  • 피보나치 수열의 경우 같은 결과를 계산하기 위해 같은 과정의 재귀를 반복했어야 했음 -> 메모이제이션 도입으로 해결

    import java.util.Scanner;
    
    public class Main {
        public static int[] fibonacci;
    
        private int solution(int number) {
            if (fibonacci[number] != 0) {
                return fibonacci[number];
            }
            if (number == 1 || number == 2) {
                fibonacci[1] = 1;
                fibonacci[2] = 1;
                return 1;
            } else {
                fibonacci[number] = solution(number - 1) + solution(number - 2);
                return fibonacci[number];
            }
        }
    
        public static void main(String[] args) {
            Main main = new Main();
            Scanner in = new Scanner(System.in);
    
            int num = in.nextInt();
            fibonacci = new int[num + 1];
            main.solution(num);
            for (int i = 1; i <= num; i++) {
                System.out.print(fibonacci[i] + " ");
            }
        }
    }