문제 정보
- 백준 알고리즘
- 단계 : 수학 1
- 문제 번호 : 2775
- 링크 : https://www.acmicpc.net/problem/2775
문제
풀이
- 호수가 1 이면 값은 무조건 1
- 층수가 0 이면 값은 무조건 호수값
- 그외 층, 호수는 아래층 동일 호수 의 값 + 동일 층 이전 호수의 값
- 재귀 함수 =
f(x,y) = f(x-1, y) + f(x, y-1)
- 재귀 함수 =
보완
- 재귀 함수의 반복 깊이가 깊어질수록 효율이 떨어진다. 당연하게도..
- 재귀가 무한으로 깊게 들어가기 전에 값을 쪼갤 수(?) 있는 규칙이 있는지
꽤 오랫동안 들여봤지만 못찾겠다. ...
- 재귀가 무한으로 깊게 들어가기 전에 값을 쪼갤 수(?) 있는 규칙이 있는지
- 재귀로 한번 계산된 값은 두번 계산되지 않도록 메모리에 저장 (캐싱)
- 문제는 입력 범위가 비교적 작은 범위로 제한되어 있으니 이중 고정 배열을 쓸 수 있지만
범위가 일정치 않다고 제한을 풀면 범위에 동적으로 대응할 수 있는 Map 이 좋을 듯- Map 을 사용할 시 floor 와 number 로 구성된 데이터 클래스를 만들어
객체의 hashCode() 를 사용하려 했으나, 일정한 값이 보장되지 않았음 - 편법으로 hashCode 를 override 후 일정한 해시코드 보장됨
- Map 을 사용할 시 floor 와 number 로 구성된 데이터 클래스를 만들어
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 오류가 발생함.- https://blog.jooq.org/2015/03/04/avoid-recursion-in-concurrenthashmap-computeifabsent/
- 관련 글들을 대충 훑어봤으나 해결 방법은 아직 모르겠음. 추후 참고.
코드
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();
}
}
}
'알고리즘' 카테고리의 다른 글
백준온라인 - 수학1 - ACM 호텔 (0) | 2020.04.05 |
---|---|
백준 온라인 - 수학1 - 달팽이는 올라가고 싶다 (0) | 2020.04.05 |
백준 온라인 - 수학1 - 분수찾기 (0) | 2020.04.04 |