본문 바로가기

알고리즘/CLRS

 (6)
3.1 점근적 표기 3. 함수의 증가 입력이 충분히 커지면 정확한 수행시간의 상수계수와 저차항은 입력 크기에 묻혀 버린다. ❓성장률 rate of growth 입렵값의 크기에 따라 함수가 얼마나 빨리 커지는지 즉, 실행시간의 성장률을 알고싶은 것! 우리가 알고 싶은건, 입력값 크기에 따른 알고리즘의 실행시간에 대한 예측이다. 프로그램을 쉽게 예측할수 있도록 불필요한 부분은 과감히 버리고 가장 중요한 부분만 추려서 함수로 간소화해야 한다. 예를 들어 0.6n²+1000n+3000 에서 n이 커질 수록 n²은 기하 급수적으로 커지게 된다. ❓접근적표기법 asymptotic notaion 상수 계수와 중요하지 않은 항목을 제거하는 표기법으로 big-Θ 표기법, big-O 표기법, and big-Ω 표기법이 있다. ❓big-Θ(T..
2.3 알고리즘의 설계 2.3 알고리즘의 설계 분할정복 분할 : 현재 문제를 같은 문제를 다루는 다수의 부분 문제로 분할한다. 정복 : 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 충분히 작으면 직접적인 방법으로 푼다. 결합 : 부분 문제의 해를 결합하여 원래 문제의 해가 되도록 만든다. 병합정렬 분할정복 시간복잡도 연습문제 2.3-1 2.3-2 def merge_without_sentinels(A, p, q, r): nL = q - p + 1 # Length of A[p...q] nR = r - q # Length of A[q+1...r] L = [0] * nL # Initialize arrays L and R R = [0] * nR for i in range(nL): # Copy A[p...q] into L..
2.2 알고리즘 분석 2.2 알고리즘 분석 알고리즘을 실행 시, 필요한 자원 예측 메모리 통신대역 하드웨어 계산시간 RAM 모델 단일 프로세서 + RAM 캐시나 가상메모리는 고려하지 않는다. 명령어는 동시에 수행되지 않고 차례로 하나씩 실행된다. 명령어 한 행당 상수시간 소요 산술연산(덧셈, 뺄셈, 곱셈, 나눗셈, 나머지, 내림, 올림) 데이터이동 연산(읽기, 저장하기, 복사하기) 제어 연산(조건 분기, 무조건 분기, 함수 호출과 리턴) 입력크기는 수행시간에 비례한다. 최악의 경우 : 크기가 n인 입력 중 가장 오래걸리는 수행 시간 평균적인 경우 : n개의 숫자 무작위 하지만 무엇이 평균적인 입력인지 불확실한 경우, 랜덤화된 알고리즘을 사용한다. 연습문제 2.2-1 θ(n³) 2.2-2 for s = 1 to A.length..
2.1 삽입 정렬 2. 시작하기 삽입정렬 분할정복 + 병합 알고리즘 2.1 삽입정렬 정렬하고자 하는 숫자 = key n의 크기가 작을 경우 삽입정렬 > 병합정렬 루프 불변성 초기조건 : 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다. 유지조건 : 루프의 반복이 시작되기 전에 루프 불변성이 참이었다면 다음 반복이 시작되기 전까지도 계속 참이어야 한다. 종료조건 : 루프가 종료될 때 불변식이 알고리즘의 타당성을 보이는데 도움이 될 유용한 특성을 가져야 한다. 수학 귀납적 과정과 유사 초기 조건: 불변식 유지 조건 : 불변식 만족 종료 조건 : 불변식 불만족 연습문제 2.1-1 2.1-2 for j = 2 to A.length key = A[j] i = j - 1 while i > 0 그리고 A[i] < k..
1.2 기술로서의 알고리즘 1.2 기술로서의 알고리즘 시간과 메모리는 한정적인 자원이므로 알고리즘을 공부해 시간과 공간의 자원을 효율적으로 사용해야 함. 📌 알고리즘의 역할 고급 컴퓨터 아키텍처와 제작 기술 사용하기 쉽고 직관적인 그래픽 사용자 인터페이스(GUI) 객체 지향 시스템 통합 웹 기술 유선 및 무선 모두에 대한 빠른 네트워킹 기계 학습 모바일 장치 📌 하드웨어 = 알고리즘 설계 응용 프로그램 = 알고리즘 설계 즉, 알고리즘 작업을 수행하는 방법이 곧 기계 학습이라고 생각 할 수 있음. 컴퓨터가 계산을 수행하고, 정보를 검색하고, 데이터를 정렬하고, 오류 없이 수많은 다른 작업을 수행하도록 도와주는 게 바로 알고리즘이다. 1.2-1 흠..네이버 길찾기 어플을 사용할때, 걸리는 시간 거리 데이터를 이용해 알고리즘 기능으로 ..
1.1 알고리즘 1.1 알고리즘 다량의 데이터 : 정보를 많이 얻을 수록 시간, 장비, 자금, 인적자원 등이 소요된다. 알고리즘 기술은 이러한 자원을 효율적으로 절약해준다. 빠른 서비스 제공 : 테이터가 전송되는 경로를 찾거나, 특정 정보가 있는 페이지를 빨리 검색하는 문제 등을 해결해준다. 보안 : 개인정보 공개키 암호화, 전자 서명 등의 핵심 기술은 수치 알로리즘과 정수론 등을 기반으로 만들어 졌다. 기업 기대 수익 극대화 : 석유회사 어디에 유정을 뜷어햐 하는지 결정, 정치 입후보자의 승리 가능성 높은 캠페인 예측, 최소 비용이 드는 승무원 스케줄 관리 및 배치, 추가 장비 배치할 위치 결정. 현실세계에서 알고리즘으로 최상의 해를 구하는건 불가능에 가깝다. 하지만 최적의 해를 찾는데는 효율적이라 할 수 있다. 📌 ..

티스토리툴바