문제 정보
문제
풀이
- 호수가 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();
}
}
}
