전체 글
-
팩토리얼 / 순열 / 조합Algorithm\자료구조 2021. 9. 6. 10:45
1. 팩토리얼 - ! - 서로 다른 n개를 나열하는 경우의 수 - ex : 3! = 3 * 2 * 1 2. 순열 (Permutation) - nPr = n! / (n - r)! - 서로 다른 n개중에 r개를 선택하는 경우의 수 (순서 O) 3. 조합 (Combination) - nCr = n! / ( (n-r)! r! ) - 서로 다른 n개중에 r개를 선택하는 경우의 수 (순서 X) 출처 : https://coding-factory.tistory.com/606
-
최대공약수와 최소공배수 (+ 소수)Algorithm\자료구조 2021. 9. 4. 09:37
1. 최대공약수 (Greatest Common Divisor) - 나눈 값이 0보다 클때까지 반복 (유클리드 호제법 사용) - 알고리즘 예시 : public static int gcd(int a, int b) { if(b == 0) return a; else { int tmp = b; b = a % b; a = tmp; return gcd(a, b); } } 2. 최소공배수 (Least Common Multiple) - 최대공약수와의 관계를 이용해서 구함 - 알고리즘 예시 : public static int lcm(int a, int b) { return ((a * b) / gcd(a, b)); } 3. 소수 (Prime Number) - "1과 그수 자신 이외의 자연수로는 나눌 수 없는, 1보다 큰자연..
-
[Java] Deque 덱 / 데크 사용법Spring\Java 2021. 8. 30. 14:05
Deque (Double-ended Queue) : 큐의 양쪽으로 삽입/삭제 가능 - Scroll : 한쪽으로만 입력 가능 - Shelf : 한쪽으로만 출력 가능 1. 선언 Deque dq = new ArrayDeque(); 2. 삽입 dq.addFirst(1); // 앞에 삽입 -> 용량 초과시 예외 발생 dq.offerFirst(1); // 정상 처리 true, 실패 false dq.addLast(1); dq.offerLast(1); dq.add(1); // addLast()와 동일 dq.push(1); // addFirst()와 동일 ------------------------------------------------------- dq.addAll(Collection
-
[Java] StringBuilder 사용법Spring\Java 2021. 8. 24. 14:56
- 자바에서 String + String 연산은 새로운 String을 생성하게 됨 -> 잦은 연산은 성능적으로 X - StringBuilder는 새로운 객체 생성 X, 기존 데이터에 더해짐 -> 속도 굿 - 또한 String은 immutable -> 변경 불가임 1. 선언 StringBuilder sb = new StringBuilder(); 2. 더하기 sb.append("add"); // 젤 뒤에 값 더하기 sb.insert(index, value); // 특정 위치에 더하기 3. 삭제 sb.delete(index, index); // index to index 삭제 4. 출력 System.out.println(sb.toString()); 5. 그 외 sb.indexOf(value); // 값의 인덱..
-
그래프의 이해와 종료 (+추가 예정)Algorithm\자료구조 2021. 8. 23. 16:00
그래프 알고리즘 : 출발지와 목적지를 정하고 그에 맞는 최적의 경로를 찾는 방법 - 수학자 '오일러'에 의해 고안되었음 (쾨니히스베르크의 다리) "정점 별로 연결된 간선의 수가 모두 짝수이어야, 한번씩만 지나서 처음 출발했던 정점으로 도착" 정점 (vertex) : 연결의 대상이 되는 개체 또는 위치 간점 (edge) : 이들 사이의 연결을 의미 - 무방향 그래프 (undirected) : 방향성이 없는 그래프 - 방향 그래프 (directed, digraph) : 간선에 방향 정보가 포함된 그래프 - 완전 그래프 : 각각의 정점에서 다른 모든 정점을 연결한 그래프 무방향 그래프와 방향 그래프는 간선의 연결 형태의 따라 구분됨 방향 그래프의 간선의 수는 무방향 그래프의 간선선의 수에 두 배 (쌍방 가능해..
-
[Java] Queue 큐Spring\Java 2021. 8. 23. 15:04
Queue란? - 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO 형태를 가짐 - 컴퓨터 버퍼에서 주로 사용 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼를 만들어 대기 시킴 - Enqueue : 큐 맨 뒤에 데이터 추가 - Dequeue : 큐 맨 앞쪽의 데이터 삭제 1. 선언 - 자바에서 큐는 LinkedList를 사용 -> LinkedList 와 Queue 선언 필요 import java.util.LinkedList; import java.util.Queue; Queue queue = new LinkestList(); Queue queue = new LinkestList(); 2. 값 추가 - add의 경우 성공시 true 반환, 실패시 IllegalStateExceptio..
-
[Java] LinkedList 사용법Spring\Java 2021. 8. 23. 13:18
Iterator iter = list.iterator(); while(iter.hasNext()) { System.out.println(iter.next); } 1. 선언 LinkedList list = new LinkedList(); // 타입 미설정 LinkedList num = new LinkedList(); // int 타입만 사용 가능 -> new LinkedList(); // 타입 파라미터 생략 가능 LinkedList list = new LinkedList(Arrays.asList(1,2)); // 생성시 값 추가 2. 값 추가 list.addFirst(); // 가장 앞에 추가 list.addLast(); // 가장 뒤에 추가 list.add(); 데이터 추가 list.add(1, 10);..
-
너비 우선 탐색 (Breadth First Search, BFS)Algorithm\자료구조 2021. 8. 23. 11:24
너비 우선 탐색 (Breath First Search, BFS)는? - 탐색시 너비를 우선으로 탐색을 수행하는 탐색 알고리즘 - 맹목적인 탐색을 하고자 할 때 사용 - 최단 경로를 찾아줌 -> 최단 길이를 보장해야 할 때 사용 - 자신에게 연결된 모든 사람에게 연락을 취하는 방식 - 특징 : 1부터(시작점으로부터) 가까운 노드들부터 탐색이 이루어짐 그래프 탐색일 경우 방문 여부 검사 필수 재귀적 동작 X FIFO (선입선출) 큐를 이용해서 반복적 형태로 구현하는 것이 일반적 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int star..