Computer Science

[알고리즘] 정렬

| 정렬이란 - 특정 값을 기준으로 데이터를 순서대로 배치하는 방법 - 기본 : 버블, 삽입, 선택 - 비교적 속도가 빠른 정렬 : 합병, 힙, 퀵, 트리 - 하이브리드 정렬 : 팀, 블록병합, 인트로 - 기타 : 기수, 계수(카운팅), 셸, 보고 | 정렬의 시간복잡도 요약 - 안정성이라는 것은, 어떤 데이터 { 1, 2, 3, 1, 1, 1 } 을 정렬한다고 할 때, 같은 숫자 1에 대해서 { 1, 1, 1, 1 } 의 순서가 유지되도록 정렬되는 것을 '안정성이 있다'라고 한다. - 아래의 보조 메모리는 추가적으로 드는 메모리를 이야기하는데, 버블이나 삽입, 선택의 경우 swap시에 드는 변수 1개만 필요하기 때문에 보조메모리가 1개만 소요된다. 정렬 방법 시간 복잡도 보조 메모리 안정성 Ω(n) Θ(..

[알고리즘] 알고리즘 개요

| 알고리즘이란? 알고리즘이란, 어떤 문제를 해결하기 위한 절차나 방법을 말한다. - 알고리즘의 조건 입력 데이터의 입력 출력 처리 후 출력 명확성 동작의 흐름(flow)에 대한 명확성 유한성 정해진 시간 및 공간 내에서의 처리 효율성 같은 동작을 하더라도 시간 및 공간 면에서 보다 효율적이어야 한다. | 알고리즘은 결국 정확성과 시간 복잡도, 공간 복잡도를 말한다. - 어떻게 보다 적은 자원을 효과적으로, 정확하게 만들어 내느냐가 알고리즘의 핵심 | 알고리즘 정리 개요 - 앞으로 정리할 알고리즘 목록입니다. - (글 작성 후 링크 업로드 예정) 정렬 이진탐색 / 투 포인터 그리디 알고리즘 분할 정복 / 다이나믹 프로그래밍 백 트래킹 최단 경로 최소 신장 트리 [ 참고 및 출처 ] 부트 캠프 강의를 들은..

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

| 들어가기 전에 - 왜 우선순위 큐는 비선형 구조일까? : 큐는 선형구조로 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 *..