전체 글 241

[C++ STL] 3.4 C++ 해시 테이블

C++ 해시 테이블해시 구현에서 항상 양의 정수만 취급할 수는 없다.오히려 문자열 데이터를 다루게 되는 경우가 더 많다영어 사전을 구현하려면 영어 단어를 키로 사용하고, 뜻을 값으로 사용해야 한다모듈로 함수는 문자열에는 적용할 수 없다간단한 해결책은 문자열의 모든 문자에 대한 ASCII 코드 값을 모두 더한 후에 모듈로 연산을 하는 것이다.위 방법은 충돌이 빈번하게 발생할 수 있다C++은 문자열로부터 해시 값을 생성하는 용도로 std::hash>(std::string) 함수 객체를 제공한다이 함수 객체 내부에는 해시 함수 알고리즘이 구현되어 있다.C++은 문자열 이외에도 모든 기본 데이터 타입에 대한 해시 값을 생성하는 기능도 제공한다"체이닝을 사용하는 해시 테이블"에서 구현했던 해시 테이블 코드를 템플..

[자료구조] 해시 테이블(2)- 충돌

해시 테이블에서 충돌다수의 키를 저장할 수 없는 문제를 해결해보자체이닝앞에서는 하나의 해시 값에 대해 하나의 원소만을 저장했다.따라서 특정 해시 값 위치에 이미 원소가 존재한다면 새로운 값과 예전 값 중 하나를 버릴 수밖에 없었다.체이닝(chaining)은 두 값을 모두 저장할 수 있는 여러 방법 중 하나이다이 방법은 해시 테이블의 특정 위치에서 하나의 키를 저장하는 것이 아니라, 하나의 연결 리스트를 저장한다새로 삽입된 키에 의해 충돌이 발생하면, 리스트의 맨 뒤에 새로운 키를 추가한다따라서 다수의 원소를 원하는 만큼 저장할 수 있다벡터 대신 연결 리스트를 사용하는 이유는, 특정 위치의 원소를 빠르게 삭제하기 위함이다Example) 체이닝을 사용하는 해시 테이블#include #include #incl..

[자료구조] 해시 테이블(1)

해시 테이블lookup(룩업, 조회)는 특정 원소가 컨테이너에 있는지 확인하거나 또는 컨테이너에서 특정 키(key)에 해당하는 값(value)를 찾는 작업을 의미한다DB에서 원하는 자료를 찾거나, 사전에서 단어의 뜻을 찾는 문제들이 이에 해당모든 원소를 선형으로 검토하여 원하는 값을 찾는 작업은 일반적으로 매우 많은 시간이 소요된다O(N) 시간 복잡도를 가짐이 작업을 훨씬 빠르게 수행할 수 있는 효과적인 알고리즘이 필요하다.해시 테이블과 블룸 필터라는 효과적인 구조에 대해 살펴본다.해시 테이블O(N)을 갖는 선형 검색보다 더 나은 검색 방법은 BST와 같은 속성을 갖도록 높이 균형 트리에 데이터를 저장하는 것이다.시간 복잡도가 O(log N)이므로 선형 검색보다 훨씬 빨라진다검색 횟수가 증가하면 이 정도..

[C++ STL] 2.6 그래프(graph)

그래프(graph)트리는 원형 또는 순환적인 종속성을 표현할 수 없다.하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에도로망을 생각해보자. 특정 노드에서 다른 노드로 이동하기 위한 다양한 경로가 존재할 수 있다.이러한 경우에는 그래프(graph) 구조를 사용해야 한다그래프 구분 - weight그래프는 노드 데이터뿐만 아니라 노드 사이의 에지 데이터도 저장해야 한다.도로망을 예로 들면 각각의 노드에 다른 어떤 노드들이 연결되어 있는지에 대한 정보를 가지고 있어야 한다.이런 방법으로 필요한 모든 노드와 에지가 있는 그래프를 만들 수 있다.이러한 그래프를 비가중 그래프(unweighted graph)라고 한다.에지에 가중치 또는 더 많은 정보를 부여할 수 있다.도로망에서 에지에 노드와 노드 ..

[C++ STL] 2.5 힙(Heap)

