알고리즘5 [알고리즘] 효율적인 알고리즘 ㅁ 계산량 문제에 맞추어 효율적인 알고리즘을 생각할 때 중요한 것은 계산량 계산량 측정 4중 루프가 n번 돌기 때문에 실행시간은 n 4승 에 비례 합니다. 그리고 n 4승 비례한다는 것은 O(n4스) 이라고 쓰고, 실행시간 [O(n4승)]이라고 씁니다. - 이것은 런다우 기법(Landau notation) 또는 O-기법이라고 한다. ㅁ 실행시간 - 알고리즘에 따른 계산량 만으로도 프로그램의 속도 차이가 수십배 나는 경우도 있다. 프로그램의 실행시간을 짧게 하기 위해서는 우선 알고리즘 계산량이 중요하다는 뜻. ㅁ 알고리즘에 제한시간 안에 실행 가능한지 판단하기 위해서는 계산량 오더 식에 최대치를 대입 예 : O(n4승)시간 알고리즘 일때 (n 2022. 8. 15. [알고리즘] 알고리즘 디자인 기법 1. 구현 기법에 의한 분류 1) 재귀 혹은 반복 재귀 알고리즘은 기본 조건이 충족될 때까지 자신을 반복 호출. C, C++에서 일반적으로 사용 반복 알고리즘은 기본적으로 루프 같은 구조로 스택이나 큐 등에 데이터 구조를 사용하여 문제 해결 어떤 문제들은 재귀에 적합하고 다른 문제들은 반복에 적합하다. 모든 재귀 알고리즘은 반복 알고리즘으로 변환 또는 반대로 가능하다. 2) 절차적 또는 선언적 선언형 프로그래밍 언어에서는 무엇을 할 것인지를 정의하는 방식을 이용한다. 절차적 프로그래밍에서는 결과를 얻기 위한 정확한 단계를 명시해야 한다. SQL은 절차적이라기보다 선언적이다. 절차적 언어는 C, PHP, PERL 등 3) 직렬 또는 병렬 또는 분산 컴퓨터가 한 번에 한 명령을 수행한다고 가정하는데, 이를 .. 2022. 8. 15. [알고리즘] 백트랙킹 (Java) n비트의 모든 문자열을 생성하라. A[0..n-1]는 크기 n인 배열이라고 가정하라. public class nBitGenerator { public static void main(String[] args) { // TODO Auto-generated method stub Integer[] A = {0,1,2,3,4,5}; Binary(4, A); } public static void Binary(int n, Integer[] A) { if(n < 1) System.out.println(A[n]); else { A[n-1] = 0; Binary(n - 1, A); A[n-1] = 1; Binary(n - 1, A); } } } 2022. 8. 15. [알고리즘] 재귀함수 (예제:하노이 탑-Java) ㅁ 재귀함수 - 자기 자신을 호출하는 함수 - 자기 자신을 호출하여 더 작은 문제를 풀게 하여 문제를 해결하는 방법 - 중요한 것은 종료해야만 한다는 것 ㅁ 재귀 사용 목적 - 배귀는 반복 코드보다 짧고 작성하기 쉽다. - 일반적인 루프는 컴파일될 때 재귀함수로 바뀐다. - 비슷한 하위 작업으로 정리될 수 있는 작업에 특히 유용(예:정렬, 검색, 탐색) ㅁ 메모리 - 재귀 호출시마다 메서드는 복사본(실제는 변수만)이 메모리에 만들어진다 - 메서드가 종료될 때마다 복사본은 메모리에서 삭제된다. - 재귀 방법은 쉬워 보이지만 시각화와 추적에 시간이 걸린다.(코드를 읽기가 어렵다) ㅁ 재귀와 반복 - 일반적으로 재귀 방법은 접근이 어려운 문제를 쉽게 풀 수 있게 해 준다. - 매번 수행하는 재귀 호출에 부가적.. 2022. 8. 15. [알고리즘] 이진 검색 (Java) 참고 : Beautiful Code / 한빛미디어 이진검색 : 미리 정렬된 수들의 배열에서 대상 원소를 찾는 방법으로 간단하고 효과적인 방법이다. 그러나 까다로운 알고리즘이다. 프로그래머의 10% 정도만이 정확하게 구현했다고 한다. 이전검색이 발표된 것은 1946이었으나 버그 없는 코드는 12년 이상 걸렸다고 한다. 문제는 구현 언어가 고정 정밀도 산술을 채용하고 있으며 주어진 배열이 충분히 큰 상황에서는 문제를 노출한다는 것 Java에서는 ArrayIndexOutOfBoundsException예외가 발생한다. 아래 버그 코드에서 int mid = (low + high) /2; 가 문제. 합이 Integer.MAX_VALUE(Java에서는 2에 31승 - 1) 보다 큰 경우 위넘침에 의해 합이 음수가 됨.. 2022. 8. 15. 이전 1 다음 728x90 반응형