Algorithm\자료구조
-
팩토리얼 / 순열 / 조합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보다 큰자연..
-
그래프의 이해와 종료 (+추가 예정)Algorithm\자료구조 2021. 8. 23. 16:00
그래프 알고리즘 : 출발지와 목적지를 정하고 그에 맞는 최적의 경로를 찾는 방법 - 수학자 '오일러'에 의해 고안되었음 (쾨니히스베르크의 다리) "정점 별로 연결된 간선의 수가 모두 짝수이어야, 한번씩만 지나서 처음 출발했던 정점으로 도착" 정점 (vertex) : 연결의 대상이 되는 개체 또는 위치 간점 (edge) : 이들 사이의 연결을 의미 - 무방향 그래프 (undirected) : 방향성이 없는 그래프 - 방향 그래프 (directed, digraph) : 간선에 방향 정보가 포함된 그래프 - 완전 그래프 : 각각의 정점에서 다른 모든 정점을 연결한 그래프 무방향 그래프와 방향 그래프는 간선의 연결 형태의 따라 구분됨 방향 그래프의 간선의 수는 무방향 그래프의 간선선의 수에 두 배 (쌍방 가능해..
-
너비 우선 탐색 (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..