봄봄.devlog

1. 유닉스 시스템의 구성 1) 커널 - 유닉스의 가장 핵심적인 부분 - 하드웨어를 보호(캡슐화)하고, 프로그램들과 하드웨어 간의 인터페이스 역할을 담당함. - 프로세스 관리, 기억장치 관리, 파일 관리, ... 여러 가지 기능을 수행함 2) 쉘 - 사용자의 명령어를 인식하여 프로그램을 호출하고, 명령을 수행하는 명령어 해석기 3) 유틸리티 - 일반 사용자가 작성한 응용 프로그램을 처리하는데 사용함 2. 유닉스의 주요 명령어 1) fork : 새로운 프로세스 생성(하위 프로세스 호출, 프로세스 복제) 2) cat : 내용을 화면에 표시 3) chmode : 파일의 사용 허가 지정 4) chown : 소유자 변경 5) ls : 현재 디렉터리 내의 파일 목록 확인 6) getpid : 자신의 프로세스 아이디..

1. 국부성(Locality) 실행중인 프로세스가 주기억장치를 참조할 때는 일부 페이지만 집중적으로 참조하는 성질이 있다는 이론 1) 시간 구역성 : 하나의 페이지를 일정 시간 동안 집중적으로 액세스하는 현상 2) 공간 구역성 : 일정 위치의 페이지를 집중적으로 액세스하는 현상 2. 스래싱(Thrasing) 프로세스의 처리 시간보다 페이지 교체 시간이 더 많아지는 현상을 말한다. 3. 디스크 스케줄링 목적 : 처리량 최대화, 평균 응답 시간의 최소화, 응답 시간 편차의 최소화 1) FCFS(First Come First Service) 2) SSTF(Shortest Seek Time First) - 탐색 거리가 가장 짧은 트랙에 대한 요청을 먼저 서비스하는 기법 - 현재 헤드 위치에서 가장 가까운 거리에..

1. 선점 스케줄링의 종류 1) SRT(Shortest Remaining Time) - 비선점 기법이 SJT 알고리즘을 선점 형태로 변경한 기법 - 현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당하는 방법 2) RR(Round Robin) - 시분할 시스템을 위해 고안된 방식으로, FCFS 알고리즘을 선점 형태로 변형한 기법 - FCFS 기법과 같이 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만 각 프로세스는 할당된 시간 (Time Slice, Quantam) 동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치됨. - 할당되는 ..

1. 운영체제 개요 1) 정의 - 컴퓨터 시스템의 자원들을 효율적으로 관리하며, 사용자가 컴퓨터를 편리하고 효과적으로 사용할 수 있도록 환경을 제공하는 여러 프로그램의 모임 - 종류 : Windows, MS-DOS, UNIX, Linux 2) 기능 - 프로세스 관리 - 프로세서, 기억장치, 입출력장치, 파일 및 정보 등의 자원 관리 - 자원의 효과적인 경영 스케줄링 기능 제공 - 사용자와 시스템 간의 편리한 인터페이스 제공 2. 운영체제 운용 기법 및 발달 과정 - 일괄처리시스템 : 일정량 또는 일정 기간 동안 데이터를 모아서 한꺼번에 처리하는 방식 - 다중 프로그래밍 시스템 : 하나의 CPU와 주기억장치를 이용하여 여러 개의 프로그램을 동시에 처리하는 방식 - 시분할 시스템(=라운드 로빈) : 여러 명..

1) 전위순회(preorder) : 중앙 -> 왼 -> 오 2) 중위순회(inorder) : 왼 -> 중앙 -> 오 3) 후위순회(postorder) : 왼 -> 오 -> 중앙 📌 알아둘 것 Tree 클래스를 구현(add, search, preorder, ...) 하면 코드가 간단해서 쉽다. 하지만 트리의 높이가 높아질수록 노드 탐색을 할 때 깊게 들어가야 하므로 스택 오버플로우가 발생할 가능성이 크다 따라서 반복문이나 스택을 사용할 수도 있다

📖 정의 - 방향성을 거스르지 않고 유향 그래프의 정점을 나열하는 방법 - 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 위해 사용하는 알고리즘 - 여러 개의 답이 존재할 수 있다. 📌 조건 - DAG(Directed Acyclic Graph)에만 적용 가능 - 사이클이 발생하는 경우 시작점이 불분명하므로 위상 정렬 불가 📌 구현 방법 1) Stack / DFS 이용 2) Queue 이용 진입 차수가 0인 정점을 queue에 삽입 queue에서 원소를 꺼내 연결된 모든 간선 제거 간선 제거 후 다시 1부터 반복 Point! 모든 정점을 방문했다면 queue에서 꺼낸 순서가 위상 정렬의 결과 모든 정점을 방문하기 전에 queue가 비면 사이클이 존재 -> 위상 정렬 불가 수행시간 O(V+E)..

[ DP 문제 풀이법 ] 1. 문제를 보고 규칙을 찾아서 점화식을 만든다. 2. 점화식을 이용하여 Top Down(재귀함수) 또는 Bottom Up(반복문) 방식으로 문제를 푼다. 왜 DP문제를 많이 풀어보라고 그러는지 알겠다...ㅠㅠ https://odysseyj.tistory.com/22 https://jyami.tistory.com/15

힙정렬(Heap Sort) 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로 한 정렬 방식 퀵정렬과 병합정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도가 높지는 않다. 하지만 힙 자료구조가 많이 활용되고 있는 것은 사실! * 힙정렬 활용 1. 가장 크거나 가장 작은 값을 구할 때 최소힙 또는 최대힙의 루트값이기 때문에 한번의 힙 구성을 통해 구하는 것이 가능하다. 2. 최대 K만큼 떨어진 요소들을 정렬할 때 삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있다. 시간복잡도 ■ heapify 함수 수행 시간 heapify 함수는 힙 구조를 만들기 위해 이진 트리에서 자식 노드와 순서를 바꾸는 재귀호출을 한다. 힙 이진 트리의 높이는 logN이다. 따라서 heapify 함수의 재귀호출 횟수는 log..