2021년 07월 04일 TIL
오늘은 네이버웹툰 코테에 대비해서 전체적으로 알고리즘을 복습했다.
알고리즘 정리
순열
// 순서를 지키면서 n 개중에서 r 개를 뽑는 경우
// 사용 예시: perm(arr, output, visited, 0, n, 3);
static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
if (depth == r) {
print(output, r);
return;
}
for (int i=0; i<n; i++) {
if (visited[i] != true) {
visited[i] = true;
output[depth] = arr[i];
perm(arr, output, visited, depth + 1, n, r);
output[depth] = 0; // 이 줄은 없어도 됨
visited[i] = false;;
}
}
}
이분탐색
- Arrays.binarySearch (정렬한 뒤에 사용해야함), 찾는 숫자가 있으면 양수, 아니면 음수 반환
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/*
* 수를 입력받아서 정렬해주고,
* Arrays.binarySearch 메서드를 통해서 그 배열에 숫자가 있는지 체크합니다
* 있다면 양수, 없다면 음수가 나오므로 그에 따라서 0과 1을 출력합니다.
*
*/
public class BOJ_1920_수찾기 {
static int N, M;
static int[] numArr;
static int[] exist;
static int[] res;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = stoi(br.readLine());
numArr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
numArr[i] = stoi(st.nextToken());
}
Arrays.sort(numArr);
M = stoi(br.readLine());
res = new int[M];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
res[i] = Arrays.binarySearch(numArr, stoi(st.nextToken()));
}
for (int i : res) {
if (i < 0) {
System.out.println(0);
continue;
} else {
System.out.println(1);
}
}
}
private static int stoi(String s) {
return Integer.parseInt(s);
}
}
- 이분탐색 (최소값 구할 시 bot을 return, 최대값 구할 시 top return)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
* bot을 1로 잡고, max는 현우가 이용할 금액들 중 최대값 * i로 잡고, 그 중간지점으로 시작하여
* 만약 인출횟수가 목표로하는 숫자보다 적다면 현재 인출하는 금액이 너무 크다는 뜻이므로 top을 mid-1로 옮겨서 다시 탐색
* 크다면, 인출금액이 너무 작다는 뜻이므로 bot을 mid+1로 올림
* 같다면, 이제 인출 최소금액을 찾으면 됩니다. 최대값을 찾는게 아니라 최소값을 찾는 것이므로,
* top을 mid-1로 낮추고 다시 check 메서드 실행
* bot이 top보다 크거나 같아지면 bot을 출력
*
*/
public class BOJ_6236_용돈관리 {
static int N, M;
static int[] numArr;
static int maxMoney = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = stoi(st.nextToken());
M = stoi(st.nextToken());
numArr = new int[N];
for (int i = 0; i < N; i++) {
numArr[i] = stoi(br.readLine());
maxMoney = Math.max(maxMoney, numArr[i]);
}
solve();
}
private static void solve() {
int bot = 1;
int top = maxMoney * M;
while (bot <= top) {
int mid = (bot + top) / 2;
switch (check(mid)) {
case 0: // 같은 횟수였음(이제 최소값 찾으면 됩니다)
top = mid - 1;
break;
case 1: // 횟수가 M보다 적었음(숫자가 너무 크단뜻)
top = mid - 1;
break;
case 2: // 횟수가 M보다 컸음(숫자가 너무 작단뜻) 혹은 인출값이 하루치 사용양보다 적었음
bot = mid + 1;
break;
}
}
System.out.println(bot);
}
private static int check(int mid) {
int left = mid;
int cnt = 1;
for (int i = 0; i < N; i++) {
if (left >= numArr[i]) {
left -= numArr[i];
} else {
if (numArr[i] > mid) {
return 2;
}
left = mid;
i--;
cnt++;
continue;
}
}
if (cnt == M) {
return 0;
} else if (cnt < M) {
return 1;
} else {
return 2;
}
}
private static int stoi(String s) {
return Integer.parseInt(s);
}
}
트리
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
/*
* 트리 클래스를 만들고, 노드 만들어서 전위 중위 후위 순회 돌렸습니당
*
*/
public class BOJ_1991_트리순회 {
static int N;
static Map<String, Node> tree = new HashMap<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = stoi(br.readLine());
StringTokenizer st;
Tree t = new Tree();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
t.add(st.nextToken(), st.nextToken(), st.nextToken());
}
t.preorder(t.root);
System.out.println();
t.inorder(t.root);
System.out.println();
t.postorder(t.root);
System.out.println();
}
static class Node {
String data;
Node left;
Node right;
Node(String data) {
this.data = data;
}
}
static class Tree {
Node root;
public void add(String data, String leftData, String rightData) {
if (root == null) {
if (!data.equals(".")) {
root = new Node(data);
}
if (!leftData.equals(".")) {
root.left = new Node(leftData);
}
if (!rightData.equals(".")) {
root.right = new Node(rightData);
}
} else {
search(root, data, leftData, rightData);
}
}
private void search(Node root, String data, String leftData, String rightData) {
if (root == null) {
return; // 탐색실패시
} else if (root.data.equals(data)) {
if (!leftData.equals(".")) {
root.left = new Node(leftData);
}
if (!rightData.equals(".")) {
root.right = new Node(rightData);
}
} else {
search(root.left, data, leftData, rightData);
search(root.right, data, leftData, rightData);
}
}
public void preorder(Node root) {
System.out.print(root.data);
if (root.left != null) {
preorder(root.left);
}
if (root.right != null) {
preorder(root.right);
}
}
public void inorder(Node root) {
if (root.left != null) {
inorder(root.left);
}
System.out.print(root.data);
if (root.right != null) {
inorder(root.right);
}
}
public void postorder(Node root) {
if (root.left != null) {
postorder(root.left);
}
if (root.right != null) {
postorder(root.right);
}
System.out.print(root.data);
}
}
private static int stoi(String s) {
return Integer.parseInt(s);
}
}
트리문제의 pre, in, post를 결정짓는 부분은
public void order(Node root) {
//System.out.print(preorder);
if (root.left != null) {
order(root.left);
}
//System.out.print(inorder);
if (root.right != null) {
order(root.right);
}
//System.out.print(postorder);
}
이 차이이다.
유니온파인드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
* 유니온 파인드
*
*/
public class BOJ_1717_집합의표현 {
static int N, M;
static int[] map;
static int[] rank;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = stoi(st.nextToken());
M = stoi(st.nextToken());
map = new int[N + 1];
rank = new int[N + 1];
for (int i = 1; i <= N; i++) {
map[i] = i;
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int cal = stoi(st.nextToken());
int u = stoi(st.nextToken());
int v = stoi(st.nextToken());
if (cal == 0) {
union(u, v);
} else {
if (find(u) == find(v)) {
sb.append("YES\n");
} else {
sb.append("NO\n");
}
}
}
System.out.println(sb);
}
private static int find(int u) {
return map[u] = map[u] == u ? u : find(map[u]);
}
private static void union(int u, int v) {
u = find(u);
v = find(v);
if (u == v) {
return;
}
if (rank[u] > rank[v]) {
map[v] = map[u];
} else {
if (rank[u] == rank[v]) {
rank[v]++;
}
map[u] = map[v];
}
}
private static int stoi(String s) {
return Integer.parseInt(s);
}
}
이 두 메서드만 기억해두자. 유니온쪽에 혼란이 생기는 경우가 많은데,
- 유니온 파인드의 처음에 map 배열을 자기 자신으로 초기화해두고,
- 아래와 같이 메서드 구현하면 끝
private static int find(int u) {
return map[u] = map[u] == u ? u : find(map[u]);
}
private static void union(int u, int v) {
u = find(u);
v = find(v);
if (u != v) {
map[v] = u;
}
}
다익스트라
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.StringTokenizer;
/*
* 인접리스트로 pQ 사용하여 다익스트라.
* 이렇게 사용하는 경우 시간 복잡도 O(V*E)
* 인접행렬로 사용하는 경우엔 O(V^2)
*/
public class BOJ_1753_최단경로 {
static int N, M;
static List<Edge>[] graph;
static int[] res;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = stoi(st.nextToken());
M = stoi(st.nextToken());
graph = new ArrayList[N + 1];
res = new int[N + 1];
Arrays.fill(res, Integer.MAX_VALUE);
for (int i = 1; i <= N; i++) {
graph[i] = new ArrayList<Edge>();
}
int k = stoi(br.readLine());
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
graph[stoi(st.nextToken())].add(new Edge(stoi(st.nextToken()), stoi(st.nextToken())));
}
dijk(k);
for (int i = 1; i < res.length; i++) {
if (res[i] == Integer.MAX_VALUE) {
sb.append("INF\n");
} else {
sb.append(res[i]+"\n");
}
}
System.out.println(sb);
}
private static void dijk(int sv) {
PriorityQueue<Edge> pQ = new PriorityQueue<>();
Set<Integer> visit = new HashSet<>();
pQ.add(new Edge(sv, 0));
res[sv] = 0;
while (!pQ.isEmpty()) {
Edge e = pQ.poll();
if (visit.contains(e.v)) {
continue;
}
visit.add(e.v);
for (Edge tmpe : graph[e.v]) {
if (res[tmpe.v] > res[e.v] + tmpe.weight) {
res[tmpe.v] = res[e.v] + tmpe.weight;
pQ.add(new Edge(tmpe.v, res[tmpe.v]));
}
}
}
}
static class Edge implements Comparable<Edge> {
int v;
int weight;
Edge(int v, int weight) {
this.v = v;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return this.weight - o.weight;
}
}
private static int stoi(String s) {
return Integer.parseInt(s);
}
}
벨만포드
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Queue;import java.util.StringTokenizer;/* * V개의 노드가 있고 e개의 간선이 있다면, [V-1]번 e개의 간선에 대해 dist[]를 갱신해준다. * 그러고나서 1번 e개의 간선에 대해 dist[]를 갱신하려할때 갱신된다면 음의 사이클이 존재한다는 뜻.(영구히 갱신된다는 뜻) * 만약 dist의 값이 INF라면, 해당 경로가 없다는 것을 의미한다. * 출력초과나면 INF를 long으로 변경하자. * * 나쁜 민식선생님... * 1. 음의 사이클이 있는지 확인한다 * 2. 음의 사이클이 최종도착지를 포함하는지 bfs로 확인한다 * 포함한다면 Gee * 포함하지않는다면 정상출력 * 음의 사이클이 없다면 정상출력 * 애초에 최종 도착지에 도달을 못하면 gg */public class BOJ_1219_오민식의고민 { static int N, SC, EC, M; static long[] dist; static int[] income; static final long INF = (long) 1e18; static List<List<Edge>> line; static int[] map; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = stoi(st.nextToken()); SC = stoi(st.nextToken()); EC = stoi(st.nextToken()); M = stoi(st.nextToken()); dist = new long[N + 1]; Arrays.fill(dist, INF); line = new ArrayList<>(); for (int i = 0; i < N; i++) { line.add(new ArrayList<>()); } for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int start = stoi(st.nextToken()); int end = stoi(st.nextToken()); int weight = stoi(st.nextToken()); line.get(start).add(new Edge(end, weight)); } income = new int[N]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < N; i++) { income[i] = stoi(st.nextToken()) * -1; } String res = ""; if (!bfs(SC, EC)) { res = "gg"; } else { if (bellmanFord()) { res = "Gee"; } else { res = String.valueOf(dist[EC] * -1); } } System.out.println(res); } private static boolean bellmanFord() { dist[SC] = income[SC]; boolean update = false; for (int i = 0; i < N - 1; i++) { update = false; for (int j = 0; j < N; j++) { for (Edge e : line.get(j)) { if (dist[j] != INF && dist[e.e] > dist[j] + e.t + income[e.e]) { dist[e.e] = dist[j] + e.t + income[e.e]; update = true; } } } if (!update) { break; } } List<Integer> cycle = new ArrayList<>(); for (int i = 0; i < N; i++) { for (Edge e : line.get(i)) { if (dist[i] != INF && dist[e.e] > dist[i] + e.t + income[e.e]) { cycle.add(i); cycle.add(e.e); } } } for (int i : cycle) { if (bfs(i, EC)) { return true; } } // 사이클과 목적지가 관계가 없는 경우, dist배열을 초기화하고 벨만포드 알고리즘 한번 더 수행(싸이클을 이루는 노드는 제외한채로) Arrays.fill(dist, INF); dist[SC] = income[SC]; for (int i = 0; i < N - 1; i++) { update = false; for (int j = 0; j < N; j++) { for (Edge e : line.get(j)) { if (dist[j] != INF && dist[e.e] > dist[j] + e.t + income[e.e]) { dist[e.e] = dist[j] + e.t + income[e.e]; update = true; } } } if (!update) { break; } } return false; } private static boolean bfs(int start, int end) { if (start == end) { return true; } Queue<Integer> que = new ArrayDeque<>(); boolean[] visit = new boolean[N]; visit[start] = true; que.offer(start); while (!que.isEmpty()) { int cur = que.poll(); for (Edge e : line.get(cur)) { if (!visit[e.e]) { if (e.e == end) { return true; } visit[e.e] = true; que.offer(e.e); } } } return false; } static class Edge { int e; int t; Edge(int e, int t) { this.e = e; this.t = t; } } private static int stoi(String s) { return Integer.parseInt(s); }}
플로이드-워셜
포문을 세번 도는데,
- 가장 바깥 포문이 경유지
- 두번째가 출발지
- 세번째가 목적지
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class BOJ_11404_플로이드 { static int N, M; static int[][] map; static final int INF = (int)1e9; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = stoi(br.readLine()); M = stoi(br.readLine()); StringTokenizer st; map = new int[N + 1][N + 1]; for (int i = 1; i <= N; i++) { Arrays.fill(map[i], INF); } for (int i = 1; i <= N; i++) { map[i][i] = 0; } for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int s = stoi(st.nextToken()); int e = stoi(st.nextToken()); int w = stoi(st.nextToken()); if (map[s][e] > w) { map[s][e] = w; } } floydWarshall(); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { System.out.print(map[i][j] == INF ? 0 + " " : map[i][j] + " "); } System.out.println(); } } private static void floydWarshall() { // 가장 바깥 포문이 중간경유지 for (int k = 1; k <= N; k++) { for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]); } } } } private static int stoi(String s) { return Integer.parseInt(s); }}
KMP 알고리즘
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;public class BOJ_1786_찾기 { static String str; static String pattern; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuffer sb = new StringBuffer(); str = br.readLine(); pattern = br.readLine(); ArrayList<Integer> res = KMP(); System.out.println(res.size()); for (int i : res) { System.out.print(i + 1 + " "); } } private static ArrayList<Integer> KMP() { int[] pi = getPi(); ArrayList<Integer> res = new ArrayList<Integer>(); int j = 0; for (int i = 0; i < str.length(); i++) { while (j > 0 && str.charAt(i) != pattern.charAt(j)) { j = pi[j - 1]; } if (str.charAt(i) == pattern.charAt(j)) { if (j == pattern.length() - 1) { res.add(i - (pattern.length() - 1)); j = pi[j]; } else { j++; } } } return res; } private static int[] getPi() { int[] pi = new int[pattern.length()]; int j = 0; for (int i = 1; i < pattern.length(); i++) { while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) { j = pi[j - 1]; } if (pattern.charAt(i) == pattern.charAt(j)) { pi[i] = ++j; } } return pi; } private static int stoi(String s) { return Integer.parseInt(s); }}
트라이(Trie)
import java.util.*;public class 가사검색 { public static void main(String[] args) { System.out.println(solution(new String[] { "frodo", "front", "frost", "frozen", "frame", "kakao" }, new String[] { "fro??", "????o", "fr???", "fro???", "pro?" })); } public static int[] solution(String[] words, String[] queries) { Trie[] tries = new Trie[100001]; for (String word : words) { int len = word.length(); if (tries[len] == null) tries[len] = new Trie(); tries[len].insert(word); } int[] answer = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int len = queries[i].length(); if (tries[len] == null) answer[i] = 0; else answer[i] = tries[len].getCount(queries[i]); } return answer; } static class Trie { Node front; Node back; Trie() { this.front = new Node(); this.back = new Node(); } public void insert(String word) { insertFront(word); insertBack(word); } private void insertFront(String word) { Node node = front; for (int i = 0; i < word.length(); i++) { node.count++; node = node.children.computeIfAbsent(word.charAt(i), c -> new Node()); } } private void insertBack(String word) { Node node = back; for (int i = word.length() - 1; i >= 0; i--) { node.count++; node = node.children.computeIfAbsent(word.charAt(i), c -> new Node()); } } public int getCount(String query) { if (query.charAt(0) == '?') return getCountFromBack(query); else return getCountFromFront(query); } private int getCountFromFront(String query) { Node node = front; for (int i = 0; i < query.length(); i++) { if (query.charAt(i) == '?') { break; } if (!node.children.containsKey(query.charAt(i))) { return 0; } node = node.children.get(query.charAt(i)); } return node.count; } private int getCountFromBack(String query) { Node node = back; for (int i = query.length() - 1; i >= 0; i--) { if (query.charAt(i) == '?') { break; } if (!node.children.containsKey(query.charAt(i))) { return 0; } node = node.children.get(query.charAt(i)); } return node.count; } } static class Node { Map<Character, Node> children; int count; Node() { this.children = new HashMap<>(); this.count = 0; } }}