자료구조란?

자료구조 , 데이터구조, data structure다 같은 용어이다.
대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미한다.
코드상에서 효율적으로 데이터를 처리하기위해서 , 데이터의 특성에 따라 , 체계적으로 데이터를 구조화해야한다.
- 어떤 자료구조를 사용하느냐에 따라 효율이 달라짐

알고리즘이란?

어떤 문제를 풀기 위한 절차/방법
어떤 문제에 대해서 특정한 '입력'을 넣으면 원하는 '출력을 얻을 수 있도록 만드는 프로그래밍'
- 얼마의 시간이 걸리고 얼마의 저장공간을 활용하는가가 중요하다.

자료구조와 알고리즘이 중요한 이유

어떤 자료구조와 알고리즘을 쓰느냐에 따라 성능이 천지차이다.

배열

데이터를 나열하고 , 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조
파이썬에서는 리스트 타입이 배열 기능을 제공하고 있음

배열이 왜필요할까?

같은 종류의 데이터를 효율적으로 관리하기위해서 사용
같은 종류의 데이터를 순차적으로 저장

배열의 장점

빠른 접근이 가능하다.
- 맨앞의 주소만 안다면 끝에있는 데이터까지 접근을 하기가 쉽다.

배열의 단점

내가 미리 배열의 데이터의 크기를 설정해야한다. 따라서 데이터의 추가가 어렵다.
예를 들어 STRING 에서 RI를 빼야하는 경우가 생긴다면 NG를 앞으로 당겨야한다. 추가와 삭제시 추가적인 배열의 공간이 필요할수있다. 즉 데이터의 추가와 삭제가 쉽지 않다.

큐

멀티태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위하여 많이 사용됨 (운영체제 참조)
- 큐의 장단점 보다는 큐의 활용의 예인 프로세스 스케쥴링 방식을 함께 이해해두는것이 좋음 (딱히 알려진 장단점이 없음)

스택

스택은 프로세스의 동작원리와 굉장히 유사하다.
Push /pop

스택의 장점

구조가 간단하기 때문에 구현이 쉽다.
데이터의 읽고/쓰기가 용이하다.

스택의 단점(일반적인 스택 이용시)

데이터의 최대 개수를 미리 정해야 한다.
- 전채 공간을 미리 확보해야하기 때문에 저장공간의 낭비가 발생할 수 있다.
- 파이썬의 경우에서는 재귀함수의 호출이 1000번까지만 가능하다.

연결 리스트

1.linked list의 구조

연결리스트라고도 함
배열은 순차적으로 연결된 공간에 나열하는 구조
연결리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 사용할 수 있다.
노드와 포인터가 한쌍으로 존재

linked list 의 장점

미리 데이터의 공간을 할당하지 않아도 된다.
- 이에 반해 배열은 미리 데이터의 공간을 할당해주어야 한다.

linked list의 단점

연결을 위한 별도의 데이터 공간이 필요하므로 저장공간의 효율이 높지는 않다.
연결정보를 찾는데 걸리는 시간이 길다.
중간 데이터 삭제시 앞뒤 노드를 연결하는 작업이 추가적으로 필요하다.

linked list의 구조

doubly linked list
double linked list의 단점
- 복잡하다.

알고리즘 복잡도 표현방법

알고리즘 복잡도 계산이 필요한 이유
- 하나의 문제를 푸는 알고리즘은 다양할 수 있음
  - Ex)정수의 절대값 구하기
    - 1, -1 ->> 1
    - 방법1: 정수값을 제곱한 값에 다시 루트를 씌우기
    - 방법2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기
알고리즘 복잡도 계산 항목
- 1.시간복잡도 : 알고리즘 실행 속도
- 2.공간복잡도 : 알고리즘이 사용하는 메모리 사이즈
알고리즘 시간 복잡도 주요 요소
- 반복문이 지배한다.(알고리즘에서 반복문의 구성정도)

알고리즘 성능 표기법
- Big O (빅-오) 표기법: O(N)
  - 알고리즘 최악의 실행 시간을 표기
  - 가장 많이/일반적으로 사용함
  - 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문
  - Ω (오메가) 표기법: Ω(N)
    - 오메가 표기법은 알고리즘 최상의 실행 시간을 표기
  - Θ (세타) 표기법: Θ(N)
    - 오메가 표기법은 알고리즘 평균 실행 시간을 표기
시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 익히면 됨
- 빅 오 표기법, Big-O 표기법 이라고도 부름
- O(입력)
  - 입력 n 에 따라 결정되는 시간 복잡도 함수
  - O(1), O(𝑙𝑜𝑔𝑛logn), O(n), O(n𝑙𝑜𝑔𝑛logn), O(𝑛2n2), O(2𝑛2n), O(n!)등으로 표기함
  - 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
    - O(1) < O(𝑙𝑜𝑔𝑛logn) < O(n) < O(n𝑙𝑜𝑔𝑛logn) < O(𝑛2n2) < O(2𝑛2n) < O(n!)
      - 참고: log n 의 베이스는 2 - 𝑙𝑜𝑔2𝑛log2n
