민팽로그

Bubble Sort - 인접한 원소를 하나하나 비교하여 가장 큰 수를 찾아 맨 끝으로 보내면서 정렬하는 알고리즘 - n^2의 시간 복잡도를 갖음. for문을 돌며 (n - 1) * (n - 2) * ... * 2 * 1 번 연산하게 됨 - 시간 복잡도를 생각했을 때 속도가 느려 효율성은 떨어지지만 알고리즘이 단순하여 빠르고 간단하게 구현할 수 있음 예제 코드(Java) public class Test { public static void main(String[] args) { int [] a = new int[10]; for(int i = 0; i < a.length; i++) { System.out.print(a[i] = (int) (Math.random() * 10)); } //for(int i =..

그리디 알고리즘(탐욕법) 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. - 위키백과 즉, 그리디 알고리즘은 각 단계마다 당장에 최적인 방법을 선택해 나가는 것이고, 그 과정을 통해 전체적인 최적의 답에 이르게 되는 알고리즘이다. 주어진 문제를 그리디 방식으로 풀기에 적절한지 판단하기 위해서는 '최적 부분 구조..

분할 정복 알고리즘(Divide and conquer algorithm) 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘으로, 보통 재귀 함수를 통해 자연스럽게 구현된다. 주어진 문제를 둘 이상의 부분 문제로 나누어 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다. function F(x): if F(x)의 문제가 간단 then: return F(x)을 직접 계산한 값 else: x 를 y1, y2로 분할 F(y1)과 F(y2)를 호출 return F(y1), F(y2)로부터 F(x)를 구한 값 주어진 문제를 둘 이상의 부분 문제로 나누어 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으..