본문 바로가기

전체 글

 (30)
자료구조와 알고리즘 with 파이썬 chapter8. 그래프 08-1 그래프란?그래프 : 복잡하게 연결된 객체 사이의 관계를 효율적으로 표현할 수 있는 자료구조. 그래프는 정점의 집합과 간선의 집합으로 구성되므로 수학적으로 G = (V, E)와 같이 표시. 정점들은 자체로는 큰 의미가 없지만, 이들을 간선으로 연결하면 관계가 만들어지고 그래프가 형성된다. 그래프의 종류무방향 그래프 : 두 정점을 연결하는 간선에 방향성이 없는 그래프. 간선은 양방향으로 갈수 있는 길. (A, B)로 표현방향 그래프 : 다이그래프라고도 한다. 간선은 한 방향으로만 갈 수 있는 길. 로 표현. 와 는 서로 다른 간선. 완전 그래프 : 그래프의 모든 정점 사이에 간선이 존재하는 그래프. 정점이 n개인 무방향 완전 그래프는 n * (n-1)/2개의 간선을 갖고, 방향 그래프는 n * (n..
자료구조와 알고리즘 with 파이썬 chapter07. 탐색 07-1 탐색이란?탐색 : 데이터의 집합에서 원하는 조건을 만족하는 데이터를 찾는 작업. 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업. 레코드 : 탐색을 위한 대상테이블 : 레코드의 집합키 : 탐색의 기준에 되는 필드(탐색키)07-2 순차탐색순차 탐색 : 일렬로 늘어선 자료중에서 원하는 킷값을 가진 레코드를 찾는 알고리즘. 테이블의 각 레코드를 처음부터 하나씩 순서대로 검사하여 원하는 레코드를 찾는다. 레코드들이 무질서하게 섞여 있어도 항상 원하는 레코드를 찾을 수 있다. def sequential_search(A, key, low, high): for i in range(low, high+1): if A[i] == key: return i return -1순차 탐색은 ..
혼공 컴+운 chapter13. 교착 상태 13-1. 교착 상태란식사하는 철학자 문제- 동그란 원탁에 다섯 명의 철학자가 앉아 있다. 이 철학자들 앞에는 맛있는 식사가 있고, 철학자들 사이 사이에는 식사에 필요한 포크가 있다. 그리고 철학자들 앞에 있는 식사는 두 개의 포크로 먹을 수 있는 음식이라 가정.이 철학자들은 아래와 같은 순서로 식사를 한다.계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다.식사 시간이 끝나면 오른쪽 포크를 내려놓는다.오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.다시 1번부터 반복한다.모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황이 ..
혼공 컴+운 chapter12. 프로세스 동기화 12-1. 동기화란동기화의 의미동시다발적으로 실행되는 많은 프로세스는 서로 데이터를 주고받으며 협력하며 실행될 수 있다. 협력적으로 실행되는 프로세스들은 올바른 실행을 위해서 동기화가 필수다. 프로세스 동기화 : 프로세스들 사이의 수행 시기를 맞추는 것. 실행 순서 제어 : 프로세스를 올바른 순서대로 실행하기상호 배제 : 동시에 접근해서는 안 되는 자원에 하나의 프로세스만 접근하게 하기.실행 순서 제어를 위한 동기화 : 동시에 실행되는 프로세스를 올바른 순서대로 실행하는 것상호 배제를 위한 동기화 : 공유가 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘. 동시에 접근해서는 안 되는 자원에 동시에 접근하지 못하게 하는 것. 생산자 소비자 문제공유 자원과 임계 구역공유 자원 : 전역변수, 파일,..
자료구조와 알고리즘 with 파이썬 chapter6. 정렬 06-1. 정렬이란?정렬 : 순서가 없는 사물들을 순서대로 나열하는 것. 정렬을 위해서는 사물들을 서로 비교할 수 있어야 한다. 같은 정렬 기준을 사용하더라도 오름차순과 내림차순으로 나열가능정렬 관련 용어레코드 : 정렬시켜야 할 대상. => 여러 개의 필드로 이루어진다. 정렬의 기준이 되는 필드를 키 또는 정렬 키 라고 부른다. 정렬이란 레코드들을 키의 순서로 재배열하는 것. 알고리즘이 단순하면 일반적으로 비효율적이다. 삽입정렬, 선택 정렬, 버블 정렬 등이 대표적인 예이다.효율을 높이기 위해서는 복잡한 알고리즘을 사용해야 한다. 대표적인 방법으로 퀵정렬, 힙 정렬, 병합 정렬, 기수 정렬, 팀 정렬 등이 있다. 안정성 : 입력 데이터에 같은 킷값을 갖는 레코드가 여러 개 있을 때, 정렬 후에도 이들의 ..
혼공 컴+운 chapter11. CPU 스케줄링 11-1. CPU 스케줄링 개요- CPU 스케줄링 : 운영체제가 프로세스들에게 공정하고 합리적으로 CPU자원을 배분하는 것.프로세스 우선순위프로세스마다 우선순위가 다르다. 우선순위가 높은 프로세스란 빨리 처리해야 하는 프로세스들을 의미한다. 우선순위가 높은 프로세스에는 대표적으로 입출력 작업이 맣은 프로세스가 있다.대부분의 프로세스들은 CPU와 입출력장치를 모두 사용하며 실행입출력 집중 프로세스 : 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스.(실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무르게 된다.)CPU 집중 프로세스 : 복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스. ( 대기 상태보다는 실..
혼공 컴+운 chapter10. 프로세스와 스레드 10-1. 프로세스 개요- 보조기억 장치에 저장된 프로그램을 메모리에 적재하고 실행하는 순간 그 프로그램은 프로세스가 된다. 이 과정을 프로세스를 생성한다라고 표현프로세스 직접 확인하기포그라운드 프로세스 : 사용자가 보는 앞에서 실행되는 프로세스백그라운드 프로세스 : 사용자가 보지 못하는 뒤편에서 실행되는 프로세스백그라운드 프로세스: 사용자와 직접 상호작용데몬/ 서비스 : 사용자와 상호작용하지 않는 백그라운드 프로세스프로세스 제어 블록CPU자원은 한정되어 있기 때문에 프로세스들은 차례대로 돌아가며 한정된 시간 만큼만 CPU를 이용.운영체제는 빠르게 번갈아 수행되는 프로세스의 실행 순서를 관리하고, 프로세스에 CPU를 비롯한 자원 배분.프로세스 제어 블록 (PCB) : 프로세스와 관련된 정보를 저장하는 자..
혼공 컴+운 chapter9.운영체제 시작하기 09-1. 운영체제를 알아야 하는 이유운영체제란- 시스템자원 : 프로그램 실행에 마땅히 필요한 요소들. ex) CPU, 메모리, 보조기억장치, 입출력장치 등운영체제 : 프로그램이 올바르게 실행되도록 돕는 특별한 프로그램 => 메모리에 적재컴퓨터가 부팅될 때 메모리 내 커널 영역이라는 공간에 따로 적재되어 실행.사용자 영역 : 커널 영역을 제외한 나머지 영역, 사용자가 이용하는 응용 프로그램이 적재되는 영역운영체제는 실행할 프로그램을 메모리에 적재하고, 더 이상 실행되지 않는 프로그램을 메모리에서 삭제하며 지속적으로 메모리 자원을 관리한다. 운영체제는 최대한 공정하게 여러 프로그램에 CPU 자원을 할당한다. 응용 프로그램과 하드웨어 사이에서 응용 프로그램에 필요한 자원을 할당하고, 응용 프로그램이 올바르게..

티스토리툴바