정렬 알고리즘: 목록의 요소를 특정 순서대로 넣는 알고리즘, 대게 숫자식 순서와 사전식 순서로 정렬 버블 정렬(O(n^2)): 배열의 요소를 끝까지 순차적으로 탐색하며 연달아 있는 2개의 요소의 순서가 맞지 않으면 스왑 병합 정렬(O(nlogn)): 배열을 더 이상 분할이 안될때까지 반씩 나누고, 요소들을 정렬하면서 이어붙힌다 대부분의 경우 퀵 정렬보다 느리지만 일정한 속도와 안정 정렬인 점 때문에 많이 쓰인다 퀵 정렬(O(nlogn)): 분할 정복 알고리즘에 피벗 개념을 추가해 피벗보다 작으면 왼쪽, 크면 오른쪽에 배치되게 분할 이미 정렬된 배열이 입력되는 등의 비효율적인 상황에서는 O(n^2) 가장 간단한 분할 알고리즘인 로무토 파티션은 피벗이 가장 오른쪽 요소 안정 정렬: 입력된 순서가 다른 기준으..
CS
트라이: 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조 특히 자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다 검색을 뜻하는 'retrieval'에서 따옴 다진 트리의 형태 각 문자열 길이만큼만 탐색하면 원하는 결과 찾을 수 있다 208. Implement Trie (Prefix Tree) - TrieNode 클래스 생성해 딕셔너리로 노드 값 정보, 불리안으로 해당 노드에서 단어 완성 여부 정보를 각 노드에 담는다 -> 삽입이나 검색하려는 문자열 갯수만큼 반복하여 각 노드의 딕셔너리 확인하며 필요한 작업 수행 336. Palindrome Pairs - 부르트 포스 -> 시간 초과 O(n^2) - 트라이 구현 -> 입력..
ROM: 메모리의 전원이 나가도 내용이 유지되는 소량의 부분, 전원이 켜지면 CPU가 ROM의 주소를 가리킴 loader는 하드디스크의 0번 섹터의 내용을 메모리에 올려 실행하라 명령 boot block은 파일 시스템에서 OS 커널의 위치를 찾아 메모리에 올려 실행하라 명령 N-SCAN으로 SCAN보다 대기시간을 조금 더 균일하게 함 여러 요청을 한꺼번에 묶어서 처리(merge)하여 효율성을 높이기도 함 프로세스 종료 시 필요없는 내용이기 때문에 공간보다는 속도 효율성이 더 중요 seek time 줄이는 것이 주요하므로 파일 시스템보다 훨씬 큰 단위의 데이터를 처리한다 parity: 오류를 생겼는지 알 수 있고 복구할 수 있을 정도의 중복저장만 간략하게 해주는 기법 출처: https://core.ewha..
메모리에 매핑하면 운영체제 관여 없이 메모리 접근 연산만으로 파일 입출력과 같은 효과를 낸다 물리 메모리에 올라와있지 않으면 마찬가지로 page fault 발생해 OS로 CPU 제어권이 넘어간다 unified buffer cache 일 때 물리 메모리에 매핑된 페이지가 올라오면 시스템콜 없이 직접 파일에 접근 가능 물리 메모리에 매핑된 데이터가 스왑될때는 swap area가 아닌 파일 시스템에 변경된 사항을 반영한 후 삭제된다 가상 메모리의 code 부분도 읽기만 가능하므로 실행파일에 온전히 존재하여 swap area로 가지 않고 삭제된다 다른 프로세스가 같은 데이터 파일을 매핑하면 물리 메모리에서 같은 주소를 공유하며 접근한다 일관성 문제에 유의해야 함 B가 데이터 파일을 매핑하여 물리 메모리에 올라가..
직접 접근이 가능한 매체(예: 디스크)라도 데이터를 관리 방식에 따라 순차 접근만 허용되는 경우도 있다 파일들을 디스크에 연속적으로 저장 공간 효율보다는 시간 효율이 중요한 상황에서 사용하면 좋다 (realtime, swapping) 파일의 부분들을 디스크의 남는 자리에 저장하고, 각 부분에는 다음 부분의 위치를 가리키는 포인터가 있음 index block을 별도로 두어서 각 파일 부분의 위치정보를 순서대로 담고 있다 index block을 여러개 연결하거나, 계층을 두어 큰 파일도 처리 가능 -> 공간 효율 ↓ boot block: 어떤 파일 시스템이든 맨 처음에 위치, 커널의 위치를 찾아 부팅할 수 있게 하는 역할 super block: 디스크의 빈 block 정보, 할당된 block 정보, inod..
메모리(주소로 접근), 파일(이름으로 접근) reposition: 파일 내 포인터를 그 파일의 다른 곳으로 옮기는 것 (계속 연속적으로만 읽지 않을 수 있음) open root의 metadata 위치는 이미 알고 있어서 메모리에 올려놓고 root 파일에 있는 a의 metadata를 메모리에 올림 디렉토리 파일인 a의 metadata 정보로 a의 저장 위치로 접근해 그 안에 있는 b의 metadata를 메모리에 올림 read b의 저장 위치로 접근해 요청한 만큼의 데이터를 OS영역의 버퍼 캐시 공간에 저장 버퍼 캐시에 있는 데이터의 복사본을 사용자 메모리 영역에 저장 요청한 데이터가 버퍼 캐시에 존재하는 경우 CPU 판단 하에 디스크를 경유하지 않고 바로 복사하여 전달 A의 PCB에 파일 b의 metada..
TLB도 캐시 메모리의 일종 CPU가 요청한 페이지가 이미 물리 메모리에 있다면 접근과정(주소변환)에서 OS의 역할은 없다 page fault가 생겨 OS가 제어권을 가질때만 관여하므로 LRU, LFU 모두 사용 불가(참조시각, 참조빈도 모름) 하드웨어적으로 물리 메모리에서 바로 참조한 페이지는 page table의 reference bit을 1로 설정 replacement 상황 시 OS가 bit=1인 페이지는 0으로 바꾸고 다음으로 이동하면서 최초로 bit=0인 페이지 교체 modified bit 사용하여 CPU가 write로 접근한 페이지에 대한 처리 가능하게 함(변경사항 반영하여 디스크에 저장) 가급적 modified bit도 0인 것을 우선적으로 교체 메모리의 각 페이지가 어떤 프로세스의 것인지도..
OS가 관리하는 부분을 배운다 지금 필요하지 않는 페이지는 disk(swap area)에 저장 CPU가 요청한 페이지가 물리 메모리에 없다면 page fault -> 디스크에서 불러오는 I/O 작업 필요 현대 시스템은 page fault 비율이 0.1 이하 정도로 낮다 디스크에서 페이지를 불러올 때 물리 메모리에 자리가 없다면 page fault가 최대한 덜 나타나도록 자리를 만든다 reference string: 페이지에 번호를 매겨 참조된 순서대로 기록한 것 victim이 수정되었다면 반영하여 backing store에 저장, 아니라면 그냥 삭제 미래에 참조될 페이지를 안다고 가정하는 알고리즘 -> offline -> 비현실적인 최대 효율 알고리즘 LRU는 연결 리스트로 구현하여 맨 위 페이지 추출하..
힙: 힙의 특성(최소 힙에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리 파이썬에는 최소 힙만 구현(heapq 모듈) 우선순위 큐에서 가장 작은 값을 가져올때 매번 최소 힙의 루트를 가져오면 된다 부모 자식 간의 관계만 정의하므로 정렬된 구조가 아님 자식이 둘인 힙은 이진 힙이라 하며, 이진 트리와 마찬가지 이유로 대부분 이진 힙이 널리 사용됨 배열에 순서대로 표현하기 좋으며, 편한 계산을 위해 인덱스는 1부터 사용 다익스트라 알고리즘, 힙 정렬, 최소 신장 트리, 프림 알고리즘, 중앙값의 근삿값 힙 연산(최소 힙): 삽입(업힙) -> O(logn), 추출(다운힙) -> O(logn), 이진 힙은 조회할 때 O(1) 삽입: 요소를 최하위 레벨의 가장 왼쪽으로 삽입 -> 부모와 비교 ..
트리: 계층형 트리 구조를 시뮬레이션 하는 추상 자료형(ADT)으로, 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합 재귀로 정의된 자기 참조 자료구조 트리는 항상 하나의 루트(Root)에서 시작되며, 자식(Child) 노드를 가지고, 간선(Edge)으로 연결되어 있다 차수(Degree): 자식 노드의 개수, 크기(Size): 자신을 포함한 모든 자식 노드의 개수 높이(Height): 현재 위치에서부터 리프까지의 거리, 깊이(Depth): 루트에서부터 현재 노드까지의 거리 레벨은 루트에서 0이고, 노드 A의 자식노드는 A의 레벨 + 1 트리는 순환 구조를 갖지 않는 그래프, 단방향, 하나의 부모 노드, 하나의 루트 이진 트리: 가장 널리 사용되는 트리 자료구조 m-ary 트리(..
