코드없이 보는 데이터+알고리즘

출처- 코드없이 보는 알고리즘

---

데이터구조

1 데이터 구조 알고리즘 기본 자료형 빅 오(o)표기법
2 선형 데이터 구조인 배열,연결 리스트,스택,큐를 설명한다.
3 트리와 트리 기반 데이터 구조를 설명
4 해시 데이터 구조를 소개한다
5 그래프의 기초를 간략하게 설명한다

알고리즘

6 선형 탐색 이진 탐색
7 정렬 알고리즘이 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬을 설명한다
8탐색 알고리즘이 너비 우선 탐색, 데이크스트라 알고리즘, A*알고리즘
9군집 알고리즘이 K-평균 알고리즘과 K-최근접 이웃 알고리즘을 소개하고, 머신러닝과 신경망을 간단히 살펴본다

알고리즘과 데이터구조를 이해하는데 필요한 지식들

10무작위성 개념에 대한 몇가지 기본 지식을 설명한다
11스케줄링 알고리즘인 선착순 스케줄링, 최단 작업 우선 스케줄링, 우선순위 스케줄링,라운드 로빈 스케줄링, 다단계 큐 스케줄링 ,다단계 피드백 큐 스케줄링을 설명한다
12문제 해결에 적당한 알고리즘 구조를 정립하는 단계인 알고리즘 기획과 설계에 사용하는 순서도와 유사코드를 소개

데이터구조

알고리즘,자료형,빅 오 표기법

선형 데이터 구조
컴퓨터 메모리,선형 데이터 구조의 개요,배열,리스트,스택,큐,우선순위 큐
트리 데이터 구조
트리,이진 트리, AVL 트리, RB 트리,B 트리,힙

해시데이터 구조

해시와 해시함수,해시테이블, 컴퓨터 보안기초, 컴퓨터 보안에서의 해시의 역할, 해시와 순환 중복 검사, 해시와 다른 용도

그래프

차원,점,선,그래프,그래프vs트리,무향 그래프와 유향 그래프, 가중치 그래프, 그래프와 소셜 네트워크 서비스, 그래프 데이터베이스

알고리즘

선형 이진 탐색

정렬 알고리즘

정렬 알고리즘의 특징, 버블 정렬,선택 정렬, 삽입 정렬, 셸 정렬, 병합 정렬, 퀵 정렬, 힙 정렬, 버킷 정렬, 기수 정렬,

경로 탐색 알고리즘

너비 우선 탐색, 깊이 우선 탐색, 데이스트라 알고리즘, A*알고리즘

군집화 알고리즘

K-평균 알고리즘,K-최근접 이웃 알고리즘,머신러닝,신경망,딥러닝

데이터 구조와 알고리즘을 이해하는 데 필요한 지식들

무작위성

무작위,하드웨어 이해하기,유사 나수,참난수 생성기

스케줄링 알고리즘

운영체제,인터럽트와 인터럽트 서비스 루틴,유한 상태 기계,커널,프로세스,스레드,작업,메모리 관리 장치,작업제어블록,스케줄러와 스케줄링

알고리즘 기획과 설계

타당한 기획과 설계의 필요성 알고리즘의 3단계 순서도 프로그램 구조 유사코드

---

데이터 구조와 알고리즘, 자료형 빅 오 표기법

• 함수,메소드,프로시저, 서브루틴

프로그래밍에서의 함수는 매개변수(파라미터) 또는 인수라고 하는 데이터를 입력으로 하용하며 때로는 결괄르 반환하기도한다
C기반의 프로그래밍 언어에서는 이를 void함수라고 한다

객체지향 프로그래밍 언어oopL에 속하는 프로그래밍 언어에는 다른 코드의 청사진 역할을 하는 특수학 코드가 존재한다 이를 클래스라고 하며 함수를 메소드라고 한다

일부 프로그래밍 언어에서는 함수를 프로시저 또는 서브루틴이라고 한다.

함수,메소드 ,프로시저,서브루틴은 목적이 같다

재귀와 반복

최대재귀깊이:재귀 함수가 자기 자신을 호출하는 횟수간 늘어날수록 컴퓨터의 가용 메모리 공간은 점점줄어들어 슽택오버플로 에러가생긴다

