tonirr

탐색의 개념 여러 데이터 중에서 원하는 값을 가진 데이터를 찾는 것 데이터 형태 -> 리스트, 트리, 그래프 등 내부탐색 vs 외부탐색 연산 -> 탐색 + 초기화(정렬), 삽입, 삭제 등 순차 탐색 리스트 형태로 주어진 원소들에 대해서 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법 탐색 실패의 경우 -> 항상 n번 비교 O(n) 탐색 성공의 경우 -> 최소 1번 ~ 최대 n번 비교 O(n) 삽입 -> O(1) 삭제 -> O(n) 삭제할 데이터에 대한 탐색이 필요 특징 모든 리스트에 적용 가능 원소가 무순서로 연속해서 저장된 비정렬 데이터 탐색에 적합 데이터가 큰 경우에는 부적합 탐색과 삭제 -> O(n) 이진 탐색 개념과 원리 정렬된 배열 형태로 주어진 원소들을 절반씩 줄여가면서..

분할정복 방법 순환적으로 문제를 푸는 하향식 접근방법 주어진 문제의 입력을 더이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고 분할된 작은 문제들을 각각 해결한 후 이 해들을 결합해서 원래 문제의 해를 구하는 방식 특징 분할된 작은 문제는 원래 문제와 동일 단, 입력 크기만 작아짐 분할된 작은 문제는 서로 독립적 순환적 분할 및 결과 통합이 가능 분할정복 방법의 처리 단계 각 순환 호출마다 세 단계의 처리과정을 거침 분할: 주어진 문제를 여러 개의 작은 문제로 분할한다. 정복: 작은 문제를 순환적으로 분할, 만약 작은 문제가 더이상 분할되지 않을 정도로 크기가 충분히 작다면 순환호출 없이 작은 문제의 해를 구함 결합: 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구함 ..