재담이의 끄적끄적

문제 원본 : https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { public static..

문제 원본 : https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { public static void main(String[] args) thro..

문제 원본 : https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Stack; public class Main { public static void main(String[] arg..

문제 원본 : https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net import java.io.BufferedWriter; import java.io.OutputStreamWriter; import java.util.Arrays; public class Main { public static void main(String[] args) throws Exception { BufferedWriter bw = new BufferedWriter(new OutputS..

문제 원본 : https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; public class Main { public static void main(St..

문제 원본 : https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWrite..

문제 원본 : https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { public static void main(String[] args) throws ..

Young Generational GC 이번에는 Eden 영역에 대해 더 알아보자. 참고로 HotSpot VM에서는 보다 빠른 메모리 할당을 위해서 2가지 기술을 사용한다. 첫 번째는 bump-the-pointer라는 기술이고, 두 번째는 TLABs(Thread-Local Allocation Buffers)라는 기술이다. bump-the-pointer는 Eden 영역에 할당된 마지막 객체를 추적한다. 마지막 객체는 Eden 영역의 맨 위(top)에 있는데, 다음에 생성되는 객체가 있으면 해당 객체의 크기가 Eden 영역에 넣기 적당한지만 확인한다. 만약 해당 객체의 크기가 적당하다고 판단되면 Eden 영역에 넣게 되고 새로 생성된 객체가 맨 위에 있게 된다. 따라서 새로운 객체 생성 시 마지막에 추가된 ..

Generational GC GC는 다음의 2가지 가정에 따라 만들어졌다. 대부분의 객체는 금방 접근 불가능 상태(unreachable)가 된다. 오래된 객체에서 젊은 객체로의 참조는 아주 적게 존재한다. 이러한 가설을 Weak Generational Hypothesis라고 한다. 실제 통계로도 생성된 객체의 98%의 객체가 곧바로 쓰레기 객체가 된다고 한다. 이 가설의 장점을 최대한 살리기 위해서 HotSpot VM에서는 크게 2개로 물리적 공간(Young / Old)으로 나누었다. 이러한 경험적 사실들을 바탕으로 Generational GC가 디자인되었다. 우선 2번째 가설에 대해 살펴보면, Old 영역에는 512 Bytes의 덩어리(chunk)로 되어 있는 카드 테이블이 존재한다. 카드 테이블에는 ..

포인터 추적 방식 포인터 추적 방식이란 한 개 이상의 변수가 접근 가능한 메모리는 앞으로 사용할 수 있는 메모리로 간주하고 그 밖의 메모리를 해제하는 방식을 의미한다. 대부분의 GC는 포인터 추적 방식을 사용한다. 포인터 추적 방식의 종류 포인터 추적 방식에는 여러 가지 방법이 존재하는데 그 종류를 살펴보자. 표시하고 쓸기(Mark and Sweep) 표시하고 쓸기는 가장 단순한 방식이다. 먼저 각 메모리 할당 영역에 표시를 위해 1 비트의 메모리를 남겨둔다. 표시 단계에서 모든 변수가 가리키는 영역을 사용 중으로 표시하고 그 영역에서 가리키는 영역 또한 사용 중으로 표시한다. 이처럼 모든 메모리 영역을 표시하고 나면 표시되지 않은 영역은 접근 불가능한 메모리 영역이 된다. 접근 불가능한 메모리 영역들은..