- 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 된다..
  - 표현식에 가장 큰 영향을 미치는 n 의 단위로 표기한다.
  - n이 1이든 100이든, 1000이든, 10000이든 실행을
    - 무조건 2회(상수회) 실행한다: O(1)
    - n에 따라, n번, n + 10 번, 또는 3n + 10 번등 실행한다: O(n)
    - n에 따라,𝑛2n2번,𝑛2n21000 번, 100𝑛2n2- 100, 또는 300𝑛2n2 1번등 실행한다: O(𝑛2n2)
해쉬테이블(hash table)
해쉬구조
- 키(key)에 데이터(value)를 저장하는 데이터구조
- 키를 통해서 바로 데이터를 받아올 수 있으므로 속도가 획기적으로 빨라짐
- 보통 배열로 hash table 사이즈 만큼 생성후에 사용
  - 단 파이썬에서는 해쉬를 별도 구현할 이유가 없음 (딕셔너리 타입을 사용하면 됨)
알아둘 용어
- 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것
- 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
- 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
- 해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address): Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음
- 슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간
- 저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음
자료구조 해쉬 테이블의 장단점과 주요 용도
- 장점
  - 데이터 저장/읽기 속도가 빠르다 ( 검색속도가 빠르다)
  - 해쉬는 키에 대한 데이터가 있는지 ( 중복) 확인이 쉬움
- 단점
  - 일반적으로 저장공간이 좀 더 많이 필요하다
  - 여러키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도의 자료구조가 필요함
- 주요 용도
  - 검색이 많이 필요한 경우
  - 저장 , 삭제 , 읽기가 빈번한 경우
  - 캐쉬 구현시 ( 중복 확인이 쉽기 때문 )
충돌(Collision)해결 알고리즘 ( 좋은 해쉬 함수 사용하기 )
- 해쉬 테이블의 가장 큰 문제는 충돌(collision)의 경우입니다. 이 문제를 충돌(collision)또는 해쉬 충돌(Hash Collision)이라고 부릅니다.
  - Chaining 기법
    - 개방 hashing 또는 open Hashing 기법 중 하나 : 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
    - 충돌이 일어나면 링크드 리스트라는 자료구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법
  - Linear Probing 기법
    - 폐쇄 해슁 또는 close Hashing 기법 중 하나 : 해쉬 테이블 저장공간안에서 충돌 문제를 해결하는 기법
    - 충돌이 일어나면 해당 hash address 부터맨 처음 나오는 빈 공간에 저장하는 기법
      - 저장공간 활용도를 높이기 위한 기법
- 충돌을 줄이기위해서는
  - 저장공간의 50%이상의 데이터를 저장하는 경우에는 저장공간을 증가시켜서 충돌을 감소시킨다.
참고: 유명한 해시함수(secure hashing algorithm)
- Sha-1
- Sha-256
hash의 시간복잡도
- 일반적인경우 (collision이 없는경우) = o(1)
- 최악의경우(collision이 모두 발생하는 경우) = o(n)
  - 해시 테이블의 경우 일반적인 경우를 기대하기 때문에 o(1) 이라고 할 수 있음
검색 테이블에서의 해시의 경우
- 16개의 배열에 데이터를 저장하고 검색할 경우 - o(n)
- 16개의 데이터 공간을 가진 해쉬 테이블에 데이터를 저장하고 검색할 경우 - o(1)
트리
1. 트리 (Tree) 구조
- 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
- 실제로 어디에 많이 사용되나?
  - 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨
2. 알아둘 용어
- Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
- Root Node: 트리 맨 위에 있는 노드
- Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
- Parent Node: 어떤 노드의 다음 레벨에 연결된 노드
- Child Node: 어떤 노드의 상위 레벨에 연결된 노드
- Leaf Node (Terminal Node): Child Node가 하나도 없는 노드
- Sibling (Brother Node): 동일한 Parent Node를 가진 노드
- Depth: 트리에서 Node가 가질 수 있는 최대 Level
3. 이진 트리와 이진 탐색 트리 (Binary Search Tree)
- 이진 트리: 노드의 최대 Branch가 2인 트리
- 이진 탐색 트리 (Binary Search Tree, BST): 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
  - 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음
