전체 글

[비선형 자료구조] 힙과 우선순위 큐

| 들어가기 전에 - 왜 우선순위 큐는 비선형 구조일까? : 큐는 선형구조로 1 : 1의 대응방식을 가진다. 앞에서 부터 데이터를 꺼내고, 뒤에서부터 데이터를 축척한다. : 우선순위 큐는 이러한 큐에 우선순위 개념을 추가한 형태로, 우선순위를 따져 우선순위가 높은 데이터를 먼저 뽑는다. : 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능한데 이중에서 힙으로 구현을 하는 것이 가장 효율적이다. : 따라서, 자바에서도 우선순위 큐는 힙으로 구현되었다. 힙은 완전 이진 트리 형태이며, 이는 1 : N 관계를 갖는 비선형구조이다. - 자바에서는 우선순위 큐를 힙으로 구현한다. 왜? : 위에서도 잠시 언급했던 것처럼, 힙으로 큐를 구현하는 것이 가장 효율적이기 때문에, 자바도 구현방식으로 힙을 쓴다. - 배..

[비선형 자료구조] 트리와 그래프

| 요약 핵심 단어 핵심 특성 언제 쓰면 좋을까 트리 계층, Acyclic, 4가지의 순회 포화 이진 트리의 경우, 하위로 갈수록 노드의 갯수가 2^0, 2^1, 2^2..로 증가 계층 관계의 데이터를 다룰 때 그래프 네트워크, cyclic, DFS/BFS 루트가 없고, 각 정점들간 단방향 또는 양방향의 관계를 가질 수 있음 연관 관계를 가진 데이터들에서 최적의 결과를 찾아야할 때 | 트리와 그래프의 차이 트리 그래프 개요 그래프의 한 종류 정점(vertex, 노드)과 간선(edge)으로 이루어진 자료구조 그림 출처 : 위키백과 출처 : 위키백과 방향 (단)방향 그래프 무(양)방향, (단)방향 그래프 사이클 Acyclic Cyclic 모델 계층 모델 네트워크 모델 루트 최상위 노드 없음 상-하위 관계 인..

비선형 자료구조 총정리

보호되어 있는 글입니다.

[운영체제] 파일 시스템

| 파일 시스템 운영체제가 저장매체에 파일을 쓰기 위한 자료구조 및 알고리즘 1) 파일은 어떻게 만들어진 걸까? - 0과 1만으로 이루어진 비트 데이터를 그대로 저장하면 관리하기 어렵다. - 따라서 블록으로 (ex. 4kb) 데이터를 나눠 저장한다. (블록에 고유 번호 부여) - 블록의 고유 번호도 구분하기 어려우니, 추상적인 객체가 필요하다. (객체 : 파일) - 그렇게 파일이 만들어졌다. 2) 저장 방법 - 가능하면 연속적인 공간에 저장하는 것이 좋지만, 외부 단편화*나 파일 사이즈 변경 문제로 어렵다. - 그렇기에 자료구조로 연결리스트를 사용한다. * 외부 단편화 : 총 메모리 공간이 남았으나, 남아있는 공간이 연속적이지 않아서 발생하는 현상 3) 다양한 파일 시스템 - 인도우는 FAT이라는 자료구..

[운영체제] 가상 메모리와 페이징 시스템

보호되어 있는 글입니다.

[운영체제] 스레드 - 동기화, 뮤텍스/세마포어, 데드락/스타베이션

| 쓰레드란? - Light Weight Process - 어떠한 프로그램 내에서, 특히 프로세스 내에서 실행되는 흐름의 단위 | 프로세스와 쓰레드의 차이점 프로세스 스레드 차이점 프로세스 간에 독립적이다 프로세스의 서브셋 각각의 프로세스가 독립적인 자원 가짐 프로세스 자원 공유 프로세스 자신만의 주소영역을 가짐 스레드는 주소 영역을 공유한다 IPC 기법으로 통신 가능 별도의 통신 기법이 필요 없다 | 스레드 장단점 정리 내용 추가 설명 장점 성능 향상 멀티 스레드로 병렬 처리 응답성 향상 다수의 사용자의 요청이 오거나, 여러개의 처리와 동시에 요청이 이루어질 때 응답성이 향상 자원 공유 효율 프로세스 내부에서 스레드 간 자원 공유(IPC X) 단점 한 스레드가 프로세스 전체에 영향을 준다 멀티 프로세스..

[운영체제] 프로세스와 스케줄러

보호되어 있는 글입니다.

[운영체제] 운영체제란? 커널, 시스템 콜, 커널 모드

| 요약 - 운영체제는 커널 + 기타 기능 - 운영체제는 시스템 콜을 제공 (쉘은 사용자와 OS간 인터페이스) - 프로그램 언어별로 OS별 API를 제공 - 응용 프로그램에서 API로 시스템 콜 호출 시, 커널 모드로 변환, OS내부에서 명령 처리 후 리턴 | 운영체제란? 운영체제 (OS : Operating System) : 사용자의 편의를 위한 환경을 제공하는 시스템 소프트웨어 - 종류 : 윈도우, 유닉스 계열(리눅스), MacOS - 운영체제는 일반적으로는 커널에 여러가지가 추가된 상태를 의미하지만, 좁은 의미로 "커널(kernel)" 자체를 말합니다. pf. General Purpose OS vs Embeded OS General Purpose OS Embeded OS 컴퓨터에서 사용되는 OS *..

객체지향 언어의 특징 4_캡슐화 (정보 은닉)

| 캡슐화 (정보 은닉) 앞에서 상속과 다형성을 이야기할 때, 캡슐화의 원칙에 대해 언급했었다. - 상속의 단점으로 상위 객체의 정보가 하위 객체에서 노출될 수 있고, 그것은 곧 캡슐화의 원칙을 깨는 것이라고 했다. - 다형성 또한 instanceof를 통해 부모가 참조하고 있던 실제 자식 인스턴스를 외부에서 노출하면 캡슐화의 원칙이 깨졌다. 여기에서도 유추할 수 있는 캡슐화의 의미는 "정보 은닉"이다. 캡슐화 : 정보를 객체 내부로 숨겨 외부로부터 감추는 것 | 접근 제어자와 참조변수 1. 접근 제어자의 UML 표현 - private 자기 자신만 접근 가능 ~ default 같은 패키지 내 # protected 상속 또는 같은 패키지 내 + public 모두가 접근 가능 _ static - - 캡슐화를..

객체지향 언어의 특징 3_다형성 (사용 편의성)

| 다형성 (사용 편의성) 다형성이란, 하나의 객체가 여러가지 타입을 가질 수 있는 것을 의미한다. 다형성은 오버로딩과 오버라이딩을 통해 구현할 수 있다. 오버라이딩이 가능한 이유는 뭘까? 그건 동적 바인딩 때문이다. 여기서 동적 바인딩이란 메서드가 실행 시점에서 성격이 결정되는 것을 말한다. 종류 정적바인딩(static binding) 동적바인딩(Dynamic binding) 정의 컴파일 시간에 성격이 결정 실행 시간(런타임)에 성격이 결정 예시 C언어 컴파일 시간에 변수의 데이터타입이 결정 ex. int *p; -- 미리 데이터타입 지정 javascript 런타임에 값에 따라 변수의 데이터타입 결정 ex. var c = 1; -- 미리 데이터타입 지정x ex. Person p = new Person(..