알고리즘 소스코드 템플릿
2021. 6. 24. 10:28
소스코드
import java.text.*;
import java.time.Duration;
import java.time.Instant;
import java.util.stream.*;
import java.io.*;
import java.util.*;
public class Main {
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringBuilder sbb = new StringBuilder();
static void solve(int opih1, int opih2) throws Exception {
System.setIn(new FileInputStream("c:/Dev/git/algo/src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stt = null;
/* don't erase above line */
}
public static void main(String[] args) throws Exception {
solve(0,0);
}
static int stoi(String s) { return Integer.parseInt(s); }
static long stol(String s) { return Long.parseLong(s); }
static void print(String s) { System.out.println(s); }
static void print(int opih) { System.out.println(opih); }
static void print(long opih) { System.out.println(opih); }
static void print(StringBuilder sbb) { System.out.println(sbb.toString().trim()); }
static void print() { System.out.println(); }
}
class Pair {
int x, y, z, a, b, c;
String s;
Pair(int x, int y) { this.x = x; this.y = y; }
Pair(int x, int y, int z) { this.x = x; this.y = y; this.z = z; }
Pair(int x, int y, int z, int a) { this.x = x; this.y = y; this.z = z; this.a = a; }
Pair(int x, int y, int z, int a, int b) { this.x = x; this.y = y; this.z = z; this.a = a; this.b = b; }
Pair(int x, int y, int z, int a, int b, int c) { this.x = x; this.y = y; this.z = z; this.a = a; this.b = b; this.c = c; }
int getX() { return this.x; } int getY() { return this.y; } int getZ() { return this.z; }
int getA() { return this.a; } int getB() { return this.b; } int getC() { return this.c; }
String getS() { return this.s; }
}
/*
그래프 범위
// static boolean isRange(int x, int y) { return 0 <= x && x < N && 0 <= y && y < M; }
------------------------------------------------------------------------------------------------------
비교
Comparator<Pair> comp = Comparator.comparing(Pair::getX, Integer::compareTo).reversed()
.thenComparing(Pair::getY)
.thenComparing(Comparator.comparing(Pair::getZ, Integer::compareTo).reversed())
.thenComparing(Pair::getS,String::compareTo);
Comparator<> comp = new Comparator<>() {
@Override
public int compare(String s1, String s2) {
if (s1.length() != s2.length()) {
return s1.length() - s2.length();
}
else {
return s1.compareTo(s2);
}
}
}
Comparator<> comp = new Comparator<>() {
@Override
public int compare(Pair p1, Pair p2) {
// 그냥(양수)인 경우 오름차순
// 음수인 경우 내림차순
if(p1.x != p2.x){
return Integer.compare(p1.x, p2.x);
}
if(p1.y != p2.y){
return Integer.compare(p1.y, p2.y);
}
if(p1.z != p2.z){
return Integer.compare(p1.z, p2.z);
}
return p1.s.compareTo(p2.s);
}
};
------------------------------------------------------------------------------------------------------
List<> to Int[]
int[] arr = al.stream().mapToInt(x->x).toArray();
Int[] to List<>
List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
------------------------------------------------------------------------------------------------------
해쉬셋
HashSet<> hs = new HashSet<>();
값 넣기 add()
값 확인하기 contains()
해쉬 맵
put()
containsKey()
get()
for( String key : map.keySet() ){
System.out.println( String.format("키 : %s, 값 : %s", key, map.get(key)) );
}
해쉬맵(HashMap) to 리스트(list)
List<Pair> list = hm.values().stream().collect(Collectors.toList());
------------------------------------------------------------------------------------------------------
디큐
Deque<> dq = new ArrayDeque<>();
값 넣기 addFirst(), addLast();
값 빼기 pollFirst(), pollLast();
------------------------------------------------------------------------------------------------------
우선순위 큐
PriorityQueue<Integer> max_pq = new PriorityQueue<Integer>(Collections.reverseOrder());
PriorityQueue<Integer> min_pq = new PriorityQueue<Integer>();
값 넣기 add()
값 빼기 poll()
값 보기 peek()
------------------------------------------------------------------------------------------------------
다음 순열
public static boolean next_permutation(int[] arr) {
int i = arr.length - 1;
//i가 0일 경우 i-1가 음수가 되므로 i > 0여야 한다.
//arr[i-1]≥arr[i]를 만족하지 않는 i-1와 i번째를 찾으면 된다.
//만족하지 않아야 반복문을 진행시키므로
while(i > 0 && arr[i-1] >= arr[i]) i--;
if(i == 0) return false;
int j = arr.length - 1;
//arr[i-1] ≥ arr[j] 를 만족하지 않는 값을 찾으면 된다.
//j를 찾는다.
while(arr[i-1] >= arr[j]) j--;
//arr[i-1]과 arr[j]를 swap한다.
int tmp = arr[i-1];
arr[i-1] = arr[j];
arr[j] = tmp;
//array reverse
int k = arr.length - 1;
while(i < k) {
tmp = arr[i];
arr[i] = arr[k];
arr[k] = tmp;
i++; k--;
}
return true;
}
이전 순열
public static boolean prev_permutation(int[] arr) {
int i = arr.length - 1;
//i가 0일 경우 i-1가 음수가 되므로 i > 0여야 한다.
//arr[i-1]≥arr[i]를 만족하지 않는 i-1와 i번째를 찾으면 된다.
//만족하지 않아야 반복문을 진행시키므로
while(i > 0 && arr[i-1] <= arr[i]) i--;
if(i == 0) return false;
int j = arr.length - 1;
//arr[i-1] ≥ arr[j] 를 만족하지 않는 값을 찾으면 된다.
//j를 찾는다.
while(arr[i-1] <= arr[j]) j--;
//arr[i-1]과 arr[j]를 swap한다.
int tmp = arr[i-1];
arr[i-1] = arr[j];
arr[j] = tmp;
//array reverse
int k = arr.length - 1;
while(i < k) {
tmp = arr[i];
arr[i] = arr[k];
arr[k] = tmp;
i++; k--;
}
return true;
}
------------------------------------------------------------------------------------------------------
// BFS, DFS
static void dfs(int x){
check[x] = true;
for(int y : adj.get(x)){
if(!check[y]){
dfs(y);
}
}
}
static void dfs(int x, int y) {
check[x][y] = 1;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(0 <= nx && nx < height && 0 <= ny && ny < width) {
if(check[nx][ny] == 0 && graph[nx][ny] == 1) {
dfs(nx, ny);
}
}
}
}
static void bfs() {
while(!dq.isEmpty()) {
int dq_size = dq.size();
for(int i = 0; i < dq_size; i++) {
Pair p = dq.pollFirst();
int x = p.x;
int y = p.y;
for(int j = 0; j < 4; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if(0 <= nx && nx < H && 0 <= ny && ny < W) {
}
}
}
}
}
static void bfs(int x){
ArrayDeque<Integer> dq = new ArrayDeque<>();
dq.add(x);
check[x] = true;
while(!dq.isEmpty()){
int u = dq.pollFirst();
for(int v : adj.get(u)){
if(!check[v]) {
check[v] = true;
dq.add(v);
}
}
}
}
static void bfs(int x, int y){
ArrayDeque<Pair> dq = new ArrayDeque<>();
dq.add(new Pair(x, y));
check[x][y] = true;
int cnt = 0;
while(!dq.isEmpty()){
Pair pos = dq.pollFirst();
cnt += 1;
for(int i = 0; i < 4; i++) {
int next_x = pos.x + dx[i];
int next_y = pos.y + dy[i];
if(0 <= next_x && next_x < heigth && 0 <= next_y && next_y < width) {
if(graph[next_x][next_y] == && check[next_x][next_y] == false) {
check[next_x][next_y] = true;
dq.add(new Pair(next_x, next_y));
}
}
}
}
}
다익스트라 dijk
public static void dijk() {
Comparator<Node> comp = Comparator.comparing(Node::getCost, Long::compareTo);
PriorityQueue<Node> min_pq = new PriorityQueue<Node>(comp);
dist[START] = 0;
min_pq.add(new Node(START, dist[START]));
while(!min_pq.isEmpty()) {
Node nd = min_pq.poll();
int now = nd.dest;
long cost = nd.cost;
if(visited[now]) { continue; }
visited[now] = true;
if(now == END) break;
for(Node next : adj.get(now)) {
// 방문하지 않은 곳이라면 987654321 임
if(cost + next.cost < dist[next.dest]) {
dist[next.dest] = cost + next.cost;
min_pq.add(new Node(next.dest, dist[next.dest]));
}
}
}
}
------------------------------------------------------------------------------------------------------
숫자 레프트 쉬프트
static int intLeftShift(int n, int digit) {
int tmp = Math.pow(10, digit-1);
return (x%tmp)*10 + (int)(x/tmp);
}
next = (x%1000)*10 + (int)(x/1000) // 최대 자리수가 4자리인 경우
숫자 라이트 쉬프트
static int intRightShift(int n, int digit) {
int tmp = Math.pow(10, digit-1);
return (x%10)*tmp + (int)(x/10);
}
next = (x%10)*1000 + x//10 // 최대 자리수가 4자리인 경우
------------------------------------------------------------------------------------------------------
// 최대 공약수 gcd
public static int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a%b); }
// 최소 공배수 lcm
public static int lcm(int a, int b) { return (a*b)/gcd(a,b); }
------------------------------------------------------------------------------------------------------
int decimal = Integer.parseInt(binaryStr,2);
String hexStr = Integer.toString(decimal,16);
------------------------------------------------------------------------------------------------------
소수 판별
static boolean isPrime(int n) {
if(n < 2) return false;
for(int i = 2; i * i <= n; i++) {
if(n % i == 0) {
return false; //소수 인지 아닌지 판별
}
}
return true;
}
------------------------------------------------------------------------------------------------------
이분 탐색
long left = 1;
long right = [최대치];
while(left <= right) {
long mid = (left+right) / 2;
// 메차쿠차 비교대상 찾는 곳
if([비교 대상] > [비교대상]) {
// 찾을 곳 중 하나
left = mid + 1;
} else {
// 찾을 곳 중 하나
right = mid - 1;
}
}
------------------------------------------------------------------------------------------------------
머지 소트(merge sort)
https://mygumi.tistory.com/309
------------------------------------------------------------------------------------------------------
eof
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = "";
while( (str=br.readLine()) != null ) {
(내용들....)
}
----
BigInteger는 연산 결과 값이 immutable 함.
BigInteger a = new BigInteger(br.readLine(), 2);
BigInteger b = new BigInteger("17");
BigInteger c = a.multiply(b);
c.toString(2); // 이진수, 2진수
c.toString(8);
------------------------------------------------------------------------------------------------------
형식 지정자
%f
%e
------------------------------------------------------------------------------------------------------
//파스칼의 삼각형
List<List<Integer>> arr = new ArrayList<>();
int n = 40;
//삼각형 모양 생성 및 1로 채우기
for(int i = 1; i <= n; i++) {
List<Integer> al = new ArrayList<Integer>(i);
for(int j = 0; j < i; j++) {
al.add(1);
}
arr.add(al);
}
//이항계수 그려주기
for(int i = 2; i < n; i++) {
for(int j = 1; j < arr.get(i).size()-1; j++) {
int a = arr.get(i-1).get(j-1);
int b = arr.get(i-1).get(j);
arr.get(i).set(j, a+b);
}
}
//테스트
for(List<Integer> al : arr) {
print(al.toString());
}
----
lower_bound
public static int lower_bound(int[] arr, int end, int n) {
int start = 0;
while (start < end) {
int mid = (end + start) / 2;
if (arr[mid] < n) { // 왼 arr[mid] < n 오른 arr[mid] > n
start = mid + 1; // 왼쪽
} else {
end = mid; // 왼쪽
}
}
return end;
}
---
prefix_sum
in = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
arr[i] = stoi(in[i-1]);
}
//prefix_sum
long[] p = new long[n+3];
for(int i = 1; i <= n; i++) {
p[i] = p[i-1] + arr[i];
}
---
LLIS
int[] d = new int[n+1];
d[0] = arr[0];
Pair[] trace = new Pair[n+1];
trace[0] = new Pair(0, arr[0]);// 트레이싱
int idx = 0; // d[0]부터 이분탐색해야 하니까
for(int i = 1; i < n; i++) {// arr는 n까지밖에 없으니까
if(d[idx] < arr[i]) {
d[++idx] = arr[i];
trace[i] = new Pair(idx, arr[i]); // 트레이싱
} else {
int prev_idx = lower_bound(d, idx, arr[i]);
d[prev_idx] = arr[i]; // 원래 자리를 찾아감
trace[i] = new Pair(prev_idx, arr[i]); // 트레이싱
}
}
// 트레이싱
Stack<Integer> stack = new Stack<Integer>();
int temp = idx;
for (int i = n - 1; i >= 0; i--) {
if (temp == trace[i].x) {
stack.push(trace[i].y);
--temp;
}
}
while(!stack.isEmpty()) {
sb.append(stack.pop() + " ");
}
print(sb);
-----
MST PRIM
static int prim() {
int cost = 0, remain = N;
boolean[] visited = new boolean[N+1];
//최소 우큐
PriorityQueue<Pair> ascpq = new PriorityQueue<Pair>(Comparator.comparing(Pair::getY, Integer::compareTo));
// 자기 노드추가, 본인에 가는데는 안움직여도되니 0
ascpq.add(new Pair(1, 0));
while(!ascpq.isEmpty()) {
Pair now = ascpq.poll();
if(visited[now.x] == false) {
visited[now.x] = true;
cost += now.y;
remain--;
for(Pair next : adj.get(now.x)) {
if(visited[next.x] == false) {
ascpq.add(next);
}
}
}
if(remain == 0) {
break;
}
}
return cost;
}
----
유니온 파인드 UNION FIND
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
public static int v, e;
public static int[] parent = new int[100001]; // 부모 테이블 초기화하기
// 특정 원소가 속한 집합을 찾기
public static int find(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return parent[x] = find(parent[x]);
}
// 두 원소가 속한 집합을 합치기
public static void union(int a, int b) {
a = find(a);
b = find(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
// Union 연산을 각각 수행
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
unionParent(a, b);
}
// 각 원소가 속한 집합 출력하기
System.out.print("각 원소가 속한 집합: ");
for (int i = 1; i <= v; i++) {
System.out.print(findParent(i) + " ");
}
System.out.println();
// 부모 테이블 내용 출력하기
System.out.print("부모 테이블: ");
for (int i = 1; i <= v; i++) {
System.out.print(parent[i] + " ");
}
System.out.println();
}
---
달팽이이이이이ㅣㅇ이잉
int N = stoi(br.readLine());
int[][] arr = new int[N][N];
int I, J;
I = (int)(N/2);
J = (int)(N/2);
//print(I + " " + J);
int k = 0;
int dir = -1;
int grade = 0;
while(true) {
if(k > N * N) break;
if(k == 0) {
k++;
arr[I][J] = k;
continue;
}
grade++;
for(int i = 0; i < grade; i++) {
k++;
if(k > N * N) break;
I += dir;
arr[I][J] = k;
}
dir *= -1;
for(int i = 0; i < grade; i++) {
k++;
if(k > N * N) break;
J += dir;
arr[I][J] = k;
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
sbb.append(arr[i][j] + " ");
}
sbb.append("\n");
}
print(sbb.toString().trim());
-----------------
벨만포드
static boolean bellman(int cur) {
Arrays.fill(dist, 987654321);
dist[cur] = 0;
boolean isUpdated = false;
for(int i = 1; i < N; i++) {
isUpdated = false;
for(int j = 1; j <= N; j++) {
for(Road r : adj.get(j)) {
if(dist[j] != INF && dist[r.end] > dist[j] + r.weight) {
dist[r.end] = dist[j] + r.weight;
isUpdated = true;
}
}
}
if(isUpdated == false) break;
}
if(isUpdated) {
for(int i = 1; i <= N; i++) {
for(Road r : adj.get(i)) {
if(dist[i] != INF && dist[r.end] > dist[i] + r.weight) {
return true;
}
}
}
}
return false;
}
*/
/*
class Pair {
int x, y, z, a, b, c;
long cost;
String s;
Pair(int x, int y) { this.x = x; this.y = y; }
Pair(int x, int y, int z) { this(x, y); this.z = z; }
Pair(int x, int y, int z, int a) { this(x, y, z); this.a = a; }
Pair(int x, int y, int z, int a, int b) { this(x, y, z, a); this.b = b; }
Pair(int x, int y, int z, int a, int b, int c) { this(x, y, z, a, b); this.c = c; }
Pair(int x, int y, String s) { this(x, y); this.s = s; }
Pair(int x, int y, int z, String s) { this(x, y, z); this.s = s; }
Pair(int x, long cost) { this.x = x; this.cost = cost; }
int getX() { return this.x; } int getY() { return this.y; } int getZ() { return this.z; }
int getA() { return this.a; } int getB() { return this.b; } int getC() { return this.c; }
long getCost() { return this.cost; }
String getS() { return this.s; }
}
*/
/*
그래프 범위
// static boolean isRange(int x, int y) { return 0 <= x && x < N && 0 <= y && y < M; }
------------------------------------------------------------------------------------------------------
비교
Comparator<Pair> comp = Comparator.comparing(Pair::getX, Integer::compareTo).reversed()
.thenComparing(Pair::getY)
.thenComparing(Comparator.comparing(Pair::getZ, Integer::compareTo).reversed())
.thenComparing(Pair::getS,String::compareTo);
Comparator<> comp = new Comparator<>() {
@Override
public int compare(String s1, String s2) {
if (s1.length() != s2.length()) {
return s1.length() - s2.length();
}
else {
return s1.compareTo(s2);
}
}
}
Comparator<> comp = new Comparator<>() {
@Override
public int compare(Pair p1, Pair p2) {
// 그냥(양수)인 경우 오름차순
// 음수인 경우 내림차순
if(p1.x != p2.x){
return Integer.compare(p1.x, p2.x);
}
if(p1.y != p2.y){
return Integer.compare(p1.y, p2.y);
}
if(p1.z != p2.z){
return Integer.compare(p1.z, p2.z);
}
return p1.s.compareTo(p2.s);
}
};
------------------------------------------------------------------------------------------------------
Array[] to Int[]
int[] NS = Arrays.asList(br.readLine().split(" ")).stream().mapToInt(Integer::parseInt).toArray();
------------------------------------------------------------------------------------------------------
해쉬셋
HashSet<> hs = new HashSet<>();
값 넣기 add()
값 확인하기 contains()
해쉬 맵
put()
containsKey()
get()
for( String key : map.keySet() ){
System.out.println( String.format("키 : %s, 값 : %s", key, map.get(key)) );
}
해쉬맵(HashMap) to 리스트(list)
List<Pair> list = hm.values().stream().collect(Collectors.toList());
------------------------------------------------------------------------------------------------------
디큐
Deque<> dq = new ArrayDeque<>();
값 넣기 addFirst(), addLast();
값 빼기 pollFirst(), pollLast();
------------------------------------------------------------------------------------------------------
우선순위 큐
PriorityQueue<Integer> max_pq = new PriorityQueue<Integer>(Collections.reverseOrder());
PriorityQueue<Integer> min_pq = new PriorityQueue<Integer>();
값 넣기 add()
값 빼기 poll()
값 보기 peek()
------------------------------------------------------------------------------------------------------
다음 순열
public static boolean next_permutation(int[] arr) {
int i = arr.length - 1;
//i가 0일 경우 i-1가 음수가 되므로 i > 0여야 한다.
//arr[i-1]≥arr[i]를 만족하지 않는 i-1와 i번째를 찾으면 된다.
//만족하지 않아야 반복문을 진행시키므로
while(i > 0 && arr[i-1] >= arr[i]) i--;
if(i == 0) return false;
int j = arr.length - 1;
//arr[i-1] ≥ arr[j] 를 만족하지 않는 값을 찾으면 된다.
//j를 찾는다.
while(arr[i-1] >= arr[j]) j--;
//arr[i-1]과 arr[j]를 swap한다.
int tmp = arr[i-1];
arr[i-1] = arr[j];
arr[j] = tmp;
//array reverse
int k = arr.length - 1;
while(i < k) {
tmp = arr[i];
arr[i] = arr[k];
arr[k] = tmp;
i++; k--;
}
return true;
}
이전 순열
public static boolean prev_permutation(int[] arr) {
int i = arr.length - 1;
//i가 0일 경우 i-1가 음수가 되므로 i > 0여야 한다.
//arr[i-1]≥arr[i]를 만족하지 않는 i-1와 i번째를 찾으면 된다.
//만족하지 않아야 반복문을 진행시키므로
while(i > 0 && arr[i-1] <= arr[i]) i--;
if(i == 0) return false;
int j = arr.length - 1;
//arr[i-1] ≥ arr[j] 를 만족하지 않는 값을 찾으면 된다.
//j를 찾는다.
while(arr[i-1] <= arr[j]) j--;
//arr[i-1]과 arr[j]를 swap한다.
int tmp = arr[i-1];
arr[i-1] = arr[j];
arr[j] = tmp;
//array reverse
int k = arr.length - 1;
while(i < k) {
tmp = arr[i];
arr[i] = arr[k];
arr[k] = tmp;
i++; k--;
}
return true;
}
------------------------------------------------------------------------------------------------------
// BFS, DFS
static void dfs(int x){
check[x] = true;
for(int y : adj.get(x)){
if(!check[y]){
dfs(y);
}
}
}
static void dfs(int x, int y) {
check[x][y] = 1;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(0 <= nx && nx < height && 0 <= ny && ny < width) {
if(check[nx][ny] == 0 && graph[nx][ny] == 1) {
dfs(nx, ny);
}
}
}
}
static void bfs() {
while(!dq.isEmpty()) {
int dq_size = dq.size();
for(int i = 0; i < dq_size; i++) {
Pair p = dq.pollFirst();
int x = p.x;
int y = p.y;
for(int j = 0; j < 4; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if(0 <= nx && nx < H && 0 <= ny && ny < W) {
}
}
}
}
}
static void bfs(int x){
ArrayDeque<Integer> dq = new ArrayDeque<>();
dq.add(x);
check[x] = true;
while(!dq.isEmpty()){
int u = dq.pollFirst();
for(int v : adj.get(u)){
if(!check[v]) {
check[v] = true;
dq.add(v);
}
}
}
}
static void bfs(int x, int y){
ArrayDeque<Pair> dq = new ArrayDeque<>();
dq.add(new Pair(x, y));
check[x][y] = true;
int cnt = 0;
while(!dq.isEmpty()){
Pair pos = dq.pollFirst();
cnt += 1;
for(int i = 0; i < 4; i++) {
int next_x = pos.x + dx[i];
int next_y = pos.y + dy[i];
if(0 <= next_x && next_x < heigth && 0 <= next_y && next_y < width) {
if(graph[next_x][next_y] == && check[next_x][next_y] == false) {
check[next_x][next_y] = true;
dq.add(new Pair(next_x, next_y));
}
}
}
}
}
다익스트라 djik
public static void djik() {
Comparator<Node> comp = Comparator.comparing(Node::getCost, Long::compareTo);
PriorityQueue<Node> min_pq = new PriorityQueue<Node>(comp);
dist[START] = 0;
min_pq.add(new Node(START, dist[START]));
while(!min_pq.isEmpty()) {
Node nd = min_pq.poll();
int now = nd.dest;
long cost = nd.cost;
if(visited[now]) { continue; }
visited[now] = true;
if(now == END) break;
for(Node next : adj.get(now)) {
// 방문하지 않은 곳이라면 987654321 임
if(cost + next.cost < dist[next.dest]) {
dist[next.dest] = cost + next.cost;
min_pq.add(new Node(next.dest, dist[next.dest]));
}
}
}
}
------------------------------------------------------------------------------------------------------
숫자 레프트 쉬프트
static int intLeftShift(int n, int digit) {
int tmp = Math.pow(10, digit-1);
return (x%tmp)*10 + (int)(x/tmp);
}
next = (x%1000)*10 + (int)(x/1000) // 최대 자리수가 4자리인 경우
숫자 라이트 쉬프트
static int intRightShift(int n, int digit) {
int tmp = Math.pow(10, digit-1);
return (x%10)*tmp + (int)(x/10);
}
next = (x%10)*1000 + x//10 // 최대 자리수가 4자리인 경우
------------------------------------------------------------------------------------------------------
// 최소 공배수 gcd
public static long gcd(long a, long b) { return (b == 0) ? a : gcd(b, a%b); }
// 최대 공약수 lcd
public static int lcm(int a, int b) {
return (a/gcd(a,b)) * (b/gcd(a,b) * gcd(a,b));
}
------------------------------------------------------------------------------------------------------
int decimal = Integer.parseInt(binaryStr,2);
String hexStr = Integer.toString(decimal,16);
------------------------------------------------------------------------------------------------------
소수 판별
static boolean isPrime(int n) {
if(n < 2) return false;
for(int i = 2; i * i <= n; i++) {
if(n % i == 0) {
return false; //소수 인지 아닌지 판별
}
}
return true;
}
------------------------------------------------------------------------------------------------------
에라토스테네스의 체
static boolean[] era(int MAX) {
boolean[] era = new boolean[MAX+1];
// true 지워짐 , 소수아님
// false 안 지워짐, 소수임
era[0] = era[1] = true;
for(int i = 2; i <= MAX; i++) {
if(era[i] == false) {
// i 는 소수임
for(int p = i+i; p <= MAX; p += i)
// 소수아닌 수들 지우는 과정
// 이전 수들은 지울 필요 X
// 지운 수들은 또 지워도 문제 X
era[p] = true;
}
}
return era;
}
------------------------------------------------------------------------------------------------------
이분 탐색
long left = 1;
long right = [최대치];
while(left <= right) {
long mid = (left+right) / 2;
// 메차쿠차 비교대상 찾는 곳
if([비교 대상] > [비교대상]) {
// 찾을 곳 중 하나
left = mid + 1;
} else {
// 찾을 곳 중 하나
right = mid - 1;
}
}
------------------------------------------------------------------------------------------------------
머지 소트(merge sort)
https://mygumi.tistory.com/309
------------------------------------------------------------------------------------------------------
eof
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = "";
while( (str=br.readLine()) != null ) {
(내용들....)
}
----
BigInteger는 연산 결과 값이 immutable 함.
BigInteger a = new BigInteger(br.readLine(), 2);
BigInteger b = new BigInteger("17");
BigInteger c = a.multiply(b);
c.toString(2); // 이진수, 2진수
c.toString(8);
------------------------------------------------------------------------------------------------------
형식 지정자
%f
%e
------------------------------------------------------------------------------------------------------
//파스칼의 삼각형
List<List<Integer>> arr = new ArrayList<>();
int n = 40;
//삼각형 모양 생성 및 1로 채우기
for(int i = 1; i <= n; i++) {
List<Integer> al = new ArrayList<Integer>(i);
for(int j = 0; j < i; j++) {
al.add(1);
}
arr.add(al);
}
//이항계수 그려주기
for(int i = 2; i < n; i++) {
for(int j = 1; j < arr.get(i).size()-1; j++) {
int a = arr.get(i-1).get(j-1);
int b = arr.get(i-1).get(j);
arr.get(i).set(j, a+b);
}
}
//테스트
for(List<Integer> al : arr) {
print(al.toString());
}
----
lower_bound
public static int lower_bound(int[] arr, int end, int n) {
int start = 0;
while (start < end) {
int mid = (end + start) / 2;
if (arr[mid] < n) { // 왼 arr[mid] < n 오른 arr[mid] > n
start = mid + 1; // 왼쪽
} else {
end = mid; // 왼쪽
}
}
return end;
}
---
prefix_sum
in = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
arr[i] = stoi(in[i-1]);
}
//prefix_sum
long[] p = new long[n+3];
for(int i = 1; i <= n; i++) {
p[i] = p[i-1] + arr[i];
}
---
LLIS
int[] d = new int[n+1];
d[0] = arr[0];
Pair[] trace = new Pair[n+1];
trace[0] = new Pair(0, arr[0]);// 트레이싱
int idx = 0; // d[0]부터 이분탐색해야 하니까
for(int i = 1; i < n; i++) {// arr는 n까지밖에 없으니까
if(d[idx] < arr[i]) {
d[++idx] = arr[i];
trace[i] = new Pair(idx, arr[i]); // 트레이싱
} else {
int prev_idx = lower_bound(d, idx, arr[i]);
d[prev_idx] = arr[i]; // 원래 자리를 찾아감
trace[i] = new Pair(prev_idx, arr[i]); // 트레이싱
}
}
// 트레이싱
Stack<Integer> stack = new Stack<Integer>();
int temp = idx;
for (int i = n - 1; i >= 0; i--) {
if (temp == trace[i].x) {
stack.push(trace[i].y);
--temp;
}
}
while(!stack.isEmpty()) {
sb.append(stack.pop() + " ");
}
print(sb);
-----
MST PRIM
static int prim() {
int cost = 0, remain = N;
boolean[] visited = new boolean[N+1];
//최소 우큐
PriorityQueue<Pair> ascpq = new PriorityQueue<Pair>(Comparator.comparing(Pair::getY, Integer::compareTo));
// 자기 노드추가, 본인에 가는데는 안움직여도되니 0
ascpq.add(new Pair(1, 0));
while(!ascpq.isEmpty()) {
Pair now = ascpq.poll();
if(visited[now.x] == false) {
visited[now.x] = true;
cost += now.y;
remain--;
for(Pair next : adj.get(now.x)) {
if(visited[next.x] == false) {
ascpq.add(next);
}
}
}
if(remain == 0) {
break;
}
}
return cost;
}
----
유니온 파인드 UNION FIND
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
public static int v, e;
public static int[] parent = new int[100001]; // 부모 테이블 초기화하기
// 특정 원소가 속한 집합을 찾기
public static int find(int x) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x;
return parent[x] = find(parent[x]);
}
// 두 원소가 속한 집합을 합치기
public static void union(int a, int b) {
a = find(a);
b = find(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
// Union 연산을 각각 수행
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
unionParent(a, b);
}
// 각 원소가 속한 집합 출력하기
System.out.print("각 원소가 속한 집합: ");
for (int i = 1; i <= v; i++) {
System.out.print(findParent(i) + " ");
}
System.out.println();
// 부모 테이블 내용 출력하기
System.out.print("부모 테이블: ");
for (int i = 1; i <= v; i++) {
System.out.print(parent[i] + " ");
}
System.out.println();
}
---
달팽이이이이이ㅣㅇ이잉
int N = stoi(br.readLine());
int[][] arr = new int[N][N];
int I, J;
I = (int)(N/2);
J = (int)(N/2);
//print(I + " " + J);
int k = 0;
int dir = -1;
int grade = 0;
while(true) {
if(k > N * N) break;
if(k == 0) {
k++;
arr[I][J] = k;
continue;
}
grade++;
for(int i = 0; i < grade; i++) {
k++;
if(k > N * N) break;
I += dir;
arr[I][J] = k;
}
dir *= -1;
for(int i = 0; i < grade; i++) {
k++;
if(k > N * N) break;
J += dir;
arr[I][J] = k;
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
sbb.append(arr[i][j] + " ");
}
sbb.append("\n");
}
print(sbb.toString().trim());
-----------------
벨만포드
static boolean bellman(int cur) {
Arrays.fill(dist, 987654321);
dist[cur] = 0;
boolean isUpdated = false;
for(int i = 1; i < N; i++) {
isUpdated = false;
for(int j = 1; j <= N; j++) {
for(Road r : adj.get(j)) {
if(dist[j] != INF && dist[r.end] > dist[j] + r.weight) {
dist[r.end] = dist[j] + r.weight;
isUpdated = true;
}
}
}
if(isUpdated == false) break;
}
if(isUpdated) {
for(int i = 1; i <= N; i++) {
for(Road r : adj.get(i)) {
if(dist[i] != INF && dist[r.end] > dist[i] + r.weight) {
return true;
}
}
}
}
return false;
}
-----------------------------------
조합 경우의 수
public static int combination(int n, int r) {
if(n == r || r == 0)
return 1;
else
return combination(n - 1, r - 1) + combination(n - 1, r);
}
--------------------------------------------
알파벳 좌측방향
('주어진 문자'-'z'+26));
----
정수 판별
String.matches("\\d+?");
-------------------
edit prace
public void getTrace(int M[][], String a, String b) {
System.out.println("[ " + b + "을(를) " + a + "로 바꾸는 과정 추적 ]");
int i = a.length() - 1;
int j = b.length() - 1;
while(!(i == 0 && j == 0)) {
int s = getMin(M[i - 1][j], M[i - 1][j - 1], M[i][j - 1]);
if(s == M[i][j]) {
i -= 1;
j -= 1;
}
else {
if(s == M[i][j - 1]) {
j -= 1;
}
else if(s == M[i - 1][j - 1]) {
i -= 1;
j -= 1;
}
else {
i -= 1;
}
}
}
}
*/
