Part 2. 알고리즘 - 7장 정렬 알고리즘

알고리즘이 중복 데이터를 빠르게 식별하거나 필요한 데이터를 빠르게 찾기 위해서 데이터를 정렬 한다. 책에서 내용은 유형 별로 나와있어서 시간복잡도를 따로 표로 첨부해왔다. 참고하고 외우도록. 기수 정렬 O(dn) 에서 d 는 정렬하고자 하는 요소의 자리수를 의미한다. 삽입정렬 선택 정렬 버블 정렬 힙 정렬 : 힙 데이터 구조와 각 노드를 최대 힙 또는 최소 힙 상태로 정렬 하는 방법을 뜻함. 병합정렬 : 데이터를 반으로 나누어 정렬을 수행, 분할 정복이라고도 함 퀵 정렬 : 피벗과, 왼쪽, 오른쪽 마커로 정렬 셀 정렬 :요소를 묶는 단위를 줄여가며 삽입 정렬을 실행 버킷 정렬 : 특정한 기준의 버킷별로 정렬 기수 정렬 : 기수별로 나눔

2022.10.30

Part 2. 알고리즘 - 6장 선형 및 이진 탐색

선형 탐색 : 쉽게 구현 할 수 있지만, 결과를 얻기 위해 배열의 모든 요소를 살펴봐야 함. 선형 알고리즘 : 실행시간이 요소 개수 증가에 정비례 하여 증가, 시간 복잡도는 O(n) 이진 탐색 : 시간 복잡도 O(logn) , 배열이 정렬된 상태에서만 올바르게 동작. * 지수함수의 역함수는 로그함수 참조 : 코드없는 알고리즘과 데이터 구조 & https://www.geeksforgeeks.org/binary-search/ Binary Search - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming ar..

2022.10.30

Part 1. 데이터 구조 - 4장 해시 데이터 구조

4장에서 다루는 것은 해시 함수를 사용하여 사용하는 동작하는 해시 테이블 이다. 특히 컴퓨터 보안의 암호화와 체크섬은 해싱에 크게 의존한다. 해시는 어떤 길이의 임의 데이터를 고정 길이의 데이터로 매핑하는 것이다. 해시 함수는 이 해시를 실행하려고 하나의 값을 다른 값으로 변환하는 상자를 뜻한다. 해시 함수 특징 : 입력되는 데이터가 무엇이든지 출력되는 해시의 값의 길이가 항상 고정되어 있다. 일반 함수는 정의역 요소 하나에 정확히 하나의 치역 요소가 대응 되지만 해시함수는 서로다른 입력 2개가 같은 해시값을 생성할 가능성 ( 해시 충돌 ) 이 있다. 다만 흔치않은 일이다. 해싱 ( 해시 테이블을 이용하는 탐색) 할대 사용하며, 이때 해시 함수는 해시 테이블 데이터 구조에서 중요한 부..

2022.10.30

Part 1. 데이터 구조 - 3장 트리 데이터 구조

트리 데이터 구조 뒤집혀 있는 나무 처럼 보인다. 키-값 유형의 구조 트리를 탐색하는 과정을 순회 (traversal) 라고 한다. 이진 트리 : 가장 많이 사용 되는 데이터 구조. 각 부모 노드가 항상 2개의 자식 노드와 연결 되어 있다. 이진 트리의 가장 일반적인 유형은 이진탐색트리이다. 이진 탐색 트리에서 모든 노드의 키는 왼쪽 서브 트리보다 크고 오른쪽 서브 트리보다 작다. 트리에 노드 추가, 트리에서 노드 삭제, 노드를 선택해 탐색하고자 하는 키가 존재하는지 확인 가능 Adelson-Velsky and Landis 불균형 이진트리, 단 하나의 자식 노드를 갖는 구조. 트리의 균형을 조정하는 과정은 트리의 역할을 유지하되 가능한 한 최소 높이(자식 노드의 계층이 최소) 로 만드는 것이다. 서브 트..

2022.10.30

Part 1. 데이터 구조 - 2장 선형데이터 구조

컴퓨터 메모리 컴퓨터 메모리는 컴퓨터가 처리중이거나 처리를 끝낸 데이터를 저장할 수 있는 공간. 계층적으로 구성되어 있고, 각 층을 이루는 메모리 유형마다 정해진 역할이 있다. 계층구조를 이상적으로 나타내면 피라미드 형태의 적층 구조이다. 레지스터 연산 처리속도가 굉장히 빠르고 CPU에 장착할 수 있을 만큼 크기가 작은 메모리. L1 캐시 L2 캐시 캐시메모리, CPU가 가장 많이 사용하는 데이터를 저장. L1, L2 두가지 종류가 있는데 L1 캐시는 CPU 레지스터만큼 빠르고, L2 캐시는 L1 캐시보다 느리지만 RAM 보다는 빠르다. 캐시는 용량이 너무 크면 비효율적, RAM 보다 용량이 작아서 데이터를 쉽게 찾을 수 있는데 캐시 용량이 너무 커지면 연산 처리 속도에서 장점이 줄어듬. 메인메모리 RA..

2022.10.28

Part 1. 데이터 구조 - 1장 데이터 구조와 알고리즘, 자료형, 빅 오 표기법

데이터 구조 : 데이터를 구성하고 저장하는 방법을 설명, 데이터를 식별하는 방법을 제공, 데이터의 관계를 보여주는 개념 알고리즘 : 문제를 해결하기 위해 사용하는 일련의 단계. 데이터 구조와 알고리즘의 관계 : 서로 다른 개념 이면서 상호 보완적이다. 데이터 구조는 알고리즘이 다루는 데이터를 구성하며, 알고리즘이 데이터를 처리하고 사용자가 원하는 완전한 정보를 산출하는 과정에서 필요한 부분을 제공한다. * 부동 소수점 수 : 소수를 표현 할 수 있다. 소수점 이라고 부르는 작은 점(.) 의 위치가 어딘가 떠다니는 것처럼 움직이기 때문에 부동점 (floating point) 이라는 이름이 붙었다. * 프로그래밍에서 함수는 매개변수(파라미터) 또는 인수라고 하는 데이터를 입력으로 사용하며 때로는 결과를 반환..

2022.10.28