221115_TIL

정렬

정의
데이터를 순서대로 나열하는 방법을 의미함.
이진탐색을 가능하게 하고, 데이터를 효율적으로 탐색할 수 있게 만들어준다.

<종류>

1. 버블 정렬(Bubble Sort)

• 첫번째 자료와 두번째 자료를, 두번째 자료와 세번째 자료를, 세번째 자료와 네번째.. << 이런식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식.

  (n - 1)과 (n)을 비교

• 작은 숫자∙큰 숫자 순서로 있으면 PASS.
  큰 숫자∙작은 숫자 순서로 있으면 Replace.

  let a = 5, let b = 2
  a, b를 비교 후, 2, 5로 재정렬

2. 선택 정렬(Selection Sort)

• 각 배열(array)을 계속해서 탐색하는 방식이라 2중 반복문을 실행해야 한다.
• 선택 정렬은 전체에서 최소값을 "선택"하는 것.
• 선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꿈.

3. 삽입 정렬(Insertion Sort)

• 삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입"하는 방식.
• 삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식임.

4. 병합 정렬(Merge Sort)

• 합치면서 정렬

• 배열(Array)의 앞부분과 뒷부분이 두 그룹으로 나누어 각각 정렬한 후, 병합하는 작업을 반복하는 알고리즘.

• 분할 정복의 개념이 적용된다.
  ㄴ 문제를 작은 2개의 문제로 분리하고, 각각 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략. (== Devide and Conquer)

• 병합 정렬은 합치면서 정렬하는 즉, 동일한 동작수행을 하면서 움직이게 되는데, "재귀적인 코드가 떠올라야 한다.".
  ㄴ 재귀적인 코드에는 항상 탈출코드도 따라온다.

  자기 자신을 포함하는 형식으로 함수를 이용해서 정의해보면, MergeSort(시작점, 끝점)이라 해보자.

  MergeSort(O, N) = Merge(MergeSort(O, N/2) + MergeSort(N/2, N)

  Merge(MergeSort(O, N/2) + MergeSort(N/2, N) ===> (시작점 ~ 절반) + (절반 ~ 끝 값)

• 병합 정렬의 핵심은, 반반 정렬한 것을 합치면 정렬이 된다는 것이다.

Stack(스택)_자료구조

정의
한 쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조. (선형적)

스택 구조(Stack) == 빨래통

• LIFO == Last In, First Out
  ㄴ 마지막에 들어간 데이터가 먼저 나오게 된다.

• 이런 자료구조는 왜 필요한가?
  - 자료를 넣은 순서를 알아야할 경우가 있어야 하는데, 스택 자료구조는 자료를 넣은 순서를 쌓아두고 있기 때문.
  예시 ) 컴퓨터의 되돌리기(Cmd + z) 기능에 스택구조가 사용된다.

• 스택 자료구조에서 제공하는 기능은 다음과 같음.

  Push(data) : 맨 위에 데이터 넣기
  pop() : 맨 위에 데이터 뽑기(==삭제)
  peek() : 맨 위에 데이터 보기
  isEmpty() : 스택이 비었는지 안 비었는지 여부 반환하기
  
  인자가 없는 이유?
  ㄴ 스택(Stack) 자료구조는 항상 맨 위에꺼만 뽑을 수 있기 때문에 선택권이 없다.

Q. 스택은 데이터를 넣고 뽑는 걸 자주하는 자료구조인데, 어떤 방식으로 구현하는 것이 좋을까?
A. Linked List(링크드 리스트)로 Stack(스택)을 구현하는 것이 좋다.

• Stack(스택) 실전 사용법?
  - 실제 코드에서는 Python의 List 자료구조를 이용해서 Stack으로 사용한다.

  예시)
  stack = [] # 빈 스택 초기화
  stack.append(4) # 스택 push(4)
  stack.append(3) # 스택 push(3)
  top = stack.pop() # 스택 pop(), 최근에 들어간 데이터 뽑기(삭제)
  print(top) # 3

• 맨 뒤에 자료가 없어지는 자료구조?
  ㄴ "Stack(스택)"이라는 자료구조라는 것을 알아채야 한다.

Queue(큐)_자료구조

정의
한쪽 끝으로 자료를 넣고, 반대편 쪽에서는 자료를 뺄 수 있는 선형구조.

놀이기구 대기줄을 연상.

• FIFO == First In First Out
  ㄴ 먼저 들어간 데이터가 빨리 나온다.

• 이런 자료구조는 왜 필요한가?
  ㄴ 순서대로 처리되어야 하는 일에 필요하기 때문에.

  데이터가 들어왔을 때, 먼저 들어온 대로 처리해야할 때,
  혹은 먼저 해야할 일들을 저장하고 싶을 때 "Queue(큐)"를 사용한다.

• 스택 자료구조에서 제공하는 기능은 다음과 같음.

  enqueue(data) : 맨 뒤에 데이터 추가하기
  dequeue() : 맨 위에 데이터 뽑기(==맨 앞 head에 있는 데이터 삭제)
  peek() : 맨 위에 데이터 보기(== 맨 앞 데이터 보기)
  isEmpty() : 스택이 비었는지 안 비었는지 여부 반환하기
  
  인자가 없는 이유?
  ㄴ 항상 맨 위에꺼만 뽑을 수 있기 때문에 선택권이 없다.

  스택과 똑같이 데이터는 맨 위에 쌓임. 하지만 빠지는 데이터는 맨 앞 데이터가 빠진다. (줄 기다리는 그림 == Queue(큐))

