study-knou/알고리즘 (11) 썸네일형 리스트형 3. 분할정복 알고리즘 분할정복 방법의 원리 - 순환적으로 문제를 푸는 하향식 접근 방법 - 주어진 문제의 입력을 더 이상 나룰 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식 - 특징 - 분할된 작은 문제는 원래 문제와 동일 -> 단, 입력 크기만 작아짐 - 분할된 문제는 서로 독립적 -> 순환적 분할 및 결과 결합이 가능 - 각 순환 호출 시의 처리 과정 - 분할 : 주어진 문제를 여러 개의 작은 문제로 붑ㄴ할 - 정복 : 작은 문제들을 순환적으로 분할, 만약 작은 문제가 더 이상 분할되지 않을 정도로 크기가 충분히 작다면 순환 호출 없이 작은 문제에 대한 해를 구함 - 결합 : 작은 문제에 대해 정복된 해를 결합하.. 알고리즘 소개2 - 최댓값 찾기1. 모두 일일이 비교 (n-1번)2. 토너먼트 방식 (n-1번)-> 효율성은 같다. 어떤 알고리즘을 써도 상관 없다.- 뒤섞인 카드에서 원하는 카드 찾기1. 순차탐색 (sequential search) -> n-1 번- 순서대로 나열된 카드에서 찾기1. 이진탐색 (binary search) -> - 알고리즘 설계 기법- 주어진 문제, 속성, 조건 등의 매우 다양-> 일반적이고 범용의 기법 x- 대표적인 방법- 분할정복- 동적 프로그래밍- 욕심쟁이 - 알고리즘 분석- 정확성 분석 ==> 여기선 다루지 않을 것- 유효한 입력, 유한 시간 -> 정확한 결과 생성?- 다양한 수학적 기법을 사용해서 이론적 증명이 필요- 효율성- 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정- 메모리 양 -> 공.. 알고리즘 - 1강. 알고리즘 소개 알고리즘 - 1강. 알고리즘 소개 - 알고리즘 기본 개념 - 알고리즘의 설계 및 분석 - 분할 정복 알고리즘/동적 프로그래밍/욕생쟁이/정렬/탐색/근사/해시 - 알고리즘의 기본 개념 - 컴퓨터 과학? : 컴퓨터를 활용해서 주어진 문제를 해결하기 위한 학문 - 알고리즘? - (페리스아 수학자 알콰리즈미에서 유래 - 문제 해결을 위한 '레시피' - '맛잇고 좋은 음식' vs '효울적인 알고리즘' - 주어진 문제를 풀기 위한 명령어들의 단계적 나열 - 입출력(1개 이상 출력), 명확성, 유한성(반드시 종료), 유효성(컴퓨터에서 수행 가능해야 함) - ex) 최댓값 구하기, 퀘닉스버그 다리 문제 (한붓그리기, 오일러경로), 단일 출발점 최단 경로(데이스트라 알고리즘), - 알고리즘 생성 단계 - 설계 -> 표현/.. 이전 1 2 다음