반복:컴퓨터가용 메모리의한계 때문에 반복의종료 조건을 지정하지않으면 프로그램 에러가 발생한다

분할정보 알고리즘

탐욕알고리즘
동적프로그래밍

알고리즘 분석 - 시간복잡도와 공간복잡도가 있다

시간복잡도: 주어진 입력에 따라 알고리즘이 문제를해결할 때걸리는시간을 뜻한다
공간 복잡도: 알고리즘이 문제를해결할 때 점유하는 컴퓨어틔 메모리 공간을 뜻한다

빅오표기법

빅 오메가, 빅 오,리틀 오,세타등 다양한 표기법이 존재한다

빅오표기법

대문자O는 시간 복잡도의 정도를 나타내는 표기법인차수라고한다

O(1)상수형 알고리즘이며, 데이터입력량과 무관하게 실행 시간이 일정핟
O(n)선형 알고리즘이며, 데이터 입렭량에비례하여 실행시간이 늘어난다
O(logn)로그형 알고리즘이며, 선형적으로 증가하면, n이기하급수적으로 증가한다
O(logn)선형-로그형 알고리즘이며, 데이터 입력량이 n배 증가하면 실행시간이 n배 조금 넘게늘어난다
O(nlogn)선형-로그형 알고리즘,데이터 입력량이 n배 늘어나면, 실행시간이 n배 조금 넘게 늘어난다
O(n제곱) ,O(2의 n승),O(n!):계승(팩토리얼)형 알고리즘이며,데이터 입력이 추가될 때마다 실행시간이 n배로 늘어난다

수형 알고리즘이 O(1)의 성능이 가장 좋고 계승(팩토리얼)형 알고리즘인 O(n!)의 성능이 가장 나쁘다

컴퓨터 메모리

컴퓨터가 처리 중이거나 처리를 끝낸 데이터를 저장할 수 있는 공간을 말한다.

메모리의 본질은 컴퓨터의 저장공간이다

컴퓨터 메모리는 계층적으로구성되어 있고, 각 계층을 이루는 메모리 유형마다 정해진 역할이 있다

적층구조

레지스터<캐시<메인 메모리< 하드 디스크

메모리의 계층 구조의 최하단 요소는 하드 디스크이다
SDD HDD와같이 저장장치가 있으며, 이들을 디스크 저장장치 또는하드디스크라고 한다.하드 디스크는 메인 메모리인 RAM에 적재되는 데이터를 저장한다

RAM에 적재된 데이터는 CPU 칩에 내장된 캐시라는 메모리 유형에 적재된 후, 결국 CPU가 처리 중인 데이터를 저장하는 레지스터에 적재된다.

연산처리 속도
하드디스크<메인메모리(RAM)<L2캐시<L1캐시<레지스터

메모리 주소
물리적 RAM이나 하드 디스크 갑ㅌ이 실제 자료나 프로그램이 저장되는 공간을 뜻한다.

가상메모리
물리적인 메모리 공간의 크기는 한정적

가상주소
메모리상의 위치를 식별하기 위한 가상주소가 존재

페이징
일정한 크기의 페이지를 나눠서 사용하는 페이징이라는 개념과페이지에 매핑된 주소를 물리적인 주소로 변환하느 페이지 테이블 이라는 개념되 있다

선형 데이터 구조의 개요

데이터 구조를 구성하는요소들이 서로 인접해순차적인 방식으로 정렬되어 있음을 뜻한다

배열
자료형 같은 요소들을 저장한다. 배열에 저장된각가의 자료를요소라고 한다

인텍스
요소에 매겨진숫자를 배열의 인덱스라고 한다

배열의 구조
배열 내 요소들은 순차적 또는 연속적으로 정렬되어 있다

배열의 다차원
2차원 배열은 프로그래밍으로 모든 요소에 접근할수 있는 행과 열이 그리드이다.
참고로 2차원 배열은 가장 일반적인 다차원 배열이자 2차원구조이며, 이를 행렬이라고 한다.

리스트
배열의 특별한 유형이라고 할 수 있다. 리스트의 요소는흩어진상태로 메모리에 저장이된다. 이 때문에 연결리스트는 메모릴르 더 효과적으로 사용할 수 있다.

