notepad by Oxix

다이나믹 프로그래밍? 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다. 연산 속도에 한계가 있고, 메모리 공간을 최대한 활용 할 수 있는 효율적인 알고리즘을 작성해야 한다. 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가 시킬 수 있는 방법이 있는데 해당 방법 중에 하나가 다이나믹 프로그래밍이다. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열을 해석하면 다음과 같다. n번째 피보나치 수 = ( n - 1 )번째 피보나치 수 + ( n - 2 )번째 피보나치 수 단, 1번째 피보나치 수 = 1 , 2번째 피보나치 수 = 1 public int fibo(int x){ i..

순차 탐색 N개의 데이터가 있을 때, 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 찾을 수 있는 장점이 있다. 코드로 작성하면 다음과 같다. public class 순차탐색 { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5}; int value = 3; boolean isTrue = sequentialSearch(arr, value); System.out.println(isTrue); } private static boolean sequentialSearch(int[] arr, int value) { for (int ..

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 의미한다. 데이터를 가공할 때 내림차순, 오름차순으로 정렬해서 사용하는 경우가 많기에 프로그램을 작성할 때 가장 많이 사용되는 알고리줌 중 하나이다. 정렬 알고리즘은 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬 등이 있다. 정렬을 공부하면 알고리즘의 효율성을 쉽게 이해할 수 있고 적절한 정렬 알고리즘이 공식처럼 사용된다. 선택 정렬 데이터가 무작위로 여러 개 있는 경우 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복한다. 이 방법은 가장 원시적인 방법으로 매번 가장 작은 것을 선택하는 의미에서 선택 정렬 알고리즘이라고 한다. void selecti..