study-knou (16) 썸네일형 리스트형 동적 프로그래밍 알고리즘(2) 두 문자열 X와 Y사이의 편집 거리(edit distance) 두 문자열 사이의 근접성 또는 유사성을 판단하는 척도 X=x1x2... xn, Y=y1 y 2... ym 문자열 X를 Y로 변환하는 데 필요한 전체 편집 연산에 대한 최소 비용 특정 위치에 새 문자를 삽입하는 연산 -> 삽입 비용 1 특정 위치의 문자를 삭제하는 연산 -> 삭제 비용 1 특정 위치의 문자를 다른 문자로 변경하는 연산 -> 변경 비용 2 X=x1x2x3x4x5 = SNOWY Y= y1 y 2 y3 y4 y 5 = SUNNY SNOWY -> SUNNY로 변경하는데 드는 편집 거리는 최소비용 4 스트링 편집 거리에서의 최적성의 원리 X와 Y사이의 편집 거리는 이들의 부분 문자열 사이의 편집 거리를 포함 x의 마지막 글자가 Y의 마지.. 동적 프로그래밍 알고리즘 (1) 동적 프로그래밍 방법의 원리 문제의 크기가 작은 소문제에 대한 해를 저장해 놓고, 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법 각 작은 문제는 원래의 문제와 동일한 문제이지만 입력의 크기만 작음 입력의 크기가 아주 작은 단순한 문제가 되면 쉽게 해를 구할 수 있고, 이를 테이블에 저장 이후 해당 소문제의 해가 필요할 때마다 테이블에 저장된 결과를 바로 이용 동적 프로그래밍 => 동적 계획법 컴퓨터에서의 프로그램과는 무관, 해를 구축하는 테이블을 이용한다는 의미 최솟값/최댓값을 구하는 문제에 적용 최적화 문제에 동적 프로그래밍 방법을 적용하려면? 최적성의 원리를 반드시 만족시켜야 함 주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성된다. 동적 프로.. 분할정복 알고리즘 2 - 합병 정렬, 선택 문제 - 합병 정렬 - 배열을 동일한 크기의 두 개의 부분 배열로 분할, 각 부분배열을 순환적으로 정렬 후, 정렬된 두 부분배열을 합명 -> 하나의 정렬된 배열을 만듦 - 분할, 정복, 결합 - 합병 정렬은 합병이 중요함 ( 퀵정렬은 분할이 중요 ) - A, B 원소를 하나씩 비교, 남은 하나는 그냥 추가 - 합병 함수 Merge() 수행 시간 ->최악의 경우 세타(n) 선형적으로. - 입력 데이터 개수만큼의 저장 장소가 추가로 필요 (제자리 정렬 알고리즘이 아님) - 합병 정렬 MergeSort() 수행 시간 - 크기 n/2인 두 번의 MergeSort() 순환 호출 + 한 번의 합병 Merge() - T(n) = 2T(n/2) + theta(n) -> T(n) = O(nlon) .. 3. 분할정복 알고리즘 분할정복 방법의 원리 - 순환적으로 문제를 푸는 하향식 접근 방법 - 주어진 문제의 입력을 더 이상 나룰 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식 - 특징 - 분할된 작은 문제는 원래 문제와 동일 -> 단, 입력 크기만 작아짐 - 분할된 문제는 서로 독립적 -> 순환적 분할 및 결과 결합이 가능 - 각 순환 호출 시의 처리 과정 - 분할 : 주어진 문제를 여러 개의 작은 문제로 붑ㄴ할 - 정복 : 작은 문제들을 순환적으로 분할, 만약 작은 문제가 더 이상 분할되지 않을 정도로 크기가 충분히 작다면 순환 호출 없이 작은 문제에 대한 해를 구함 - 결합 : 작은 문제에 대해 정복된 해를 결합하.. 알고리즘 소개2 - 최댓값 찾기1. 모두 일일이 비교 (n-1번)2. 토너먼트 방식 (n-1번)-> 효율성은 같다. 어떤 알고리즘을 써도 상관 없다.- 뒤섞인 카드에서 원하는 카드 찾기1. 순차탐색 (sequential search) -> n-1 번- 순서대로 나열된 카드에서 찾기1. 이진탐색 (binary search) -> - 알고리즘 설계 기법- 주어진 문제, 속성, 조건 등의 매우 다양-> 일반적이고 범용의 기법 x- 대표적인 방법- 분할정복- 동적 프로그래밍- 욕심쟁이 - 알고리즘 분석- 정확성 분석 ==> 여기선 다루지 않을 것- 유효한 입력, 유한 시간 -> 정확한 결과 생성?- 다양한 수학적 기법을 사용해서 이론적 증명이 필요- 효율성- 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정- 메모리 양 -> 공.. 2. 프로세스 개요 프로세스 - 프로세스 : 실행중인 프로그램- 프로그램 : 동작을 하지 않는 정적/수동적 개체- 프로세스 : 동작을 하는 능동적 개체 - 운영체제로부터 자원을 할당받아 동작- 자원 : cpu, 메모리, 입출력장치, 파일 등- 동작 : cpu가 프로세스의 명령을 실행 - 사용자 및 시스템 프로세스 존재- 프로세스 관리자의 역할- 프로세스를 생성 및 삭제- 프로세스 실행(CPU 할당)을 위한 스케줄 결정- 프로세스의 상태를 관리하며 상태 전이를 처리 - 프로세스의 상태5-상태 모델 (생성,준비,실행,종료,대기)- 생성 : 처음 작업이 시스템에 주어진 상태- 준비 : 실행 준비가 되어 cpu 할당을 기다리는 상태- 실행 : 프로세스가 처리되는 상태- 대기 : 프로세스가 특정 자원을 할당받을 때까지 또는 I/O .. 알고리즘 - 1강. 알고리즘 소개 알고리즘 - 1강. 알고리즘 소개 - 알고리즘 기본 개념 - 알고리즘의 설계 및 분석 - 분할 정복 알고리즘/동적 프로그래밍/욕생쟁이/정렬/탐색/근사/해시 - 알고리즘의 기본 개념 - 컴퓨터 과학? : 컴퓨터를 활용해서 주어진 문제를 해결하기 위한 학문 - 알고리즘? - (페리스아 수학자 알콰리즈미에서 유래 - 문제 해결을 위한 '레시피' - '맛잇고 좋은 음식' vs '효울적인 알고리즘' - 주어진 문제를 풀기 위한 명령어들의 단계적 나열 - 입출력(1개 이상 출력), 명확성, 유한성(반드시 종료), 유효성(컴퓨터에서 수행 가능해야 함) - ex) 최댓값 구하기, 퀘닉스버그 다리 문제 (한붓그리기, 오일러경로), 단일 출발점 최단 경로(데이스트라 알고리즘), - 알고리즘 생성 단계 - 설계 -> 표현/.. 1강 운영체제의 개요 CPU의 동작 모드 - 보호 모드 -> *시스템 호출 -> 슈퍼바이저 모드 (운영체제) -> 커널 동작 -> 하드웨어 제어 - 슈퍼바이저 모드로 바뀌어야지만 운영체제로 하드웨어 컨트롤 가능 - *시스템 호출 : 응용 프로그램이 운영체제에게 서비스를 요청 - 운영체제 -> 하드웨어 컨트롤 커널? - 운영체제의 핵심 요소, 응용 프로그램과 하드웨어 수준의 처리 사이의 가교 역할- 일체형 커널, 마이크로 커널 - 일체형 커널(monolithic kernel) : 운영체제 의 모든 서비스가 커널 내에 포함, 커널 내 부 요소들이 서로 효율적으로 상호작용, 한 요소 오류 -> 시스템 전체 장애 발생 가능 (Unix, Linux) - 마이크로 커널(microkernel) 운영체제의 대부분 요소들을 커널 외부로 분 .. 이전 1 2 다음
