른록노트

1. 재귀 알고리즘 재귀 알고리즘의 바탕이 되는 기본 개념은 '어떤 문제를 해결하기 위해 문제의 범위보다 좁은 하위 문제를 해결하고, 그 하위 문제의 해답을 이용하여 원래 문제를 해결한다.' 이다. 재귀 함수는 자기 자신을 참조하는 함수이다. 원래의 문제를 동일한 유형의 하위 문제로 나누고 하위문제를 해결한 다음 결과와 결합한다. 이러한 알고리즘을 분할 정복법 이라 한다. 또 하위 결과를 저장하여 조회하는 알고리즘이 추가되면 동적프로그래밍이라고 부른다. 이러한 재귀 함수는 다음과 같은 구조를 가져야 한다. Base Case : 재귀함수의 종료 조건으로 더 이상 문제를 쪼갤수 없을 때, 자기자신을 호출하지 않고 답이 나올 때 Recusion Case: 복잡한 입력을 더 간단한 입력으로 분류하..

에라토스테네스의 체 에라토스테네스의 체는 에라토스테네스가 고안했다고 여겨지는 소수 판정 방법으로, 자연수를 순서대로 늘어놓은 표에서 소수는 남겨두고 소수의 배수(합성수)를 지워나가면서 소수 목록을 얻는 것을 말한다. (소수의 개수) 소수를 판별하는 세가지 방법 소수는 영어로하면 Prime Number이다. 우리는 Java로 파라미터로 받은 정수가 소수인지 함수인지 판단하는 함수를 만들어 볼 것 이다. 1. 임의의 수 i를 사용하여 n-1 까지 반복하면서 증가하는 수로 n을 나눴을 때 나머지가 0인지 확인하는 방법 (간단한 방법) public boolean checkPrimeNumber(int n){ boolean result = true; if( n < 2 ){ result = false; }else i..

크러스컬 알고리즘 크루스컬 알고리즘(Kruskal’s algorithm)은 최소 비용 신장 트리를 찾는 알고리즘 입니다. 변의 개수를 E라고 하고 꼭지점의 개수를 V라고 하면 O(ELogV)의 시간복잡도를 가진 알고리즘 입니다. 최소 비용 신장 트리(minimum spanning tree, MST)란 신장 트리는 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프입니다. 한 곳으로 도달하는 경우가 두 개 이상 존재하는 경우, 즉 사이클이 존재하는 경우에는 최소한의 연결이라 말할 수 없기 때문에, 모든 위치 하나에서 다른 곳으로 이동하는 경우는 단 한 가지로 결정되도록 항상 트리의 형태를 나타냅니다. 최소 비용 신장 트리는 이러한 신장 트리들 중 간선의 가중치 합이 가장 작은 트리입니다. 개요 크러..

이전글참고 피보나치 수열이란? 1. 팩토리얼이란? 1 * 2 * 3 * 4 * 5 * 6, ... 팩토리얼은 다음과 같이 정의됩니다. f(n) = 1 * 2 * 3 * ... n 5! = 1 * 2 * 3 * 4 * 5 = 120 2. Java로 팩토리얼을 구현해보세요 1) 첫번째 방법은 재귀로 구현해보겠습니다. public class Main { public static int count = 0; public static void main(String args[]) { int n = 5; System.out.println(factorial(n)); System.out.println("메서드 실행 횟수:"+count); } public static int factorial(int n) { count++;..

참고사이트 오명운님 블로그 1. 피보나치 수열이란? &#39;0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...` 피보나치 수열은 다음과 같이 정의됩니다. f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2); 2. Java로 피보나치 수열을 구현해보세요 1) 먼저 첫번째 방법은 간단하게 재귀로 구현할 수 있습니다. public class Main { public static int count = 0; public static void main(String args[]) { int n = 10; System.out.println(fibonacci(n)); System.out.println("메소드 실행횟수:" + count); } public static int fibo..