sudo dd if=/dev/zero of=/swapfile bs=128M count=16
위와 같이 설정할 경우 스왑 공간은 128MB x 16 = 2GB가 된다.
sudo chmod 600 /swapfile
스왑 파일의 읽기 및 쓰기 권한 업데이트
sudo mkswap /swapfile
Linux 스왑 영역 설정
sudo swapon /swapfile
스왑 공간에 스왑 파일을 추가하여 스왑 파일 즉시 사용 가능
sudo swapon -s
프로시저가 성공적인지 확인
sudo vi /etc/fstab
/etc/fstab 파일을 편집하여 부팅 시 스왑 파일을 시작하도록 한다.
스왑 파일은 아래와 같이 마지막에 /swapfile swap swap defaults 0 0 코드를 추가해준다.
이로써 스왑 설정이 마무리됐다.
sudo ./gradlew clean build 를 실행해 빌드를 시도해보면 잘되는 것을 확인할 수 있다.
N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.
풀이:
소인수분해 문제를 해결하기 위해서는 우선 소수를 판정하는 방법에 대해 알아야한다.
어떤 수 $x$가 소수일 조건은 약수로 1과 자기 자신만을 가져야 한다. 따라서 $x$를 $[2, x - 1]$ 범위 내의 수로 나누었을때, 나누어 떨어지는 수가 없으면 그 수는 소수이다. 이를 코드로 표현하면 다음과 같다.
bool IsPrime(int x) {
for (int i = 2; i < x; ++i) {
if (x % i == 0)
return false;
}
return true;
}
위 알고리즘의 시간복잡도는 $O(x)$이다. 이 시간복잡도를 줄일 수가 있는데 이론은 다음과 같다.
$\sqrt{x}$ 보다 큰 수 $d$가 $x$의 약수라고 하자. ($\sqrt{x} < d$) 그럼, $x = d * m$이 성립하는 $m$이 존재한다. $d$와 $m$의 곱은 $x$보다 작아야 하므로 ($m < \sqrt{x} < d$)라는 부등식을 세울 수 있다. 즉, $\sqrt{x}$보다 작은 수 $y$가 $x$의 약수이면 $y$와 곱했을때, $x$가 나오는 수가 반드시 존재하는 것이다. 따라서, 우리는 다음과 같이 소수 판정의 범위를 줄일 수가 있다.
bool IsPrime(int x) {
for (int i = 2; i*i <= x; ++i) {
if (x % i == 0)
return false;
}
return true;
}
이를 통해 우린 시간복잡도를 $O(\sqrt{x})$로 줄일 수 있다.
소수를 판정하는 대표적인 방법으로는 에라토스테네스의 체가 있다. 에라토스테네스의 체는 1과 자기자신 사이에 약수의 배수를 모두 지우면 남는 수가 약수라는 이론이다.
예를 들어, $72$가 있으면 $2*2*2*3*3$으로 표현된다. 이를 살펴보면 2로 가능한 나누어 표현하고 그 다음으로 3으로 가능한 나누어 표현하였다.
따라서 우리는 어떤 수 $x$에 대해 작은 수부터 가능할 때까지 나누어주며 그 수를 출력해주면 된다. 범위는 앞선 알고리즘에서 살펴본 바로 $[2, \sqrt{x} - 1]$ 까지로 하면 된다. 결과적으로 2의 배수, 3의 배수, 5의 배수...가 차례대로 지워지면서 소인수들이 갯수만큼 출력이 된다.
#include <iostream>
using namespace std;
void __init() {
cin.tie(0);
ios::sync_with_stdio(0);
}
void Factorization(int num) {
for(int i = 2; i*i <= num; i++) {
while(num % i == 0) {
cout << i << "\n";
num /= i;
}
}
if(num != 1) cout << num;
}
int main() {
int num;
__init();
cin >> num;
Factorization(num);
}
준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.
준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.
준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.
입력:
첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)
둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.
출력:
첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.
풀이:
오른쪽, 아래, 대각선으로 이동가능하지만 대각선은 배제하고 생각해도 된다. 그 이유는 우선, 대각선으로 이동하기 위해서는 대각선 or 아래 -> 오른쪽 or 오른쪽 -> 아래 세 가지 길이 있다. 최대한 많은 사탕을 먹어야 하므로 지름길인 대각선 방향은 배제한다.
y와 x의 범위 체크를 위해 isValidCoord 함수를 사용했고, 아래, 오른쪽으로 이동을 표현하기 위해 구조체 dir을 만들었다.
문제를 처음 보고 나는 DFS를 떠올렸다. 그래서 DFS로 짜기 시작했는데 코드를 진행하다 보니 사탕의 양을 저장해 줄 DP가 필요하다는 것을 깨달았다. DFS와 DP를 이용해서 풀어야지 마음 먹고 다시 짜 내려갔는데 이 문제는 DFS를 쓰면 오히려 더욱 복잡해지는 문제라는 것을 알았다. 단순 완전탐색으로 DP를 활용해 진행하면 된다.
코드:
#include <iostream> #include <algorithm> #define DIR 2 using namespace std; int N, M; int Maze[1001][1001]; int DP[1001][1001]; typedef struct { int y, x; } Dir; Dir dir[DIR] = {{0,1},{1,0}}; bool isValidCoord(int y, int x) { return 0 <= y && y < N && 0 <= x && x < M; }
int main() { cin >> N >> M; for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) cin >> Maze[i][j]; DP[0][0] = Maze[0][0]; for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { for (int k = 0; k < DIR; ++k) { int dy = i + dir[k].y; int dx = j + dir[k].x; if(isValidCoord(dy, dx)) DP[dy][dx] = max(DP[dy][dx], DP[i][j] + Maze[dy][dx]); } } }
