# G1

6개의 포스트
post-thumbnail

[BOJ 20158 / C++] 사장님 달려가고 있습니다

백준 문제 링크 : 20158 - 사장님 달려가고 있습니다 문제 알바 첫날인 정훈이는 늦잠을 잤다. 다행히도 정훈이는 달리기가 정말 빨라서 괜찮다고 생각했지만, 오늘은 공사로 인해 길을 통제하는 중이었다. 첫날부터 늦을 수 없는 정훈이는 가장 빠른 경로를 생각하며 달린다. 공사 지도 N x N가 있다. 정훈이는 0초에 맨 왼쪽 위(1, 1)에서 출발하고 맨 오른쪽 아래(N, N)에 도착해야 한다. 달리는 방향은 상,하,좌,우로 달릴 수 있다. 매초 1칸을 갈 수 있고 전과 같은 방향으로 달린다면 가속도가 붙어 1초 안에 전보다 1칸을 더 갈 수 있다. (전에 오른쪽으로 1칸을 갔다면 오른쪽으로 2칸을 1초에 갈 수 있다.) 가속도를 주체할 수 없으므로 방향전환을 해야만 다시 1초에 1칸을 갈 수 있다. 정훈이는 현재 위치에서 달려갈 때 1초 후 지도 밖에 서 있다면 갈 수 없다고

2023년 7월 19일
·
4개의 댓글
·
post-thumbnail

G1 Garbage Collector. Young/Old GC

본 글은 ORACLE의 Getting Started with the G1 Garbage Collector의 일부를 번역한 글입니다. 구형 Garbage Collector들에 대해 먼저 알아보고 읽으시는 것을 추천드립니다. Garbege-First Collector 개요 구형 가비지 콜렉터(Serial, Parallel, CMS...)의 힙 구조는 Young/Old/Permanent Generation 세 구역으로 나누어 진다. 모든 메모리 객체는 이 세 구역 내에 포함된다. 그러나 G1 콜렉터는 다른 접근 방식을 취한다. ![](https://velog.velc

2023년 7월 15일
·
0개의 댓글
·

[백준 2213] 트리의 독립집합 (DP/DFS, 자바스크립트)

트리의 독립집합 문제 그래프 G(V, E)에서 정점의 부분 집합 S에 속한 모든 정점쌍이 서로 인접하지 않으면 (정점쌍을 잇는 간선이 없으면) S를 독립 집합(independent set)이라고 한다. 독립 집합의 크기는 정점에 가중치가 주어져 있지 않을 경우는 독립 집합에 속한 정점의 수를 말하고, 정점에 가중치가 주어져 있으면 독립 집합에 속한 정점의 가중치의 합으로 정의한다. 독립 집합이 공집합일 때 그 크기는 0이라고 하자. 크기가 최대인 독립 집합을 최대 독립 집합이라고 한다. 문제는 일반적인 그래프가 아니라 트리(연결되어 있고 사이클이 없는 그래프)와 각 정점의 가중치가 양의 정수로 주어져 있을 때, 최대 독립 집합을 구하는 것이다. 입력 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는

2023년 2월 20일
·
0개의 댓글
·

[백준 16933] 벽 부수고 이동하기 3

벽 부수고 이동하기 3 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 이동하지 않고 같은 칸에 머물러있는 경우도 가능하다. 이 경우도 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 한다. 이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다. 만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.

2023년 1월 27일
·
0개의 댓글
·

[백준 1562] 계단 수 (DP, 자바스크립트)

https://www.acmicpc.net/problem/1562 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 풀이 길이가 n인 계단수를 만들려면 길이가 n-1인 계단수 뒤에 마지막 수와 1 차이나는 수를 붙여주면 된다. 이를 메모이제이션 하기 위해서는 n x 10만큼의 배열을 만들어주면 된다. 하지만 이 문제에서는 0부터 9까지가 포함되었는지 체크해야 하므로n x 10 x (2^10)만큼의 배열이 필요하다. 그러한 배

2023년 1월 13일
·
0개의 댓글
·
post-thumbnail

[백준 2098] 외판원 순회 (DP, 자바스크립트)

https://www.acmicpc.net/problem/2098 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다. 각 도시간에 이동하는데 드는 비용은 행렬 Wi형태로 주어진다. Wi는

2023년 1월 12일
·
0개의 댓글
·