# 최대 공약수 & 최소 공배수 --> // 두 자연수의 곱 == 최대 공약수 * 최소 공배수 ## 약수 - 해당 수를 나눠서 나머지가 0이 되는 수 - ** 해당 수 /2 까지 나머지가 0인 수 + 해당 수 ** ## 최대 공약수 - 두 수의 약수 중 공통적으로 나오는 약수이면서 가장 큰 수 ## 최소 공배수 - 배수 중 공통적으로 배수면서 가장 작은 수 - 최소 공배수 == (a * b) / GCD(a, b) 나눠서 나머지가 발생하지 않는 수 public List getDivisor(int num) { List result = new ArrayList(); for (int i = 1; i
자료구조 & 알고리즘
# 경우의 수 ## 경우의 수 - 어떤 사건에서 일어날 수 있는 가짓수 - ex) 주사위를 던지는 사건의 경우의 수 = 6 - 사건 A가 일어날 경우의 수 = n(A) ## 합의 법칙 - 사건 A 또는 B가 일어날 경우의 수 - 사건 A와 사건 B의 합의 법칙 n(A U B) = n(A) + n(B) - n(A 교집합 B) ## 곱의 법칙 - 사건 A와 사건 B가 동시에 일어날 경우의 수 - n(A x B) = n(A) x n(B) public class Main { public static void main(String[] args) { // 1. 합의 법칙 System.out.println("== 합의 법칙 =="); // 두 개의 주사를 던졌을 때 합이 3 또는 4의 배수일 경우의 수 int[] d..
# Comparable 혹은 Comparator에서 ex) x, y -> x - y //오름차순 x, y -> y - x //내림차순 # 자바 우선순위큐 사용 예시 - 1. 기본 오름차순 정렬 - 2. 기본 내림차순 정렬 (reverse) - 3. Comparable 구현 정렬 - 4. Comparator 구현 정렬 - 5. 문자열(사전식) 정렬 // Comparable || Comparator 사용... class Person implements Comparable { String name; int age; public Person(String name, int age) { this.name = name; this.age = age; } @Override public int compareTo(Perso..
# 힙(heap) - 완전이진트리 형태 -> 데이터의 연속성이 보장되서 배열(혹은 배열의 일종인 어레이 리스트)로 트리 작성하기 용이함 - 중복값 허용 - 반 정렬 상태 (형제 노드들 간의 정렬 X - 부모 노드와 자식 노드 같의 정렬만 O) - 최소값 혹은 최대값을 빠르게 찾아내기 유용한 자료구조 // ArrayList 로 최소 힙 구현 import java.util.ArrayList; class MinHeap { ArrayList heap; public MinHeap() { this.heap = new ArrayList(); this.heap.add(0); // 더미데이터삽입 -> 인덱스 기준으로 1번부터 사용하기 위함 !! } public void printTree() { for (int i = 1..
// 인접 리스트 그래프의 DFS, BFS class GraphList2 extends GraphList { public GraphList2(int size) { super(size); } public void dfs(int idx) { // && DFS는 배열&스택(인접 정점들을 스택에 넣는다.) boolean[] visited = new boolean[this.vertices.length]; Stack stk = new Stack(); stk.push(idx); visited[idx] = true; while (!stk.isEmpty()) { // 노드 정보 & 간선 정보 분리되어있다는 것 주의 int i = stk.pop(); System.out.print(vertices[i] + " "); //n..
class GraphMatrix2 extends GraphMatrix { public GraphMatrix2(int size) { super(size); } public void dfs(int idx) { // DFS는 배열&스택(인접 정점들을 스택에 넣는다.) boolean[] visited = new boolean[this.vertices.length]; Stack stk = new Stack(); stk.push(idx); visited[idx] = true; while (!stk.isEmpty()) { int i = stk.pop(); System.out.print(vertices[i] + " -> "); for (int j = matrix[i].length - 1; j >= 0; j--) { /..
// 인접 리스트를 이용한 그래프 구현 class Node { int id; // 노드가 id 들고 있음 주의 -> 추후 dfs,bfs 시 방문배열체크용 ! Node next; public Node(int id, Node next) { this.id = id; this.next = next; } } class MyGraphList { char[] vertices; Node[] nodeList; int idx; public MyGraphList(int size) { this.vertices = new char[size]; nodeList = new Node[size]; idx = 0; } public void addVertex(char c) { if (idx == this.vertices.length) {..
class GraphMatrix { char[] vertices; // 노드 int[][] matrix; // 인접 행렬 int idx; public GraphMatrix(int size) { this.vertices = new char[size]; this.matrix = new int[size][size]; this.idx = 0; } public boolean isFull(){ return this.vertices.length == idx; } public void addVertex(char c) { if(isFull()){ System.out.println("Graph is full"); return; } this.vertices[this.idx++] = c; } public void addEdg..
// AVL 트리 import java.util.LinkedList; import java.util.Queue; class Node { int key; int height; Node left; Node right; public Node(int key, Node left, Node right) { this.key = key; this.height = 0; this.left = left; this.right = right; } } class AVLTree { Node head; public int height(Node node) { // 노드가 null일 때 높이는 -1 if (node == null) { return -1; } return node.height; } // LL 케이스 public Node ..
class Node2 { int data; Node2 left; Node2 right; public Node2(int data, Node2 left, Node2 right) { this.data = data; this.left = left; this.right = right; } } class BinarySearchTree2 { Node2 head; public BinarySearchTree2(int data) { this.head = new Node2(data, null, null); } public Node2 addNodeRecursive(Node2 cur, int data) { if (cur == null) { return new Node2(data, null, null); } if (data < ..
