출저: pop it의 심천보님
잘 정리가 되어있는 글을 읽고, 공유하게 되었습니다.
이번 발표에 대한 가장 충격이었던 부분은 'var 지원'이였습니다. 뭔가 어색하네요 ,
한번 다들 읽어보셔요 !
'개발이야기 > Java' 카테고리의 다른 글
Linked List (단순 연결 리스트) 소스 (0) | 2017.11.10 |
---|---|
GC(가비지 콜렉션)에 대한 공부 (0) | 2017.11.03 |
출저: pop it의 심천보님
잘 정리가 되어있는 글을 읽고, 공유하게 되었습니다.
이번 발표에 대한 가장 충격이었던 부분은 'var 지원'이였습니다. 뭔가 어색하네요 ,
한번 다들 읽어보셔요 !
Linked List (단순 연결 리스트) 소스 (0) | 2017.11.10 |
---|---|
GC(가비지 콜렉션)에 대한 공부 (0) | 2017.11.03 |
취업준비를 하면서 내가 제대로 보지 못했던 자바의 '진짜 모습'을 보고자 노력하고 있다. 그래서 첫번째로, GC에대해서 살펴 볼 것이다.
자바를 공부하면서 흥미로웠던 것은 GC였다. 하지만, 학교내의 프로젝트에서는 GC를 보기 힘들다. 이번기회를 통해 GC를 튜닝하는 방법까지 공부하면서 구현할 예정이다.
가비지 컬렉션(GC)
말그대로 '쓰레기 수집가'이다. 하지만 그냥 수집가가 아니다, GC는 프로그램의 성능과도 연결될 수 있다. 그만큼 GC는 자바의 필수적인 요소이다.
Stop-the-world
이 용어의 뜻은 나는 이렇게 이해했다. 모두 멈추고 어둠의 지배자인 GC의 활동(?).. 이해하기 위해서 이렇게 생각했었다. GC를 진행하는 쓰레드를 제외하고 모든 쓰레드가 멈춘후, GC가 작업을 완료하면 중단한 작업들을 다시 시작한다, 라는 용어이다. 생각해보면 멈춘시간이 짧을 수록 좋은 프로그램이 아닐까 생각든다. 그렇기때문에 GC튜닝과정에서는 이 시간을 줄이는 것이다.
자바는 명시적으로 프로그램을 지정하여 해제 하지 않는다
그렇다. 그러지 않는다, 명시적으로 해제하지 않고 가비지 컬렉터가 필요없는 객체들을 찾아 치우는 작업을 한다. 하고 싶다면 null로 지정하거나, system.gc()를 호출하는데 후자는 절대로 하면 안된다.(성능에 무리)
weak generational hypothesis
가비지 컬렉터는 이 가설을 바탕으로 만들어 졌는데 ,
이 가설을 전제조건으로 가비지 콜렉터가 만들어졌다.
2개의 공간 Young and Old
위 가설의 장점을 살리기 위해 2개의 물리적 공간으로 나뉘는데 ,
Young과 Old이다.
Young 영역
Order 영역
추가적으로 perm영역이 있다. java 8에서는 사라졌다고 들었다, 아니 대체되었다는 표현이 정확하겠다. 이 영역에서는 객체or억류된 문자열이 저장된다. Old영역에서 살아남은 객체가 영원히 남아있는 것은 아니다. GC가 발생할 수 있고 Major GC라한다.
Old영역에 있는 객체가 Young 영역의 객체를 참조하는 경우의 처리
카드 테이블을 이용한다. 카드테이블의 크기는 512Byte이다. Old영역에 있는 객체가 Young영역의 객체를 참조할때마다 카드테이블에 표시를 해준다. 따라서 Young의 GC가 실행되면 Old영역이 아닌 카드테이블을 이용하여 처리한다. write barrier를 사용하며 관리하고 minor gc빠르게 해준다. 약간의 오버헤드의 위험이 있지만, 전반적인 GC시간은 줄어든다.
Young generation
제일 먼재 객체가 생성되어 저장되는 곳이다 , 3개의 영역으로 나뉘는데
Eden 과 두개의 Survivor이다.
두 개의 Survivor중 반드시 하나는 비어있어야한다. 둘다 아무것도 없거나, 둘다 있으면 시스템은 정상이 아니다.
빠른 메모리 할당을 위한 기술이 있다.
bump-the-pointer
Eden의 가장 높은(top)부분에는 마지막 객체가 존재한다. bump-the-pointer는 새로운 객체가 생성되면
이 객체가 Eden에 들어가도 되는지 검사를 한다. 그리고 검사를 통과한 객체는 Top위치로 가게 된다.
이러한 이유로 객체를 생성할때 마지막에 추가된 객체만 점검하면된다. 때문에 메모리 할당이 매우 빠르게 된다.
하지만..!
멀티 쓰레드 상황에서는 Thread-safe를 위해 여러 스레드에서 Eden영역을 사용할때에는 롹이 발생한다.
그렇게 되면 성능은 떨어질 가능성이 있다. (..lock contention)
Thread-Local-Allocation-Buffers(TLABs)
각 스레드마다 Eden영역의 작은 덩어리를 나눠준다. 그렇기 때문에 각 스레드는 자신의 TLABs에만 접근하면 된다.
이렇게 롹이 발생할 가능성을 없앨 수 있다.
Old 영역의 GC
Old Generation에 객체가 가득차면 실행하게된다.
Old영역에서 사용하는 알고리즘이다.
Mark : Old영역에 살아있는 객체를 식별한다.
Sweep : 힙의 앞부분부터 확인하여 살아있는것만 남긴다.
Compaction : 앞부분부터 채워서 객체가 존재하는 구역과 존재하지 않는 구역을 나눔
#Parallel Old GC
Parallel GC와 비교하여 Old영역의 GC만 다름
mark-summary-Compaction 단계를 거침
별도로 살아있는 객체를 식별한다는 점에서 더 복잡해짐
-XX:+UseParallelOldGc 로 활성화
Linked List (단순 연결 리스트) 소스 (0) | 2017.11.10 |
---|---|
Java9 발표에 대한 요약 (0) | 2017.11.06 |
풀이방법: 다익스트라
특정한 장소에 최단시간으로 모두 갔다오고, 그 중 가장 오랜시간 걸린 사람을 찾는 문제이다.
풀이방식
문제를 읽고 두 가지 풀이가 생각났다.
1.플로이드
2.다익스트라
처음에는 플로이드로 하면 금방할 것 같아 했는데 , 뭔가 오류가난다. 시간이 초과되고 그러는것 같다.
그래서 플로이드의 조건을 바꾸느냐? 아니면 다익스트라로 다시푸느냐...
다시하는게 빠를것 같아 다익스트라로 풀었다.
그냥 다익스타로 하기전에 고민을 좀 더 해봤다.
다시 생각해보면 우리는 X의 지점만 왓다리 갓다리 하면된다.
문제에서 보면 1 -> 2 가 4인데 이것을 뒤집으면 2 -> 1이된다. 보기에는 다르겠지만 의미는 같다.
따라서 두 가지의 방식을 사용하면된다.
일반적인 거리배열을 이용한것과 위처럼 뒤집은 배열을 사용한것 이 결과 두개를 더하면된다.
또한 우리는 기준이 되는 점을 알고 있기 때문에 기준점을 활용한다.
dist[i] = map{x}{i} + d[x]를 점화식으로 세운다.
나머지는 다른 다익스트라와 같다. (우선순위 큐쓰고,, 넣고 와일문 돌리고등.)
함수의 매개변수를 (int x, int{}{}map, int{} dist) 이렇게 받아주고 계산하면된다.(쓴 이유는 아래에 있다)
그리고 우리는 함수를 2번 호출한다. 왜냐하면 우리는 2개씩 배열을 만들것이기 떄문!
안뒤집은 배열, 뒤집은 배열, 안뒤집은 거리, 뒤집은 거리 이렇게 4개를 활용한ㄷ.
뒤집은 것을 넣게되면 아까 말한것처럼 1->2 를 2->1로 계산할 수 있다.
출력할때는
제일 큰 dist[i] + redist[i] 하면된다. 모두 x까지 왕복한 거리들이기 떄문이다.
코드 전체 보기
: 풀다가 잣다.. 어려웡.
백준 2665 미로만들기 (0) | 2017.10.30 |
---|
풀이방법: 동적계획법
엄청 시간이 걸렸던 문제다.
처음에 생각했던 것은 d[2-1] = d[1]+1.. 이런식으로 했었다.
그런데 여기서 4=2의 제곱이 되니 카운트가 바껴야 하는데 그 포인트를 못구했다.
그래서 중간에 월드시리즈 7차전을 잠깐보고 다시 문제를 풀었다.
오늘따라 다저스 타자들이 힘이 없어 보였다..나처럼 ㅜ
풀이방식
한번 생각해보자 ,
처음에 생각했던 방식 d[N - (N-1)] = d[N-1]+1 에 대해서 한번더 생각해보았다.
이렇게 하다보면 d[4]일때가 1차적으로 문제가 생기는데 ,
d[4-4] = d[0]+1을 만들어 줘야하기 때문이다.
자세히 식을 들여다보니 4 =2*2 가 된다. 그렇다면 1은 1x1이 된다는 것을 알 수 있다.
이제 반복문에 대해서 생각을 해보았다.
먼저 우리는 동적계획법을 할꺼고 bottom-up 방식을 사용하기 때문에 1부터 n까지 계산을
해줘야 된다.
for(int i = 1; i < n+1; i++) 로 시작하여
for(int j = 1l; j*j<i; j++)를 만든다. jxj < i 가 포인트인데 이유는
이렇게 하면 2의 제곱은 4부터 등장하게 되고, 처음 방식을 하면서 문제였었던 8은
d[8-4] = d[4] +1 = d[0] +1 +1 = 2가 될 수 있다.
따라서 조건에 의해 제곱수의 범위를 잘 나눌 수 있다. (손으로 해보는 것을 추천한다.)
점화식은 간단하다.
d[i] = Math.min(d[i],d[i-j*j]+1)
여기서 답을 놓칠뻔했다.
왜냐하면 d[i]를 초기화 해주지 않았다. d[i]의 초기화는 모두 d[i]=i로 해야된다.
이유는 모든 수는 1의 제곱으로 구성되어있기때문에, 1의 개수가 최대 개수가 된다.
코드 전체 보기
: 알고리즘은 항상 어렵다.
백준 2579 계단오르기 (0) | 2017.11.07 |
---|---|
백준 1463 1로 만들기 (0) | 2017.11.03 |
백준 11726,11727 2xN타일링 , 2xN타일링2 (0) | 2017.11.03 |
백준 11051 이항 계수2 (0) | 2017.11.01 |
백준 1915 가장 큰 정사각형 (0) | 2017.11.01 |
풀이방법: dfs
문제 해석
알고보니 예전에 틀렸던 문제이다, 왜 틀렸을까..
어렵지는 않다.
상하좌우 움직임 / dfs 만 알면된다.
풀이방식
한번 생각해보자 ,
지렁이는 움직인다. 지렁이가 이동하면서 모든 배추를 보호한다.
=> 다시말해서, 1이 모여있는 구역당 지렁이가 한마리면 된다.
상하좌우로 움직인다.
=> x,y가 움직일 두 개의 이동배열을 만든다.
int nx = x + dx[i];
int ny = y + dy[i];
1일때 dfs탐색을 시작한다.
=> map{i}{j}==1이면 탐색을 시작한다. 탐색을 시작할때마다 카운팅한다.
for (int i = 0; i < M ; i++) {
for (int j = 0; j < N ; j++) {
visitedi = true;
dfs(i, j);
cnt++;
}
}
}
방문했던것은 방문하지 않는다. (안하면 스택오버플로우)
=> 각 칸당 boolean 타입의 visited배열을 만들어 방문하면 true바꿔준다.
if (isRange(nx, ny)&& !visitednx&&mapnx==1) {
visitednx = true;
dfs(nx,ny);
}
이게 전부다. 그리고 재귀해주자,
코드 전체 보기
: 예전엔 왜 틀렸을까.. 중간에 10분정도 오류를 못찾았다.. 이유는..예제를 카운팅하면서 6으로 숫자를 세가지고
왜 5가 안되는거지 하면서 고민했다. 맞다 바보다..
풀이방법: 동적계획법
문제 해석
이항 계수 문제이다. 고등학교때 수학을 배웠다면, 쉽게 생각할 수 있다.
단 .. 기억을 하고있다면 ...
역시 나는 기억하지 못하고 있었다(공부는 못해도 수학은 좀 했다 신승범짱!)
네이버 검색을 해서 이항계수의 공식을 보는데 이렇게 풀면 되겠구나 하는게 있었다.
출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98
이 공식을 보고 풀이를 시작했다.
풀이방식
한번 생각해보자 ,
우리는 n과 k를 안다.
두가지로 나눠져있다.
=> 두개의 경우로 나눠서 합치자!
순열,조합을 풀다보면 항상 재귀를 떠올리게 된다.
이것 또한 재귀적 방법으로 풀면된다. 또한 메모이제이션을 통해 효율성을 높여주면된다.
그리고 공식에서는 우측이 n+1이지만, 우리는 굳이 저렇게 할필요없다. 모든 항목을 -1해주자
이제 끝이다. 뽑기만 하면된다.
그리고 베이스 케이스 설계를 해야되는데, 한 번 생각을 해보자, 뽑을때마다 각 케이스 별로 -1씩을 해줄것이다.
dp {n}[k} = solution(n-1,k-1) + solution(n-1,k);
이렇게 식을 세우게 되면 어느순간 k==n 또는 k==0이된다. 수학시간에 배웠다. nCn =1 , nC0 = 1이다.
그러면 우리는 베이스 케이스를 설계 할 수 있다.
if(n==k||k==0) return 1;
이렇게 설계하면 될 것이다.
그리고 메모이제이션
if(dp{n}{k}>0) return dp{n}{k}
이제 끝이다 !
이렇게 3줄이면 끝난다. 검증을 하고 싶다면 예제를 손으로 하면된다. 5분도 안걸린다.
코드 전체 보기
: 나이를 먹더니 수학을 다 까먹은 것 같다..
백준 2579 계단오르기 (0) | 2017.11.07 |
---|---|
백준 1463 1로 만들기 (0) | 2017.11.03 |
백준 11726,11727 2xN타일링 , 2xN타일링2 (0) | 2017.11.03 |
백준 1699 제곱수의 합 (0) | 2017.11.02 |
백준 1915 가장 큰 정사각형 (0) | 2017.11.01 |