본문 바로가기
728x90

👨‍💻Computer Science/알고리즘 분석8

[알고리즘 분석] 03 - 1 동적계획(Dynamic Programming) 동적계획 divide-and-conquer(분할정복식, 재귀) 알고리즘은 하향식(top-down) 해결법 나누어진 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합 피보나찌 알고리즘은 나누어진 부분들이 서로 연관이 있음. 같은 항 f(i) 를 한 번 이상 -> 비효율적 분할정복식 방법은 적합하지 않음. 동적계획법(dynamic programming)은 상향식 해결법(bottom-up approach) 분할정복식 방법과 마찬가지로 문제를 나눈 후에 나누어진 부분들을 먼 저 푼다. 인덱스를 효과적으로 설정하여 작은 문제들의 중복해결을 배제 작은 문제 해결을 먼저 결과를 큰 문제의 해결로 확산 개발 절차 (1) 재귀 관계식(recursive property) 정립 (2) 작은 사례를 먼저 해결하는 상.. 2021. 10. 2.
[Python] Python numpy, matapotlib 라이브러리 설치 no module named 'matplotlib' 문제해결 방법 pip install matplotlib을 통해 matplotlib라이브러리를 설치해줘야 합니다. 1. pip의 중요성 - matplotlib 설치 : cmd 창에 다음과 같은 명령어를 입력한다. pip install matplotlib - numpy 설치 : cmd 창에 다음과 같은 명령어를 입력한다. pip install numpy 2. pip 명령어를 실행시키면 종종 마주치는 문제 'pip'은(는) 내부 또는 외부 명령, 실행할 수 있는 프로그램, 또는 배치 파일이 아닙니다. *위 그림과 같이 py파일의 경로를 찾고 그 안에 있는 Scripts 파일로 경로를 이동한 후 pip를 사용해주면 문제가 해결됩니다. Numpy의 특징 대화 형.. 2021. 9. 29.
[알고리즘 분석] 02 - 3 빠른정렬(Quicksort) 빠른정렬(Quicksort) 1962년에 영국의 호아(C.A.R. Hoare)의 의해서 고안 빠른정렬(quicksort)란 이름이 오해의 여지가 있음. 왜냐하면 사실 절대적으 로 가장 빠른 정렬 알고리즘이라고 할 수는 없기 때문이다. 차라리 “분할교환정렬(partition exchange sort)”라고 부르는 게 더 정확함. 보기: 15 22 13 27 12 10 20 25 *빠른정렬 알고리즘의 수행절차. 부분배열은 네모로 둘러싸 여 있는 데 반해, 기준 아이템은 그렇지 않다. 빠른정렬 알고리즘 문제: n개의 정수를 비내림차순으로 정렬 입력: 정수 n > 0, 크기가 n인 배열 S[1..n] 출력: 비내림차순으로 정렬된 배열 S[1..n] 알고리즘: 분할 알고리즘 문제: 빠른정렬을 하기 위해서 배열 S.. 2021. 9. 23.
[알고리즘 분석] 02 - 2 합병정렬(mergesort) 합병정렬(mergesort) 문제: n개의 정수를 비내림차순으로 정렬하시오. 입력: 정수 n, 크기가 n인 배열 S[1..n] 출력: 비내림차순으로 정렬된 배열 S[1..n] 보기: 27, 10, 12, 20, 25, 13, 15, 22 합병(merge) 문제: 두 개의 정렬된 배열을 하나의 정렬된 배열로 합병하시오. 입력: (1) 양의 정수 h, m, (2) 정렬된 배열 U[1..h], V[1..m] 출력: U와 V에 있는 키들을 하나의 배열에 정렬한 S[1..h+m] 시간복잡도 분석 합병 알고리즘의 최악의 경우 시간복잡도 분석 단위연산: U[i]와 V[j]의 비교 입력크기: 2개의 입력 배열에 각각 들어 있는 항목의 개수: h와 m 분석: i = h+1이고, j = m인 상태로 루프(loop)에서 빠.. 2021. 9. 16.
[알고리즘 분석] 02 - 1 분할정복법(divide-and-conquer) 분할정복(Divide-and-Conquer)식 설계 전략 분할(Divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다. 정복(Conquer): 나눈 작은 문제를 각각 해결한다. 통합(Combine): (필요하다면) 해결된 해답을 모은다. 이러한 문제 해결 방법을 하향식(top-down) 접근방법이라고 한다. 이분검색(binary search): 재귀적 방식 - 문제: 크기가 n인 정렬된 배열 S에 x가 있는지를 결정하라. - 입력: 자연수 n, 비내림차순으로 정렬된 배열 S[1..n], 찾고자 하는 항목 x - 출력: location, x가 S의 어디에 있는지의 위치. 만약 x가 S에 없다 면 0 - 설계전략: x가 배열의 중간에 위치하고 있는 항목과 같으면, x 찾음. 그렇 지 않으면:.. 2021. 9. 16.
[알고리즘 분석] 01 - 3 차수(order) 대표적인 복잡도 함수 Θ(lg n) Θ(n) : 1차(linear) Θ(n lg n) Θ(n 2 ) : 2차(quadratic) Θ(n 3 ) : 3차(cubic) Θ(2n ) : 지수(exponential) Θ(n!) Θ(n n) 최고차 항이 최종적으로 전체 영향이 가장 크다. • Eventually 10,000보다 큰 n에 대해서 0.01n^2 > 100n. 시간복잡도별 실행시간 비교 Asymptotic(점근적) Behavior f(n)의 asymptotic behavior는 n이 큰 수가 될 때의 함수 f(n)이 갖는 특성 (예) f(n) = 1/n 복잡도 함수 표기법 O( ) - big oh: asymptotic upper bound o( ) - small oh: upper bound that i.. 2021. 9. 14.
[알고리즘 분석] 01 - 2 알고리즘의 분석(analysis) 알고리즘 분석 공간복잡도(space(memory) complexity) 분석 입력크기에 따라서 작업공간 (메모리)이 얼마나 필요한 지 결정 하는 절차 시간복잡도(time complexity) 분석 입력크기에 따라서 단위연산이 몇 번 수행되는지 결정하는 절차 알고리즘이 수행되는 기계에 따라 문제를 해결하는 시간이 달라 짐. 우리의 관심도 시간복잡도 > 공간복잡도 시간복잡도분석의 기준 기계에 독립적인, 문제 본연의 복잡도를 표현하여야 함. 표현 척도 - 단위연산(basic operation) 비교문(comparison), 지정문(assignment) 등 - 입력크기(input size) 배열의 크기, 리스트의 길이, 행렬에서 행과 열의 크기, 트리에 서 마디와 이음선의 수 분석 방법의 종류 Every-cas.. 2021. 9. 14.
[알고리즘 분석] 01 - 1 알고리즘: 효율, 분석 그리고 차수 알고리즘에서 효율, 분석 그리고 차수 알고리즘을 만들어 얼마만큼의 효율성이 있는지 더불어 그것을 분석하여 얼마만큼 빨리 문제를 해결할 수 있는지 알아야합니다. 그리고 분석을 위한 척도로 차수를 정의합니다. 알고리즘 단어의 기원 페르시아의 수학자이자 천문학자, 지리학자인 알코와리즘(780-850)의 이름을 따와 알고리즘이라는 단어가 탄생했습니다. 알고리즘 사용 예시 ex1. 24와 16에 대해 최대공약수, 최소공배수 구하기 이러한 절차를 어떻게 표현할지를 알고리즘 분석을 통해 배우게 됩니다. ex2. a에서 b로 가는 최단거리? 어떻게 최단거리를 찾을 것인지? ex3. 화랑 문제 박물관에서 모든 공간을 감시하기 위한 최소 인원 배치는? ex4. 선분교차문제 컴퓨터 그래픽에서 평면 또는 3차원 공간상의 두 .. 2021. 9. 2.
728x90

티스토리툴바