본문 바로가기

알고리즘

백준 온라인 - 수학1 - 부녀회장이 될테야

문제 정보

문제

풀이

  • 호수가 1 이면 값은 무조건 1
  • 층수가 0 이면 값은 무조건 호수값
  • 그외 층, 호수는 아래층 동일 호수 의 값 + 동일 층 이전 호수의 값
    • 재귀 함수 = f(x,y) = f(x-1, y) + f(x, y-1)

보완

  • 재귀 함수의 반복 깊이가 깊어질수록 효율이 떨어진다. 당연하게도..
    • 재귀가 무한으로 깊게 들어가기 전에 값을 쪼갤 수(?) 있는 규칙이 있는지
      꽤 오랫동안 들여봤지만 못찾겠다. ...
  • 재귀로 한번 계산된 값은 두번 계산되지 않도록 메모리에 저장 (캐싱)
  • 문제는 입력 범위가 비교적 작은 범위로 제한되어 있으니 이중 고정 배열을 쓸 수 있지만
    범위가 일정치 않다고 제한을 풀면 범위에 동적으로 대응할 수 있는 Map 이 좋을 듯
    • Map 을 사용할 시 floor 와 number 로 구성된 데이터 클래스를 만들어
      객체의 hashCode() 를 사용하려 했으나, 일정한 값이 보장되지 않았음
    • 편법으로 hashCode 를 override 후 일정한 해시코드 보장됨
1
18
18
8597496600
## i : 0, Recursive Execute Time : 13160 -- 재귀호출 매번 반복
8597496600
## i : 0, RecursiveWithCacheArray Execute Time : 0 -- Array Cache
8597496600
## i : 0, RecursiveWithCacheMap1 Execute Time : 14 - Map Cache

주의사항

  • Map 의 putIfAbsent 는 Map 에 Key 가 있건 없건 없을 경우 넣을 값을 미리 계산한 뒤 key 가 없으면 넣는다.
    • cache 의 이미가 없음 (cache 확인 전 무조건 재귀 계산을 해버리니까)
    • 오히려 더 성능이 떨어지게 됨
    • Optional 의 orElse 도 마찬가지..
    • 현실 코드에서 단순 로직에 이와 같은 동작을 하는건 성능상 큰 문제가 없겠지만 이건 재귀 동작이니 문제가 됨
  • computeIfAbsent 는 HashMap 을 사용할 경우 ConcurrentModificationException 가 일어나고
    ConcurrentHashMap 을 사용할 경우 recursive 오류가 발생함.

코드

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    private static Map<Integer, Long> cache = new HashMap<>();

    private static long[][] arr = new long[25][25];

    public static long recursiveWithCacheArray(int floor, int number) {
        if (number == 1)
            return 1;

        if (floor == 0)
            return number;

        if (arr[floor][number] == 0) {
            arr[floor][number] = recursiveWithCacheArray(floor, number - 1) + recursiveWithCacheArray(floor - 1, number);
        }

        return arr[floor][number];
    }

    public static long recursiveWithCacheMap(int floor, int number) {
        if (number == 1)
            return 1;

        if (floor == 0)
            return number;

        Couple couple = new Couple(floor, number);
        if (cache.containsKey(couple.hashCode())) {
            return cache.get(couple.hashCode());
        } else {
            long value = recursiveWithCacheMap(floor, number - 1) + recursiveWithCacheMap(floor - 1, number);
            cache.put(couple.hashCode(), value);
            return value;
        }
    }

    public static long recursive(int floor, int number) {
        if (number == 1)
            return 1;

        if (floor == 0)
            return number;

        return recursive(floor, number - 1) + recursive(floor - 1, number);
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int count = Integer.parseInt(scanner.nextLine());

        for (int i = 0; i < count; i++) {

            int floor = Integer.parseInt(scanner.nextLine());
            int number = Integer.parseInt(scanner.nextLine());

            long start = System.currentTimeMillis();
            System.out.println(recursive(floor, number));
            System.out.println("## i : " + i + ", Recursive Execute Time : " + (System.currentTimeMillis() - start));

            long start2 = System.currentTimeMillis();
            System.out.println(recursiveWithCacheArray(floor, number));
            System.out.println("## i : " + i + ", RecursiveWithCacheArray Execute Time : " + (System.currentTimeMillis() - start2));

            long start3 = System.currentTimeMillis();
            System.out.println(recursiveWithCacheMap(floor, number));
            System.out.println("## i : " + i + ", RecursiveWithCacheMap1 Execute Time : " + (System.currentTimeMillis() - start3));
        }

        System.out.println(cache.size());
    }

    public static class Couple {
        private int floor;
        private int number;

        public Couple(int floor, int number) {
            this.floor = floor;
            this.number = number;
        }

        public String toString() {
            return "# Floor : " + floor + ", # Number : " + number;
        }

        public int hashCode() {
            return ("F" + floor + "N" + number).hashCode();
        }

    }

}