자바 알고리즘 구현 코드

 

 

 - 에라토스테네스의 체

public ArrayList<Integer> eratos(int n) {
    ArrayList<Integer> result = new ArrayList<>();
    ArrayList<Boolean> check = new ArrayList<>();
    for (int i = 0; i <= n; i++) {
        check.add(true);
    }

    for (int i = 2; i <= n; i++) {
        if (!check.get(i)) continue;
        result.add(i);
        for (int j = i * 2; j <= n; j += i) {
            check.set(j, false);
        }
    }
    return result;
}

 

 

 - GCD 구하기(유클리드 호제법)

public int getGCD(int a, int b) {
    while (b > 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

 

 

 -  LCM 구하기

public int getLCM(int a, int b) {
    return a / getGCD(a, b) * b;
}

 

 

 - Permutation

public void permutation(int[] arr, int depth, int n, int r, boolean[] visited, int[] out) {
    if (depth == r) {
        System.out.println(Arrays.toString(out));
        return;
    }

    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        out[depth] = arr[i];
        permutation(arr, depth + 1, n, r, visited, out);
        visited[i] = false;
    }
}

 

 

 - Combination

void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
    if (r == 0) {
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
        return;
    }

    if (depth == n) return;

    visited[depth] = true;
    combination(arr, visited, depth + 1, n, r - 1);

    visited[depth] = false;
    combination(arr, visited, depth + 1, n, r);
}

 

 

 - sqrt(바빌로니아 법)

static double sqrt(int n) {
    double result = 1;
    for (int i = 0; i < 10; i++) {
        result = (result + (n / result)) / 2;
    }
    return result;
}

 

 - BFS

import java.io.*;
import java.util.*;

public class Main {
    public static class Pair {
        int x;
        int cnt;

        Pair(int x, int cnt) {
            this.x = x;
            this.cnt = cnt;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int max = (int) 2e6 + 1;
        int[] visited = new int[max];
        Arrays.fill(visited, -1);

        Queue<Pair> q = new LinkedList<>();
        visited[n] = 0;
        q.add(new Pair(n, 0));

        while (!q.isEmpty()) {
            Pair cur = q.remove();
            if (cur.x == k) break;

            int[] nexts = new int[]{2 * cur.x, cur.x + 1, cur.x - 1};
            for (int i = 0; i < nexts.length; i++) {
                int next = nexts[i];
                if (next >= 0 && next < max && visited[next] == -1) {
                    visited[next] = cur.cnt + 1;
                    q.add(new Pair(next, cur.cnt + 1));
                }
            }
        }
        bw.write(visited[k] + "\n");

        bw.flush();
        bw.close();
    }
}

 

- Trie

class Node {
    HashMap<Character, Node> child;
    boolean isTerminal;

    public Node() {
        this.child = new HashMap<>();
        this.isTerminal = false;
    }
}

class Trie {
    Node root;

    public Trie() {
        this.root = new Node();
    }

    public void insert(String str) {
        Node cur = this.root;

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            cur.child.putIfAbsent(c, new Node());
            cur = cur.child.get(c);

            if (i == str.length() - 1) {
                cur.isTerminal = true;
            }
        }
        return;
    }

    public boolean search(String str) {
        Node cur = this.root;

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            if (cur.child.containsKey(c)) cur = cur.child.get(c);
            else return false;

            if (i == str.length() - 1 && !cur.isTerminal) {
                return false;
            }
        }
        return true;
    }

    public void delete(String str) {
        boolean ret = this.delete(this.root, str, 0);
        if (ret) System.out.println(str + " 삭제 완료");
        else System.out.println(str + " 단어가 없습니다");
    }

    public boolean delete(Node node, String str, int idx) {
        char c = str.charAt(idx);

        if (!node.child.containsKey(c)) return false;

        Node cur = node.child.get(c);
        idx++;

        if (idx == str.length()) {
            if (!cur.isTerminal) return false;
            cur.isTerminal = false;

            if (cur.child.isEmpty()) {
                node.child.remove(c);
            }
        } else {
            if (!this.delete(cur, str, idx)) {
                return false;
            }

            if (!cur.isTerminal && cur.child.isEmpty()) {
                node.child.remove(c);
            }
        }
        return true;
    }
}

 

 

- 플로이드 워셜