[백준] 점프 (DP) 참고 정리

[백준] 점프 문제 풀이 https://orion-log.tistory.com/96

---

참고할 주요 개념 설명

✅ Java에서 자료형 범위 – long을 쓰라는 명확한 신호

문제에서 “경로 수는 2⁶³ - 1보다 작거나 같다”는 조건은 사실상 다음 의미와 같다:

👉 int로는 절대 안 되고 long을 써야 한다는 공식 힌트

자료형	바이트 수	표현 가능 범위
byte	1 byte	-2⁷ ~ 2⁷ - 1 (-128 ~ 127)
short	2 bytes	-2¹⁵ ~ 2¹⁵ - 1 (-32,768 ~ 32,767)
int	4 bytes	-2³¹ ~ 2³¹ - 1 (약 21억)
long	8 bytes	-2⁶³ ~ 2⁶³ - 1 (약 ±9.2×10¹⁸)

예시로 dp[i][j] += dp[x][y] 연산이 수십억 번 중첩될 수 있으므로, int는 누적 과정에서 오버플로우 위험이 있음
→ 따라서 long으로 경로 수를 세는 것이 사실상 필수 조건

---

✅ BFS로 풀면 메모리 초과가 나는 이유

1. BFS 방식의 특징 요약

항목	현재 코드가 사용하는 방법	메모리 사용 추정	위험 요인
게임판 int[N][N]	고정 크기 100×100	약 40 KB	안전
ArrayDeque<Object> 내부 배열	초기 용량 16 → 자동 확장	약 O(큐 크기 × 8 bytes)	큐가 커질수록 폭발적으로 증가
좌표 객체 new int[]{r,c}	객체 헤더(12~16 B) + int 2개(8 B) ≈ 24 B	경로 수만큼 객체 생성	수십만~수백만 개 생성 시 초과 위험

---

2. 왜 큐가 폭발하는가?

1) 중복 방문을 막기 어려움

• 경로 수를 세는 문제이므로, 같은 좌표 (i,j)라도 경로가 다르면 독립적으로 처리해야 함
• BFS에서 방문한 적 있는 좌표라도 또 큐에 넣음 → 중복 삽입 많음

2) 경로 수 자체가 천문학적이다

• 예: 모든 칸의 값이 1이면, (0,0) → (N-1,N-1)까지 총 2×(N-1)번 이동 필요
• 가능한 경로 수:
  $\binom{198}{99} \approx 9 \times 10^{58} \quad (N = 100 \text{일 때})$
• 이 중 **극히 일부만 큐에 들어 있어도 메모리 한계(128MB)**를 금방 초과

3) 좌표 객체의 메모리 사용량이 상당함

• 큐에 들어가는 new int[]{r, c}는 객체당 약 24~28 B
• 100만 개만 삽입해도 약 25 MB
• 중복 경로와 맞물려 큐 용량이 무제한 확장됨

---

✅ Java 객체의 구조와 int[]가 메모리를 많이 먹는 이유

📦 Java 객체의 메모리 레이아웃

JVM에서 객체는 다음 3단계로 메모리에 저장됨:

[ 객체 헤더 | 인스턴스 변수들 | 정렬 패딩 ]

---

객체 헤더의 구성 (64비트 JVM 기준)

항목	크기	설명
Mark Word	8 bytes	GC 정보, 해시값, 락(lock) 등 메타데이터
Class Pointer	8 bytes	객체가 어떤 클래스인지 가리키는 포인터
배열 길이 (배열일 경우)	4 bytes	배열인 경우만 존재하는 크기 정보
정렬 패딩	0~4 bytes	8 bytes 단위 정렬용 여유 공간

---

예시: new int[]{x, y} 객체 하나의 실제 메모리 사용

int[] pos = new int[]{5, 7};

항목	크기
객체 헤더	16 bytes
배열 길이 정보	4 bytes
데이터(int 2개)	8 bytes
정렬 패딩 (필요 시)	0~4 bytes
합계	약 24~28 bytes

즉, BFS 큐에 좌표 객체를 100만 개만 넣어도 약 25MB 소모
큐 확장과 중복 삽입이 반복되면 금방 128MB 초과

---

🔗 참고 자료

자료 제목	설명
Oracle JVM 구조 설명서	JVM 구조 설명
Java Object Layout (JOL)	JVM의 객체 레이아웃 체계를 분석하는 도구