Q. Queue(큐)는 데이터를 넣고 뽑는 걸 자주하는 자료구조인데, 어떤 방식으로 구현하는 것이 좋을까?
A. Linked List(링크드 리스트)로 Stack(스택)을 구현하는 것이 좋다.

• Stack(스택)과 다르게 Queue(큐)는 시작과 끝의 노드를 전부 가지고 있어야 한다.

Hash(해쉬)_자료구조

정의

• 해쉬 테이블이란?
  - 컴퓨팅에서 Key를 Value에 매핑할 수 있는 구조인, 연관배열 추가에 사용되는 자료구조다.
  해쉬 테이블은 해쉬 함수를 사용하여 인덱스(index)를 버킷(bucket)이나 슬롯(slot)의 배열(Array)로 계산한다.
  데이터를 다루는 기법중 하나로, 데이터의 검색과 저장이 아주 빠르게 진행된다.
  

딕셔너리를 해쉬테이블이라 부르기도 한다.
{Key:Value}

Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라진다.
찾는 데이터가 있는지 배열을 다 둘러보지 않고, Key에 대해서 검색하면 바로 값을 조회할 수 있는 아주 유용한 자료구조임.

**딕셔너리는 사실 내부적으로는 배열(Array)를 사용한다.

• 해쉬함수는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수임.

• 해쉬 충돌 해결방법

1. 체이닝
2. 개방주소법

• 체이닝(Chainning)
  - 각 배열(Array)에 링크드리스트(Linked List)를 연결해놓는 것. 그리고 Key가 동일하다면, 그 아이템의 뒤 아이템으로 만들어놓음. 그리고 항상 Key기도달하게 되면 그 Key에 대한 링크드리스트를 전부 조회해서 Key를 가지고있는 Value를 반환해주는 방식.

• 개방 주소법(Open Addressing)
  - 예시

  items라는 배열에 해쉬값을 넣는 과정.
  
  fast라는 key의 해쉬값이 3이 나와서 items[3]에 들어감.
  그런데, slow의 해쉬값이 동일하게 3이 나왔음.
  slow는 items[3]에 자리가 없을을 알고 items[4]로 이동했지만, 이미 어떤 데이터가 들어가있음을 확인함.
  slow는 [3],[4]를 지나 items[5]에 빈자리를 찾았고, 결국 items[5]에 slow의 value를 넣음.
  
  이를 "개방 주소법"이라고 한다.

• 해쉬 내용 정리

1. 해쉬 테이블(Hash Table)은 "key"와 "value"를 저장함으로써 즉각적으로 데이터를 받아오고, 업데이트하고 싶을 때 사용하는 자료구조.
   - 해쉬 테이블의 내부 구현은 Key를 해쉬 함수를 통해 임의의 값으로 변경한 뒤, Array(배열)의 index(인덱스, 색인)값으로 변환하여 해당하는 값에 데이터를 저장한다.
   그렇기 때문에 즉각적으로 데이터를 찾고, 추가할 수 있는 것이다.
   
   "만약, 해쉬값 혹은 index가 중복되어 충돌이 일어난다면? => 체이닝과 개방주소법 방법으로 해결 가능."
   
   
2. 해쉬 함수(Hash Function)는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수다.

Tree(트리)_자료구조

정의
뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료구조.

Queue(큐),Stack(스택)은 자료구조에서 선형 구조다.

선형구조?

• 자료를 구성하고 있는 데이터들이 순차적으로 나열된 형태를 의미

• Tree는 '비선형 구조'인데, 선형구조와 다르게 데이터가 계층적 or 망으로 구성되어 있다.
  - 선형구조는 자료를 저장하고, 꺼내는 것에 초점.
  - 비선형구조는 표현에 초점. (==> 폴더구조, 계층형)

• Tree에서 사용되는 용어 정리

  Node : Tree에서 데이터를 저장하는 기본 요소
  Root Node : Tree 맨 위에 있는 노드(Head Node)
  Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch러 연결된 노드의 깊이를 나타낸다.
  Parent Node : 어떤 노드의 하위 레벨에 연결된 노드
  Child Node(== Terminal Node) : 어떤 노드의 상위 레벨에 연결된 노드
  Sibling : 동일한 Parent Node를 가진 노드
  Depth : Tree에서 Node가 가질 수 있는 최대 Level

• Tree 종류

1. 이진 트리(Binary Tree)
   - 각 노드가 최대 두개의 자식을 가짐
   - 하위 노드가 무조건 0,1,2개만 있어야 함.

2. 완전 이진 트리(Complete Binary Tree)
   - 노드를 삽입할 때, 최하단 왼쪽 노드부터 차례대로 삽입해야 한다.

---

Python Array의 요소 삭제

1. del : 인덱스로 삭제
   • del은 함수가 아니라 예약어이다. 그렇기 때문에 함수와 같이 사용할 수 없다.
   • del의 사용방법은 del 뒤에 한 칸을 띄고서 'del array [인덱스]' 형태로 사용한다
2. remove() : 값으로 삭제