Algorithm/알고리즘 설명14 [알고리즘] 위상 정렬 (Topological Sorting) 위상 정렬 (Topological Sorting) 사이클이 없는 유향 그래프의 모든 정점을 정렬하는 알고리즘 간선 (i, j) 가 존재하면 정점 i는 반드시 정점 j보다 앞에 위치해야한다. → 사이클이 있으면 이 성질을 만족할 수 없다. 시간 복잡도 : O(V+E) 알고리즘 각 노드마다의 진입 간선을 보관하는 배열 in_edge 생성 맨 처음, 진입 간선이 없는 노드들을 queue에 추가 queue가 빌 때까지 반복문 실행 현재 노드 now 출력 now에 연결된 진출 노드들 탐색 진출 노드 next의 진입 간선 줄이기 next의 진입 간선이 0이면 next 앞에 있는 노드들이 모두 출력되었다는 의미이므로 next를 queue에 추가 import java.util.*; public class Main { .. 2020. 9. 17. [알고리즘] 이분 탐색 (Binary Search) 이분 탐색 (Binary Search) O( log N )의 시간 복잡도로 전체 배열에서 특정 값을 찾아내는 방법 이 때 배열은 무조건 정렬이 되어있어야함 반복문 실행할 때마다 탐색 범위를 왼쪽 절반 혹은 오른쪽 절반으로 줄여 나감 응용 최대값, 혹은 최소값을 찾는 문제 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 알고리즘 left = index 최소 값 right = index 최대 값 반복문 실행 left가 right 보다 이하일 동안 반복 (left m.. 2020. 8. 31. [알고리즘] 최대공약수, 최소공배수 구하기 import java.util.*; public class Main { public static void main(String[] args) { int a = 8; int b = 6; //최대공약수 (유클리드호제법) System.out.println("최대공약수 : "+gcd(a,b)); //최소공배수 = 0이 아닌 두 수의 곱 / 최대공약수 System.out.println("최소공배수 : "+ (a * b) / gcd(a,b)); } //최대공약수 public static int gcd(int a, int b) { //a에 큰 값 위치 시킴 if(a < b) { int temp = a; a = b; b = temp; } //유클리드 호제법 while(b != 0) { int n = a % b; a =.. 2020. 8. 22. [알고리즘] 각 자리 수의 합 구하기 import java.util.*; public class Main { public static void main(String[] args) { int num = 1234567; int result = 0; //num : 1234567 -> 123456 -> 12345 -> 1234 -> 123 -> 12 -> 1 while(num >= 10) { result += num % 10; num /= 10; } result += num; System.out.println(result); } num을 10으로 나눈 나머지 값을 결과값에 더한다. num을 10으로 나눈 몫을 새로운 num으로 대입한다. 결과적으로 1의 자리 수 -> 10의 자리 수 -> 100의 자리 수 .... 순서대로 수를 더하게 된다. 2020. 8. 22. 이전 1 2 3 4 다음
