Computer Science/알고리즘9 BFS / DFS 참고용 블로그 https://yabmoons.tistory.com/99 [ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++) 브루트포스 알고리즘에서 가장 많이 사용되는 방법이 순열과 조합등으로 모든 경우의 수를 모두 계산해본 뒤에 원하는결과 값을 찾는 방식이다. 이 글에서는, 순열과 조합을 STL을 사용하지 않 yabmoons.tistory.com https://blog.naver.com/kks227/220786417910 백트래킹(Backtracking) (수정 2019-10-09) 탐색 중에서는 가장 마지막으로 쓰는 글이 아닐까 싶습니다. 이제 DFS와 BFS도 익혔으니, 백트래킹(b... blog.naver.com https://foameraserblue.tistory.com/m/188 PS를 .. 2023. 4. 1. 알고리즘10. Heapsort 4. Sorting 4-4. Heapsort Heap and Heapsort Heap: 우선순위 큐 구현 방법 max-heap 기준1. insert()2. findMax()3. deleteMax()3가지 함수를 이용해 정렬 Heap data structure는 특수 속성을 가진 binary tree이다. Heap Structure →구조 Partial order tree property(부분 정렬 트리 속성) →순서 Heap Structure binary tree T는 다음 조건을 만족하는 경우에만 heap structure (h = 트리의 height) 1. T is complete at least through depth h-1 →depth h-1까지 트리가 꽉 차 있다 2. All leaves ar.. 2021. 11. 11. 알고리즘: Mergesort 합병 정렬 4. Sorting 4-3. Mergesort 합병 정렬 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것 입력 데이터가 많으면서 자주 정렬해야 할 필요가 있을 때 사용. 정렬 문제의 문제 복잡도 F(n) = O(n lgn) time 합병 정렬의 worst case complexity W(n) = O(n lgn) time W(n) = F(n) : Optimal algorithm 따라서 합병 정렬 알고리즘은 Optimal algorithm 이다. Merging Sorted Sequences Problem 오름차순으로 정렬된 두 리스트 A, B를 새로운 리스트 C로 합친다. Strategy A와 B.. 2021. 11. 11. 알고리즘6. Searching on Ordered Array(정렬된 배열 탐색)(2) - binary search(이진탐색) 1. Analyzing Algorithms and Problems: Principles and Examples 1-4. Searching on Ordered Array 정렬된 배열 탐색 Let's Divide-and-Conquer 개선된 알고리즘 → 분할과 정복 Problem and Strategy D K를 먼저 배열의 가운데에 있는 entry와 비교 한 번의 연산으로 절반의 entry를 제거할 수 있다. 동일한 전략을 재귀적으로 수행한다. Algorithm D: Binary Search (반드시 정렬된 array 여야 함) Input: E, first, last, and K→ first, …, last까지 정렬된 array E, K 는 찾아야 할 key 값, input 모두 정수 Output: firs.. 2021. 10. 3. 알고리즘5. Searching on Ordered Array(정렬된 배열 탐색)(1) 1. Analyzing Algorithms and Problems: Principles and Examples 1-4. Searching on Ordered Array 정렬된 배열 탐색 Problem and Strategy A Problem: array search 배열 탐색 n개의 entry가 담긴 배열 E와 value K가 주어졌을 때, 배열에서 K=E[index]를 찾는다면 인덱스 값을, K를 찾지 못한다면 -1을 결과로 리턴한다. Strategy A input data와 자료구조: 정렬되지 않은 배열 sequential search(index 0부터 차례로 비교) Algorithm A int seqSearch(int []E, int n, int K) Analysis A W(n) = n //wors.. 2021. 9. 27. 알고리즘4. 점근적 증가율에 따른 함수 분류 1. Analyzing Algorithms and Problems: Principles and Examples 1-3. Classifying Functions by Their Asymptotic Growth Rates 점근적 증가율에 따른 함수 분류 Clasifying Functions asymptotic growth rate점근적 증가율, asymptotic order점근적 순서 또는 order of functions함수 순서 asymptotic: input size n이 충분히 커짐을 뜻함 n이 충분히 커졌을 때 함수의 증가율 상수 인자와 small input을 무시하는 함수 비교 및 분류. The Sets big oh O(g), big thetaθ(g), big omega Ω(g) f와 g가 음이 .. 2021. 9. 13. 알고리즘3. 알고리즘과 문제 분석 1. Analyzing Algorithms and Problems: Principles and Examples 1-3. Analyzing Algorithms and Problems 알고리즘과 문제 분석 Analyzing Algorithms and Problems 알고리즘을 분석하는 이유 1. 알고리즘 개선(☞R&D(Research and development)영역) 2. 문제를 풀 수 있는 다양한 알고리즘 중 가장 최적의 알고리즘을 선택하기 위해(☞사용자 측면. 누군가 개발한 알고리즘을 사용) 알고리즘 분석 요소 - Correctness 정확성 - Efficiency 효율성 Amount of work done(시간 복잡도 Time Complexity) Space used(공간 복잡도 Space Compl.. 2021. 9. 7. 알고리즘2. 수학적 배경지식 1. Analyzing Algorithms and Problems: Principles and Examples 1-2. Mathematical Background 수학적배경지식 Analysis Tool: Mathematics - series: 숫자들의 나열(sequence)의 합 - Arithmetic series: 연속적으로 증가하는 정수들의 합 - Polynomial Series 다항식 시리즈 -The sum of squares -The general case is - Power of 2 -Arithmetic-Geometric Series Analysis Tool: Logic(논리학) Logic: 더 명확한 추론을 위해 자연어를 formalizing(수학적으로 형식화)하는 시스템 A ⇒ B A imp.. 2021. 9. 2. 알고리즘 1. Problem Solving의 절차 1. Analyzing Algorithms and Problems: Principles and Examples -알고리즘 & 문제 complexity 분석 1-1. Introduction 컴퓨터 알고리즘 상세한 단계별(step-by-step) 방법으로 유한 시간(finite time) 이내 컴퓨터를 이용해 문제를 해결하는 것 Problem Solving의 체계적 절차 Problem(문제 정의) > Strategy(문제풀이 전략) > Algorithm(알고리즘, 의사코드 서술) > Anaysis(서술한 알고리즘을 분석) > Implementation(구현) > Verification(검증) 1. Problem 문제 정의 ex. 비정렬 배열을 정렬하는 알고리즘 input : 5, 3, 67, 1, 2 -> .. 2021. 9. 2. 이전 1 다음 반응형
