전체 글

슬라이딩 윈도우: 고정 사이즈의 윈도우가 이동하며 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘 정렬 여부와 관계없이 사용 좌 또는 우 한 방향으로만 이동 교과서에 정의된 내용이 아니며, 투 포인터와 혼용하여 쓰기도 하고, 원래 네트워크에서 사용되던 알고리즘 이름 정렬 여부 윈도우 사이즈 이동 투 포인터 대부분 O 가변 좌우 포인터 양방향 슬라이딩 윈도우 X 고정 좌 또는 우 단방향 239. Sliding Window Maximum - 브루트 포스 - 큐로 최적화 -> 윈도우 이동하여 최댓값 계산 시, 이전 윈도우의 최댓값이 빠질 때만 새로 계산 ※ 고정된 윈도우 크기로 탐색하면서 필요한 계산 수행 (가능하면 계산 최소화하여 구현) 76. Minimum Window Substring - 브루..

부울 연산자: NOT, AND, OR (기본), XOR (보조) 기본 연산자를 조합해 보조 연산 가능 XOR: TT, FF 일때는 F 반환, TF, FT 일때는 T 반환 # XOR x = y = True (x and not y) or (not x and y) >>> False 비트 연산자 ~ : (2의 보수) - 1, 십진수로는 -x-1, 부울 변수 True에 적용하면 -1-1 = -2 True & False # Bitwise AND >>> False True | False # Bitwise OR >>> True True ^ True # Bitwise XOR >>> False ~ True # Bitwise NOT >>> -2 # 십진수와 마찬가지로 연산 bin(0b0110 + 0b0010) >>> '0b..

이진 검색: 정렬된 배열에서 타겟을 찾는 검색 알고리즘 값을 찾아내는 시간 복잡도가 O(logn) 704. Binary Search - 재귀로 이진 검색 * 파이썬은 재귀 호출 횟수 제한이 1000번으로 정해져있으므로 유의 (sys 모듈로 변경가능하지만 대부분 지원하지 않음) - 반복으로 이진 검색 - 이진 검색 모듈 bisect - index() * 최악의 경우 O(n)으로, 앞에서부터 탐색하므로 뒤에 위치할수록 느려진다 bisect.bisect(iterable, value)는 bisect.bisect_right(iterable, value)와 같으며 value 값이 iterable에 정렬되어 삽입된다면 위치할 인덱스 값 리턴 -> value 값과 동일한 값이 이미 iterable에 있다면 그 값 우측..

정렬 알고리즘: 목록의 요소를 특정 순서대로 넣는 알고리즘, 대게 숫자식 순서와 사전식 순서로 정렬 버블 정렬(O(n^2)): 배열의 요소를 끝까지 순차적으로 탐색하며 연달아 있는 2개의 요소의 순서가 맞지 않으면 스왑 병합 정렬(O(nlogn)): 배열을 더 이상 분할이 안될때까지 반씩 나누고, 요소들을 정렬하면서 이어붙힌다 대부분의 경우 퀵 정렬보다 느리지만 일정한 속도와 안정 정렬인 점 때문에 많이 쓰인다 퀵 정렬(O(nlogn)): 분할 정복 알고리즘에 피벗 개념을 추가해 피벗보다 작으면 왼쪽, 크면 오른쪽에 배치되게 분할 이미 정렬된 배열이 입력되는 등의 비효율적인 상황에서는 O(n^2) 가장 간단한 분할 알고리즘인 로무토 파티션은 피벗이 가장 오른쪽 요소 안정 정렬: 입력된 순서가 다른 기준으..

트라이: 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조 특히 자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다 검색을 뜻하는 '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인 것을 우선적으로 교체 메모리의 각 페이지가 어떤 프로세스의 것인지도..