IT 기획의 길

큰 문제를 작은 문제로 나눠서 푸는 알고리즘은 1. 다이나믹 프로그래밍 2. 분할 정복 총 2가지가 있다. 큰 문제를 여러개의 작은 문제로 나누었을때 작은 문제가 문제끼리 중복이 가능한것이 DP이고 중복이 불가능한것이 분할정복기법이다. 그중에서 이번에는 다이나믹 프로그래밍에 대해서 공부해 보겠다. 작은 예시를 들어보겠다. 피보나치 수열이라고 많이 들어봤을것이다 0 1 1 2 3 5 8 13 21 34 55 와 같이 n번째 수는 n-1번째 수와 n-2번째 수의 합으로 이루어져 있는 수열을 피보나치 수열이라고 한다 우리는 보통 피보나치 수열 풀때 import java.util.*; public class Main { public static void main(String[] args){ System.out...

퀵정렬: 하나의 큰 문제를 두개의 작은 문제로 분할하는 식으로 빠르게 정렬하는 방법 -> 특정한 값 피벗(Pivot)을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다 EX) (3) 7 8 1 5 9 6 10 2 4 3을 피벗으로 지정 3보다 큰 숫자를 왼쪽에서 찾고 3보다 작은 숫자를 오른쪽부터 찾는다. 3보다 큰 수: 7 3보다 작은 수: 2 이때 큰값과 작은 값의 위치를 바꿔준다 (3) 2 8 1 5 9 6 10 7 4 3보다 큰 수: 8 3보다 작은 수: 1 (3) 2 1 8 5 9 6 10 7 4 3보다 큰 수: 8 3보다 작은 수: 1 이때 큰값의 인덱스와 작은값의 인덱스가 엇갈린다 이럴때는 피벗값(3)과 작은값(1)을 바꿔준다 1 2 (3) 8 5 9 6 10 7 4 ..

삽입정렬: 필요할때만 적절한 위치에 삽입하는 정렬 (앞의 요소들은 정렬이 되어있다고 가정한다) Java code import java.util.*; public class InsertionSort { public static void main(String[] args) { int i,j,temp; int []arr= {1,10,5,8,7,6,4,3,2,9}; for(i=0;iarr[i+1]) { //앞의 원소가 뒤의 원소보다 작을때 까지 while문 실행 temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=temp; i--; } } for(int k=0;k

버블정렬: 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내는 정렬 Java code import java.util.*; public class BubbleSort { public static void main(String[] args) { int i,j,temp; int []arr= {1,10,5,8,7,6,4,3,2,9}; for(i=0;i 이때 9개의 데이터를 탐색한다 .... 이런식으로 실행하면 버블정렬은 10+9+8+ ...+2+1=N(N*1)/2=O(N^2)의 시간복잡도를 갖는다 선택정렬같은 경우는 탐색을 다 마친후에 최솟값만 맨앞으로 가져오면 되지만 버블정렬은 배열의 현재 요소와 뒤의 요소를 비교할때마다 뒤의 요소가 더 작으면 현재 요소와 교체해야 된다(매우 비효율적) ->시간복잡도는 선택..