힙(heap)std::priority_queue에서 다룬 heap에 대해 더 깊이 있게 알아보자힙은 앞서 말했던 것처럼 다음과 같은 시간 복잡도를 만족해야 한다O(1) : 최대 원소에 즉각적으로 접근할 수 있어야 한다.O(log N) : 원소 삽입에 대한 시간 복잡도O(log N) : 최대 원소 삭제에 대한 시간 복잡도원소 삽입 또는 삭제에 대해 O(log N)의 시간 복잡도를 만족하기 위해 트리 구조를 사용해야 한다.특히 이 경우 완전 이진 트리를 사용해야 한다.완전 이진 트리는 트리의 데이터를 배열을 이용하여 저장할 수 있다.루트 노드를 배열 또는 벡터의 맨 처음에 저장하고, 그다음 레벨의 모든 노드는 왼쪽부터 오른쪽 순서로 저장한다포인터를 사용하지 않아서 메모리 사용 측면에서 효율적이다.부모 노드로..

[운영체제] 14. File System Implementation

File System Implementation파일 시스템 구현 (File System Implementation)사용자 관점에서의 파일 시스템 (File system of the user’s viewpoint)파일 시스템을 사용자에게 어떻게 보여줄 것인가?파일 시스템 인터페이스파일, 디렉토리, 속성 및 작업예: 트리 구조저장 관리 관점에서의 파일 시스템 (File system of the storage management viewpoint)논리적 파일 시스템을 저장 장치에 어떻게 매핑할 것인가?파일 시스템 구현레이아웃, 데이터 구조 및 알고리즘저장 내부를 이해하는 것이 필요함파일 시스템은 저장 장치를 블록의 시퀀스로 간주디스크와 메모리 간의 데이터 전송은 블록 단위로 이루어짐.각 블록에는 일반적으로 5..

[운영체제] 13. File System Interface

File System파일 시스템File system저장 장치에 데이터를 조직화하는 소프트웨어.User's viewpoint (사용자의 관점)Storage management's viewpoint (저장 관리의 관점)사용자의 관점에서의 파일 시스템File system interface (파일 시스템 인터페이스)How to show the file system to user? (사용자에게 파일 시스템을 표시하는 방법)파일, 디렉터리, 속성, 그리고 작업트리 구조저장 관리 관점에서의 파일 시스템File system implementation (파일 시스템 구현)How to map the logical file system to the storage device? (논리적 파일 시스템을 저장 장치에 매핑하는 방..

[운영체제] 12. I/O Systems

Modern I/O Systems다양한 종류의 I/O 장치가 있습니다CPU는 디바이스 컨트롤러(device controller)와 상호작용합니다.디바이스 컨트롤러는 읽고 쓸 수 있는 레지스터 세트를 포함합니다.Programmed I/OPort I/O특수 프로세서 명령어를 사용하여 데이터를 전송합니다.예: 인텔 아키텍처의 in/out 명령어각 장치는 다른 I/O 포트를 사용합니다. (포트 번호)Memory-mapped I/O디바이스 컨트롤러의 레지스터는 물리 주소 공간에 매핑됩니다.주소는 하드웨어 점퍼(hardware jumper) 또는 부팅 시 프로그래밍으로 설정됩니다.I/O는 로드 및 저장 명령어(load and store instructions)를 통해 수행됩니다.I/O 주소 공간이 시스템 메모리 주..

[운영체제] 11. Mass-Storage Structure

Hard Disk InternalsMoving head disk mechanism아래 내용은 참고 트랙(track): 디스크 표면에서의 원형 경로스핀들(spindle): 디스크를 회전시키는 중심축섹터(sector): 트랙을 나눈 작은 저장 단위실린더(cylinder): 동일한 위치의 모든 트랙표면(surface): 플래터의 저장 공간플래터(platter): 회전하는 디스크헤드(head): 데이터를 읽고 쓰는 장치회전(rotation): 디스크의 회전 운동Disk I/O service time디스크 I/O 서비스 시간: 탐색 시간 + 회전 지연 + 데이터 전송 시간탐색 시간(Seek time): 디스크 헤드를 원하는 트랙으로 이동하는 시간(위 아래 수직이동)탐색 시간 ≈ 탐색 거리회전 지연(Rotation..

[운영체제] 10. Virtual Memory

Virtual Memory ConceptsRestricted physical memory size물리적 메모리 크기의 제한물리적 메모리 공간보다 큰 프로그램은 실행될 수 없음.General program execution pattern일반적인 프로그램 실행 패턴프로그램의 일부만 실행되고 전체 프로그램은 실행되지 않음.오류 코드 및 예외 코드100x100 배열 중 10x10 요소만 사용됨.프로그램의 특정 옵션 및 기능이 드물게 사용됨.전체 프로그램이 필요할 때조차도 모든 부분이 동시에 필요하지 않을 수 있음.Virtual memory가상 메모리메모리에 완전히 들어가지 않은 프로세스의 실행을 허용.프로그램의 일부만 메모리에 있어도 실행 가능.논리적 메모리 주소 공간과 물리적 메모리 주소 공간의 분리.논리적 ..