CS (46) 썸네일형 리스트형 [ 자료구조 ] 연결 리스트(Linked List) : 단일 연결 리스트 연결 리스트를 배우기 전에 왜 배우는지를 먼저 알고 가자. 결론부터 말하면 연결 리스트는 배열의 단점을 극복하기 위해 나온 자료구조다. 배열의 장단점에는 무엇이 있는지 먼저 알아보고, 연결 리스트의 가장 단순한 구조인 '단일 연결 리스트'를 구현하는게 오늘의 학습목표다. 배열의 특징, 연결리스트 구조 배열은 인덱스를 통해 데이터에 직접적인 접근이 가능하기 때문에 접근이 아주 빠르다는 장점이 있다. 그러나 배열 내의 데이터 이동 및 재구성이 굉장히 힘들다. 배열에서 원소를 하나 삭제하려면 그 뒤에 있는 원소들을 전부 한 칸씩 당겨야 하고, 원소를 삽입하려면 그 뒤에 있는 원소들을 전부 한 칸씩 밀어야 한다. 또한 배열의 크기는 초기에 설정하면 이후에 변경 불가능하다. 초기에 설정한 크기를 넘어가면 데이터 .. [ 자료구조 ] 템플릿, 예외처리 템플릿 공식문서에 따르면, '템플릿은 사용자가 템플릿 매개 변수에 대해 제공하는 인수에 따라 컴파일 시간에 일반 형식 또는 함수를 생성하는 구문' 이라고 나와있다. 그냥 변수 타입이 컴파일 시간에 결정된다고 이해하면 될 것 같다. 사실 우리는 템플릿을 자주 사용해왔다. C++에서 제공하는 백터나 큐, 스택을 사용할때 안에 변수 타입을 적었을 것이다. 이게 바로 템플릿이다. 템플릿은 함수와 클래스에 모두 적용 가능하다. 기본 형식은 아래와 같다. template // 함수 또는 클래스 정의 T는 모든 타입을 포함하는 대단한 녀석이다. 당연히 T 말고 다른 문자를 써도 된다. 먼저 함수 템플릿을 살펴보자. // 함수 템플릿 // 벡터 안에 있는 모든 값의 합을 반환 template T sum(const ve.. [ 자료구조 ] 상속, 보호 타입, 다형성, 추상클래스 오늘은 클래스에서 굉장히 중요한 상속에 대해 자세히 다뤄볼 생각이다. 바로 가보자. 상속이란? 상속이란 말 그대로 물려받는다는 의미다. 여기서 상속해주는 클래스를 부모 클래스, 기본 클래스, 슈퍼 클래스라 부르고 상속받는 클래스를 유도된 클래스, 자식클래스, 서브클래스로 부른다. 자식 클래스는 부모의 멤버를 사용 가능하다. 초간단 예시를 하나 살펴보자. // 부모 class Base { public: // Base type void f() { cout [ 자료구조 ] 복사 생성자 & 배정 연산자, 얕은 복사 & 깊은 복사, 프랜드 함수 & 클래스, 중복된 헤더 피하기 자료구조를 공부하기 위해서는 클래스에 대한 이해가 선행되어 있어야 한다. 그래서 한동안은 클래스에 대한 글이 될 것 같다. 바로 본론으로 들어가자. [1] 메모리 유출(Memory Leak) C++에서는 새로운 메모리 공간이 필요할때마다 new를 통해 자원을 요청할 수 있다. 이를 '동적 할당'이라고 한다. 동적 할당은 스택 메모리가 아닌 힙 메모리를 사용하는 특징이 있다. 여기서 힙 메모리는 자유 저장소(free store)라고 부르기도 한다. 연산자 new는 주어진 타입의 객체를 생성하는데 필요한 메모리를 자유 저장소로부터 동적으로 할당하여 이 객체에 대한 포인터를 반환한다. 그런데 동적으로 할당된 객체들은 할당 후 삭제하지 않으면 문제가 발생할 수 있다. 만약에 새로운 객체 p를 동적으로 할당한 뒤.. [ 자료구조 ] 자료구조 포스팅을 시작하며 오늘부터는 틈틈이 자료구조를 정리할 생각이다. 대학교 강의자료를 그대로 쓰려고 했으나 운영체제를 정리할 때 전공책을 읽으면서 정리하는게 훨씬 효율적일거 같아 전공서적을 하나 구입했다. 내가 공부하는 책은 'C++로 구현하는 자료구조와 알고리즘' 이다. 가격이 무려 38,000 원이나 하는데(원서는 더 비쌈..) 최대한 뽕을 뽑아야겠다. 자료구조 정리를 완료하는 그날까지 달려보자! [ 운영체제 ] HDD 구조, HDD 스케줄링, SSD, 디스크 관리(Disk Management) Hard Disk Drive (HDD) 하드 디스크는 자기 패턴으로 정보를 기록한다. 쉽게 말하면 수많은 CD를 밀집시켜 놓은 구조로 생각하면 된다. 하드 디스크의 구조를 그림으로 살펴보면 아래와 같다. Read-write head : 데이터를 읽고 쓰는 역할을 담당 Disk arm : 헤드를 데이터가 있는 곳으로 움직이는 역할 Spindle : 플래터를 돌려주는 역할 Platter : CD 한 장으로 생각하면 된다. 위, 아랫면에 자기적 성질을 이용해 정보를 저장 Track : 플래터의 동심원 일부 Sector : 하드 디스크의 최소전송 단위로 트랙의 일부분. 섹터의 집합이 트랙이다. 섹터는 고정 크기를 가지는데 2010년까지는 512B, 현재는 일반적으로 4KB의 크기를 가진다 Cylinder : 다.. [ 운영체제 ] 쓰레싱(Thrashing)과 작업 공간(Working Set), 지역성(Locality) 메모리 파트에서 중요한 개념을 하나 놓쳐서 급히 쓴다. 쓰레싱과 작업 공간에 대해 자세히 다뤄보자. 두 가지 개념을 완벽하게 이해하는게 이 글의 학습목표! [1] 쓰레싱 (Thrashing) 쓰레싱을 간단하게 정리하면 'Page Fault가 시스템의 허용 수준을 넘어가는 현상' 으로 요약할 수 있다. Page fault가 많이 발생하는 경우는 두 가지로 나눌 수 있다. 1) 메모리 허용량보다 더 많은 프로세스를 동시에 실행하려고 할 때 말 그대로 메모리 용량을 초과하는 경우다. 이렇게 되면 많은 프로세스 중에 일부만 메모리 위에 올라가고, 나머지는 저장장치 안에 있게 되므로 스케줄링이 계속 됨에 따라 page fault 가능성이 매우 높아진다. 2) 스케줄러가 CPU 이용률만 보고 계속해서 새로운 프로세.. [ 운영체제 ] 가상 메모리2 - Modify bit(Dirty bit), 페이지 교체 알고리즘 운영체제에는 다양한 페이지 교체 알고리즘이 있다. 페이지 교체 알고리즘이 필요한 이유는 page fault ratio를 낮추기 위해서지만, 근본적인 원인은 메인 메모리의 용량이 한정적이기 때문이다. Page Fault가 발생했는데 메인 메모리가 가득 찼다면 페이지를 교체해야 한다. 여기서 교체 대상이 되는 페이지를 'victim page'라고 한다. 위 그림을 보면 victim 페이지가 SSD에 swap out 되고, 페이지f 가 swap in 됐다. 페이지 테이블에서 valid bit의 변화를 보면 victim 페이지는 i로, 페이지f 는 v로 수정됐다. 즉, victim 페이지는 메인 메모리 상에 없다는 뜻이고, 페이지f 는 메인 메모리 상에 있다는 뜻이다. Valid bit는 찾고자 하는 페이지가 .. 이전 1 2 3 4 5 6 다음