포인터는 리스트 내의바로 다음 요소가 저장된 메모리 위치를 가리킨다

단방향 연결리스트 : 노드 하나가 다른 노드를 가리키는 포인터 하나를갖는유형의 연결리스트를 단방향 연결리스트라고한다

양방향 연결리스트 : 각 노드가 다음 노드를 가리키는포인터와이전노드를 가리키는 포인터를 함께 갖는 연결리스트 구조

스택

추가된 요소를 사용가능한메모리의가장 앞주소에 배치하는선형 데이터구조의 한종류 이다
정적스택 : 배열을 사용하여 설게할수 있다. 최상단 요소를 가리키는 포인터가 있는 단반향 연결 리스트를 사용하여 동적 스택을 설계할수 있다.

큐: 각 요소에 우선순위를 부여하는 데이터 구조의한 종류다. 큐에 첫번째 요소를 추가하면 큐 뒤쪽에배치된다

이렇게 큐에 요소를 추가하는것을 인큐라고 한다.
큐에서 요소를 삭제하는 것을 데큐라고한다

선입선출 : 큐에 가장 먼저 추가된 요소가 우선적으로 삭제된다는 점

우선순위 큐 : 키 값을 식별하고 검색하는 데 사용 값의 체계를사용해 큐의 요소들을 정렬한다.

해시 데이터 구조

해시: 데이터를 고정길이의 데이터로 매핑하는것이다
해시충돌: 해시 함수에서 서로 다른 입력 2개가 같은 해시값을 생성할 가능성도

선형탐색

숫자를 저장할 변수를 마련한다-> 배열 탐색을 시갖한다->배열 각요소를 숫자 7이 저장된 변수와 비교한다 -> 변수와 배열의 요소가 일치하면 숫자를 찾은 것이다 ->찾은숫자의 인텍스를 반환한다

선형알고리즘 - 시간복잡도는 O(n)이다. 시간 복잡도의원리와 앞서 언급한 선형성의 개념을 떠올려보면 이러한알고리즘이 데이터쌍을 이용해 선형적으로 요소를 탐색하는 방법임을 알 수 잇다

정렬알고리즘- 이진 탐색은 알고리즘을수행하기 전에 데이터를 비교하도록 특정 순서로배열을 정렬한다

버블정렬-비효율적인 알고리즘
선택정렬 - 선형탐색을 응용한 알고리즘이다 시간 복잡도가 O(n제곱)이다
삽입정렬- 훌륭한 알고리즘이다 왼쪽 끝에서 두 번째에 있는 숫자부터 차례대로 앞의 숫자들과 비교한다
셸정렬 - 요소를 몇 개 단위로 묶은 후 단위마다 삽입 정렬을 실해
이후 단위요소 수를 줄여 묶은 후 삽입정렬 단위 요소수가 1이 될대까지 실행하면 정렬이 완료됨
병합정렬-데이터를 반으로 나누어정렬을 수행하는 독창적인 알고리즘이다 이러한 방식을분할정복이라고한다
퀵정렬-마커 이동의 기준이 되는 피벗으로 정한다. 맨오른쪽에 위치한 요소와 배열 맨 오른쪽에 위치한 요소를 선택하여 왼쪽마커 오른쪽마커로 정한다
힙정렬- 각구조의 각 노드를 최대 힘 혹은 최소힙 상태로 정렬하는 방법을 뜻한다
버킷정렬-버킷 사용할 기억공간을 준비, 버킷을 만들 때의기준에 따라 요소를 분류해 넣음, 버킷별로 요소를 정렬함,버킷 안에서 정렬한 요소를 버킷의 순서에따라나열해서 정렬을 완료함
기수정렬-특정 자릿수끼리 비교해서 정렬한다는 것이다

스케줄링 알고리즘

커널 프로세스스레드작업
커널에 파일관리, 사용자인터페이스,프로토콜스택, 보안 메커니즘등을추가하면 운영체제가 된다
프로그램이 메모리에 적재되어 실행될 때, 이를 프로세스라고 한다

메모리 관리장치

메모리와 보조 저장 장치 사이에서 페이징이발생
커널 모드 - 시스템 하드웨어에 접근할 수 있고커널의 주소공간과 사용

스케줄러 -어떤 작업이언제 실행될지 결정하는 역할