Computer Science/Algorithm6 페이지 교체 알고리즘 운영체제가 페이지 부재가 발생했을 때 메모리에 새 페이지를 적제하기 위해기존 페이지 중 하나를 선택하여 교체하는 방법 ▶ 페이지가상 메모리 시스템에서 프로그램의 주소 공간은 일정 크기의 블록으로 나눠지는데, 이 블록을 페이지라고 함→ 컴퓨터 운영체제의 가상 메모리 관리에서 사용하는 메모리 관리 단위→ 가상 메모리와 실제 물리적 메모리 간의 매핑을 관리하는 기본 단위→ 일반적으로 4KB, 8KB 등의 크기를 가짐운영체제는 프로그램을 실행할 때 필요한 메모리를 페이지 단위로 나눠서 관리함이 과정을 통해 메모리 효율성을 높이고, 프로그램이 필요한 만큼의 메모리만 실제로 할당받아 사용할 수 있게 됨 ▶ 페이지 테이블각 프로세스는 페이지 테이블을 가지고 있으며, 이 테이블은 가상 주소와 물리적 주소 간의 매핑 .. 2024. 7. 23. [Algorithm] 탐욕 알고리즘 Greedy Algorithm 문제를 해결하는 과정에서 그 순간순간 최적이라고 생각되는 결정을 하는 방식 >> 지역적으로 최선의 선택을 하여 전체적으로 최적의 결과를 도출하겠다! 탐욕적 선택 속성 현재 선택이 그 이후의 선택에 영향을 주지 않음 최적 부분 구조 큰 문제를 작은문제로 나눌 수 있으며 작은 문제의 방법으로 큰 문제를 해결할 수 있음 ▼ 문제점 ▼ 제일 빠른 길은 1 → 3 → 5 인데 그리디 알고리즘을 적용하면 오른쪽과 같은 문제점이 생길 수 있음 ▶ Greedy Argorithm 문제 중에 젤 유명한 문제 ▼ 함수 안에 뭐 써야할까 ▼ 함수 안에 뭐 써야할까 >> 400을 리스트에 추가해도 결과는 6이 나옴 >> 탐욕 알고리즘의 문제점을 보여줌 2023. 10. 5. [Algorithm] 복잡도 알고리즘 복잡도 알고리즘이 얼마나 많은 리소스를 사용하는지 측정하는 방법 시간 복잡도 알고리즘이 문제를 해결하는데 얼마나 많은 시간이 필요한지를 측정 입력 크기에 따른 연산 횟수로 표현하며 이 연산 횟수가 증가하는 속도를 나타내는 것이 중요 공간 복잡도 알고리즘이 문제를 해결하는데 얼마나 많은 메모리가 필요한지를 측정 입력 데이터 외에 추가적으로 필요한 공간을 어떻게 만들어줄지 Big O notation 시간 및 공간 복잡도를 표현하기 위한 수학 표기법 O()는 최악의 경우(worst case scenario)에서 알고리즘의 성능을 의미, 입력크기가 n이라고 할 때 함수의 상한선(upper bound)를 제공 O(1) 상수 시간(constant time) : 입력 크기와 무관하게 항상 동일한 시간이 걸림.. 2023. 10. 5. [Algorithm] 정렬 Sorting 정렬 1. Selection Sort 선택정렬 가장 간단하지만 효율성이 떨어지는 정렬 알고리즘 기본 아이디어는 매 순환(linear search)에서 가장 작은/큰 요소를 찾아서 위치를 이동하여 정렬함 리스트에서 최소값 찾음 ↓ 그 값을 첫번째 값과 교환 ↓ 남은 리스트 중 가장 작은 값을 두번째 값과 교환 ↓ 이 과정을 전체 리스트가 정렬될 때 까지 반복 시간 복잡도 : O(n^2) 2. Insertion Sort 삽입정렬 리스트의 두번째 요소부터 시작하여 현재 키를 그 이전의 모든 요소와 비교함 ↓ 키가 이전 요소보다 작으면 이전 요소를 한 위치 오른쪽으로 이동시킴 ↓ 키가 이전 요소보다 큰 위치를 찾을 때 까지 혹은 모든 이전 요소를 확인 할 때 까지 반복 ↓ 원하는 위치에 키 값을 .. 2023. 10. 5. [Algorithm] 재귀 · 탐색 Recursion 재귀 Searching 탐색 탐색 알고리즘 : 데이터 구조에서 특정 값을 찾는 방법 1) 선형탐색 linear Search 가장 간단한 형태의 알고리즘 리스트의 처음부터 끝까지 원하는 요소를 찾을 때 까지 하나하나 확인함 시간복잡도가 최선의 경우 O(1), 최악의 경우 O(n) >> n :리스트의 길이 정렬에 대한 의미가 없음 2) 이진 탐색 이진 탐색은 정렬된 배열에서 특정 값을 찾는데 사용되는 효율적인 알고리즘 중간값과 찾으려는 값을 비교해서 검색 범위를 절반으로 줄여나감 매 단계 검사 해야할 요소가 절반으로 줄어들기 때문에 시간복잡도는 O(log N) >> 엇 훨씬 효율적이네 (데이터가 커지면 커질수록) 문제01 문제02 2023. 9. 27. [Algorithm] 자료구조 자료구조와 알고리즘 Data Structor 메모리 담당 Algorithm 속도 담당 어떻게 하면 최저의 비용으로 최고의 성과를 낼까 메모리가 감소하면 속도도 줄어듦 (비용감소) 메모리가 증가하면 속도도 빨라짐 (비용증가) 자료구조 데이터를 효율적으로 저장 · 조직화 · 관리하기 위한 방법 >> 알고리즘을 도와주는 요소 자료를 기억장치의 공간 내에 저장하는 방법 + 자료간의 관계, 처리 방법 등을 연구 · 분석한 것 선형 구조 배열, 스택 · 큐, 연결리스트, 데크 비선형 구조 트리, 그래프 목차) 1. 배열(Array) 2. 스택(Stack) · 큐(Queue) 3. 연결리스트(Linked List) 4. 트리(Tree) 1. 배열 (Array) 동일한 유형의 요소들의 데이터들이 연속적인 메모리 공간에.. 2023. 9. 14. 이전 1 다음
