본문 바로가기

알고리즘4

[알고리즘] 4강 분할정복 알고리즘 2 2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 3강 분할정복 알고리즘 - 1 2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 2강 알고리즘 소개 2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개 1. [복습] 분할정복 방법의 원리 순환적으로 문제를 푸는 하향식 접근 방법 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식 '분할' - '정복' - 결합 특징 - 분할된 문제는 원래 문제와 동일(입력 크기만 감소) 하고 서로 독립적 .. 2018. 5. 25.
[알고리즘] 3강 분할정복 알고리즘 - 1 2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 2강 알고리즘 소개 2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개 1. 분할정복 방법의 원리 순환적으로 문제를 푸는 하향식 접근 방법 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식 특징 분할된 작은 문제는 원래 문제와 동일 → 단, 입력 크기만 작아진다. 분할된 문제는 서로 독립적 → 순환적 분할 및 결과 결합이 가능 각 순환 호출 시의 처리 과정 분할: 주어진 문제를 여러 개의 작은 문제로 분할 정복: 작은 문제.. 2018. 5. 22.
[알고리즘] 2강 알고리즘 소개 2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개 1. 알고리즘의 설계 1) 최댓값 찾기 1-1) 값들을 하나씩 모두 비교해 가면서 최댓값을 찾는 방법 1-2) 토너먼트 방식 둘씩 비교해서 큰값을 찾아가는 방법 더 효율적인것을 결정해야한다. (n-1)번 1-1과 1-2 의 효율성은 7번으로 같다. 2) 뒤섞인 카드에서 원하는 카드 찾기 2-1) 순차탐색(Sequential Search) 순차적으로 전부 다 뒤집는다 1 2 3 4 5 6 7 8 SequentialSearch(A[], n, x) // 배열 A[0..n-1]에서 x를 찾는 알고리즘 { for(i = 0; i Right) return -1; Mid = (left + right) / 2; .. 2018. 5. 22.
[알고리즘] 1강 알고리즘 소개 1. 알고리즘 기본개념1) 알고리즘 생성단계 설계 > 표현/기술 > 정확성 검증 > 효율성 분석2. 기본 자료구조1) 알고리즘에서 자료구조는?1-1) 자료구조 - 컴퓨터 기억공간 내에 자료를 표현하고 조직화 하는 방법 - 프로그램 = 자료구조 + 알고리즘 - 자료구조에 대한 고려 없는 효율적인 알고리즘의 선택, 또는 알고리즘에 대한 고려 없는 효율적인 자료구조의 선택은 무의미기본 자료구조 =배열, 연결리스트 , 스택 , 큐 , 트리 , 그래프선형 자료구조 : 배열 , 연결리스트 , 스택 , 큐 ㄴ 데이터에 순서가 있다. 비선형 자료구조 : 트리, 그래프 ㄴ 데이터에 순서가 없다. 2) 배열 정의: 같은 자료형을 갖는 여러 개의 데이터를 하나의 변수에 저장해놓고 각각의 원소에 접근할 때에는 인덱스 첨자를 .. 2018. 3. 19.