- (출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)
4. 자료 구조 이진 탐색 트리의 장점과 주요 용도
- 주요 용도: 데이터 검색(탐색)
- 장점: 탐색 속도를 개선할 수 있음
이진트리와 정렬된 배열간의 탐색 비교
(출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)
- 배열은 배열의 크기만큼 걸린다 이진탐색트리(BST)는 혁신적으로 검색시간을 줄인다.
이진 탐색 트리 삭제
- 매우 복잡함. 경우를 나누어서 이해하는 것이 좋음
  삭제할 Node를 탐색한다.
  - 삭제할 Node가 없는 경우도 처리해야함
    - 이를위해서 삭제할 Node가 없는 경우는 False를 리턴하고 , 함수를 종료시킴
  Case1
  - 노드가 leaf Node일때 (즉, Node의 자식이 아무도 없을때)
    - 삭제할 Node를 None으로 만들고 branch 를 삭제하면 된다.
  Case2
  - 15를 삭제한다음 10인 노드가 19를 가리키게한다.
    - 여기서도 케이스를 두개로 나누어야한다.
    - - 삭제할 노드가 자식을 왼쪽에만 가지고있을때
      - 삭제할 노드가 자식을 오른쪽에만 가지고 있을때
  Case3
  - 기본사용전략
    - 5를 삭제한후에 3을 5자리에 올릴지 6을 5자리에 올릴지 생각해야한다.
      - Sol1) 삭제할 노드의 오른쪽 자식들중에 가장 작은 값을 5자리에 올린다.
      - Sol2) 삭제할 노드의 왼쪽 자식들중에 가장 큰 값을 5자리에 올린다.
  - 위의 기본 사용전략을 사용한다고 하더라도 2가지 case를 더 나누어야한다
  - - Ex)sol1 을 사용하여 구현한다고 할때
      - Sol1-1
        
        삭제하려는 노드의 오른쪽 트리에서 제일작은 노드가 자식이 없는경우(이때에는 오른쪽자식밖에 있을수가 없다 있다면 그것이 바꿔져야 하는 값이어야 함으로)
      - Sol1-2
        
        삭제하려는 노드의 오른쪽 트리에서 제일작은 노드가 자식이 있는경우
  이진 탐색 트리의 시간 복잡도와 단점
  - 시간복잡도(탐색시)
    - depth(트리의 높이)를 h라고 표기한다면 O(h)
    - n개의 노드를 가진다면 h=log2(n)에 가까움으로 시간복잡도는 O(logn)
      - 참고 :빅오 표시법에서 logn의 밑은 10이 아니라 2이다.
      - 한번 실행시마다 50%의 실행할 수도 있는 명령을 제거한다는 의미, 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함
  - 단점(worst case)
    - 평균 시간 복잡도는 log(n)이지만 균형잡혀있을때를 의미한다.
    - 만약에 한쪽으로 쏠릴경우는 링크드 리스트와 동일한 성능이다(log(n))
  힙
  - Heap: 데이터에서 최대값과 최소값을 빠르게 찾기 위하여 고안된 완전 이진트리(complete binary tree)
    - 완전이진트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차래로 삽입하는 트리
  힙의 구조
  - 힙은 두가지의 구조로 분류할 수 있다.
    - 최대값을 구하기위한 Max Heap
    - 최솟값을 구하기위한 Min Heap
  - 힙을 구성하기 위한 두가지 조건
    - 각 노드의 값은 해당 노드의 자식노드의 값보다 크다(Max Heap의 경우)
    - 완전이진트리 의 조건에 맞추어야 한다.
  힙과 이진탐색트리의 공통점과 차이점
  - 공통점
    - 힙과 이진탐색트리는 모두 이진트리이다.
  - 차이점
    - 힙은 각노드의 값이 자식노드보다 크다 (Max heap)의 경우
    - 이진 탐색 트리는 왼쪽 노드의 값이 가장작다
    - 힙은 오른쪽이 클수도 있고 왼쪽이 클수도 있다.
  - 결론
    - 이진탐색트리는 탐색을 위한 구조 , 힙은 최대/최소값 검색을 위한 구조다
  힙의 동작
  - 힙의 삽입
  - 힙의 삭제
  Heap insert(max heap)
  - 완전 이진트리 이기때문에 기본적으로 왼쪽 최하단부 노드부터 채워진다.
  - 이후에 부모노드보다 값이 클경우 바꿔준다(Max Heap의경우)
  Heap Delete(max heap)
  - 1.최상단노드 삭제
  - 2.최상단 노드 삭제후 가장 최하단부 왼쪽에 위치한노드를 root 노드로 이동
  - 3.root노드값이 child노드 보다 작을경우 root노드의 child 노드중 가장 큰 값을 가진 노드와 root노드를 바꿔주는 작업을 반복(swap)
  힙의 시간복잡도
  - 트리의높이(depth)를 h라고 한다면
  - n개의 노드를 가지는 heap 에 데이터 삽입 혹은 삭제시 최악의 경우 root에서 leaf 까지 비교해야 하기 때문에 h=log2n에 가깝다. 따라서 시간복잡도는 O(logn)이다.
대문자 O 표기법