DAY003. Computer Sciensce & Data Structuer & Algorithm
컴퓨터
- 운영체제
- 여러 종류의 하드웨어를 공통적으로 제어하기 위해 만들어짐
- 종류 : UNIX, Linux, Windows 등
– 시스템 하드웨어 관리 -> 사용자 프로그램의 오류나 잘못된 자워 사용을 감시, 입출력장치 등이 자원에 대한 연산과 제어를 관리
– (가상)시스템 서비스 제공 -> 사용자에게 컴퓨터의 ㅍ로그램을 쉽고 효율적으로 실행할 수 있는 환경 제공
– 자원관리 -> 컴퓨터 시스템 하드웨어 및 소프트웨어 자원을 여러 사용자간에 효율적 할당, 관리, 보호 - 자원관리
– 프로세스 -> 보조기억장치에 있던 프로그램이 주기억장치에서 실행이 되는것.
– 프로세스 상태 -> 생성, 준비, 실행, 대기, 종료.
– 프로세스 스케줄링 - FCFS(FirstComeFIrstServed) -> 도착 순서에 따라 차례로 실행
- SJF(ShortestJobFirst) -> 실행시간이 짧은 프로세스가 먼저 실행, 실행시간이 긴 프로세스는 무한 대기 발생
- RoundRobinScheduling -> 시분할 시스템을 위해 고안된 방식, FCFS 기법 변형, 완료되지 않으면 가장 뒤로 배치. 할당된 시간이 클수록 FCFS와 유사, 할당시간이 작을수록 문맥교환과 오버헤드가 발생.
오버헤드(overhead)는 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등을 말한다. 예를 들어 A라는 처리를 단순하게 실행한다면 10초 걸리는데, 안전성을 고려하고 부가적인 B라는 처리를 추가한 결과 처리시간이 15초 걸렸다면, 오버헤드는 5초가 된다. (출처 : https://ko.wikipedia.org/wiki/%EC%98%A4%EB%B2%84%ED%97%A4%EB%93%9C )
- PriorityBasedScheduling -> 프로세스마다 우선순위 부여, 우선순위 동일시 FCFS기법으로 할당, 우선순위낮은 프로세스는 무한 대기 발생.
- MultiQueueScheduling -> 프로세스를 특정 그룹으로 분류할수 있는 경우 각 그룹에 따라 다른 준비단계 사용
– 주기억장치 관리 -> 단순관리, 가상메모리<보조기억장치를 주기억장치처럼 활용>
– 파일관리 -> 운영체제에서 파일 입/출력 요청을 받아 보조기억장치로 부터 파일 입/출력 처리를 함.각각의 운영체제마다 파일시스템이 다름. - 커널 -> kernel 운영체제의 핵심 및 정체성, 보안, 자원관리, 추상화
컴퓨터 과학에서 커널(kernel)은 운영 체제의 핵심 부분으로서, 운영 체제의 다른 부분 및 응용 프로그램 수행에 필요한 여러 가지 서비스를 제공한다. 핵심(核心)[1]이라고도 한다. (출처 : https://ko.wikipedia.org/wiki/%EC%BB%A4%EB%84%90_(%EC%BB%B4%ED%93%A8%ED%8C%85) )
자료구조
– 자료를 효율적으로 이용할 수 있는 방법론 – 데이터를 구조적으로 표현하는 방법- 원시구조 -> 정수, 실수, 문자 // 단순구조로 자료형에 따른 분류.
- 선형구조 -> 배열, 연결리스트, 스택, 큐, 덱 //자료간의 관계가 1 대 1인 구조
비선형구조 -> 트리, 그래프 // 자료간의 관계가 1대 다인 구조.
연결리스트 -> 단순연결리스트, 이중연결리스트, 원형연결리스트
단순연결리스트 - 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.
이중연결리스트 - 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.
원형연결리스트 - 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트이다.
– Stack -> FILO (데이터를 넣음 Push, 데이터를 가져옴 Pop)
– Queue -> FIFO (데이터를 넣음 Put, 데이터를 가져옴 Get)
– Dequeue (double ended queue) //양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조이다.– Tree -> 나무를 뒤집어 놓은 듯한 모양으로 생긴 구조, root가 있음. 자식간에는 연결되지 않음. 검색/탐색에 이용
개인적으로 Tree는 다단계에서 주로 사용하는 모양과 거의 동일. 흔히 가계도 표현할때 많이 사용.
– Graph -> 각각의 노드가 자유로이 연결, root없음. 부모자식의 개념없음. 관계에 이용
트리와 그래프는 다음 url 참조 http://www.ktword.co.kr/abbr_view.php?id=506&m_temp1=3980&nav=2, http://dblab.duksung.ac.kr/ds/pdf/Chap10.pdf)
알고리즘
– 문제 해결을 위한 절차/방법
– 어떠한 문제를 해결하기 위한 여러동작들의 모음
- 일을 처리하는 방법/순서
대표적 알고리즘 - 정렬, 탐색, 재귀 등
정렬 알고리즘 -> 선택정렬, 버블정렬, 삽입정렬, 병합정렬, 퀵정렬
선택 정렬 (Selection Sort) - 가장 큰 또는 가장 작은 자료를 선택하는 과정을 반복적으로 수행
.. 첫째 루프에서 첫째 자료와 나머지들과 비교하여 제일 작은 자료와 위치 교환,
.. 첫째 루프에서 둘째 자료와 나머지들과 비교,위치 교환을 해가며 반복 정렬됨
버블 정렬 (Bubble Sort) - 두 인접한 원소를 검사하여 정렬
.. 첫째 루프에서 첫째 자료와 나머지를 순차적으로 비교하여 가장 큰 자료를 맨 뒤로 보냄
.. 총 루프는 자료의 갯수 만큼 반복
삽입 정렬 (Insertion Sort) - 원래 배열 첫 원소부터 뽑아서, 적절한 위치에 삽입하면서 반복 수행
. for 루프 마다,
.. Data[1,..,j-1]은 정렬된 배열이 되고,
.. Data[j+1,…,n]은 아직 미정렬 배열이 됨
병합 정렬 (Merge Sort)
..리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
..정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
..각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
..두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
퀵 정렬 (Quick Sort)
..리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
..피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
..분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.시간복잡도 -> 알고리즘이 실행되는데 소요되는 시간분석, 점근표기법(대문자O표기법)
ㅇ 소요되는 기본 연산 수에 따름
- 주로, 알고리즘이 사용한 기본 연산의 수에 따름
. 주요 기본 연산 : 정수의 비교,덧셈,곱셈,나눗셈 등
. 총 실행시간이 기본 연산의 수행 수에 거의 비례적임 - 따라서, 입력 크기의 함수로 기본 연산 수를 구함으로써 시간 효율성 분석이 가능
ㅇ 시간 복잡도 표기 : big-O, big-Omega, big-Theta
- 전체 값 계산에 가장 큰 영향을 주는 항 만 고려한 표기법
. 例) n2 + n + 1 => O(n2)
- 주로, 알고리즘이 사용한 기본 연산의 수에 따름
탐색알고리즘 -> 선형탐색, 이진탐색
선형검색(혹은선형탐색, 순차탐색, Linear Search)은주어진데이터에서키값에의하여데이터를찾는 과정이다. 검색방법중가장간단하다.
이진검색(Binary Search)은 데이터가 정렬되어 있는 상태에서 사용하는 방법으로 가운데 값을 기준으로 비교하여 검색하는 방법으로 리스트를 1/2로 줄이는 방법.
특이사항
MarkDown 문서 작성할 수 있는 편집기 다운받음.
수업내용 정리를 그쪽에서 할 수 있도록 할 예정.
편집기를 사용할지 웹사이트에서 제공되는 것을 사용할지 고민중.