TIL_10_221111 회고

10일 차 회고

• 알고리즘 개념 정리

스트레스 받지 않기 👋

오늘은 아침부터 cs 개념 ~ 알고리즘 개념까지 완전
처음인 것들에 대해 배웠다. 이해가 안 된다고 좀 스트레스를 받았는데
그런 부분은 그냥 초조하지 않게 차근히 인터넷이든 책으로 찾아서
봐야겠다고 생각했다.

• 특강으로 들은 CPU를 간단히 적어봤다.
  https://velog.io/@young0_0/CS-CPU

알고리즘 개념 정리2

스택

한쪽 끝로만 자료를 넣고 뺄 수 있는 자료구조 (Last In First Out) -> LIFO

• 직전에 했던 행동의 되돌리고 싶을 때 사용하기 위해 스택을 사용한다.
• 스택 자료구조에서 제공하는 기능
  - push(data) : 맨 앞에 데이터 넣기
  - pop() : 맨 앞에 데이터 뽑기
  - peek() : 맨 앞의 데이터 보기
  - isEmpty() : 스택이 비었는지 안 비었는지 반환해주기
• 시간복잡도 : $O(N^2)$

큐

한쪽 끝으로 자료를 넣고, 반대쪽에서 자료를 뺄 수 있는 선형구조 (First In First Out) -> FIFO

• 순서대로 처리되야 하는 일에 필요하기 때문에 큐를 사용한다.
• 큐 자료구조에서 제공하는 기능
  - enqueue(data) : 맨 뒤에 데이터 추가하기
  - dequeue() : 맨 앞의 데이터 뽑기
  - peek() : 맨 앞의 데이터 보기
  - isEmpty() : 큐가 비었는지 안 비었는지 여부 반환해주기

해쉬

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

• 딕셔너리 = 해쉬테이블
• 해쉬 테이블(Hash Table)
  "키" 와 "데이터"를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용하는 자료구조입니다.
  해쉬 테이블의 내부 구현은 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장합니다.
• 해쉬함수(Hash Function)
  임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수.

  >> hash("fast")
  -146084012848775433

• 딕셔너리 함수
  - put(key, value): key에 value 저장하기
  - get(key) : key에 해당하는 value 가져오기
• 충돌(collision) 이 난다면!
  같은 어레이의 인덱스로 매핑이 되어서 데이터를 덮어 써버리는 결과가 발생하는것
  - 해결방법 1 : 체이닝(chaning)
  - 해결방법 2 : 배열의 다음 남는 공간에 넣는 것 (개방 주소법 Open Addressing)
• 시간복잡도 :O(N) ->시간은 빠르되 공간을 대신 사용하는 자료구조

트리

뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조 // 위~ 아래가 구분되어있다.

• 트리에 나오는 용어
  - Node : 트리에서 데이터를 저장하는 기본요소
  - Root Node: 트리 맨 위에 있는 노드
  - Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
  - Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
  - Child Node: 어떤 노드의 하위 레벨에 연결된 노드
  - Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
  - Sibling: 동일한 Parent Node를 가진 노드
  - Depth: 트리에서 Node가 가질 수 있는 최대 Level

이진 트리

각 노드가 최대 두 개의 자식을 가진다. 하위의 노드가 0,1,2개만 있어야한다.

완전 이진 트리

노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다.

• 완전 이진 트리는 왼쪽부터 데이터가 쌓이고 이를 순서대로 배열에 쌓으면서 표현할 수 있다.
• 완전 이진 트리의 높이 : 루트 노드부터 가장아래 리프노드까지의 길이를 말한다.

힙

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리
힙은 항상 큰 값이 상위 레벨에 있고 작은 값은 하위 레벨에 있또록 하는 자료 구조이다.

• 큰값이 가장 모든 자식보다 커야 하기 때문에 가장위에 있다. 따라서 최대의 값들을 빠르게 구할 수 있게 된다.
• 힙
  - 최댓값이 맨 위인 힙 : Max Heap
  - 최솟값이 맨 위인 힙 : Min Heap
• 시간복잡도 : $O(log(N))$

그래프

연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조

• 비선형 구조 :연결관계에 초점이 맞춰져 있다.
• 그래프에 사용되는 용어
  - 노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 합니다.
  - 간선(Edge): 노드 간의 관계를 표시한 선.
  - 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)
• 그래프의 종류
  - 유방향 그래프(Directed Graph): 방향이 있는 간선을 갖습니다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있다
  - 무방향 그래프(Undirected Graph)는 방향이 없는 간선을 갖는다

DFS & BFS

자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다.

• DFS 는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구한다.
  따라서 공간을 적게 씁니다. 그러나 최단 경로를 탐색하기 쉽지 않다
• BFS 는 최단 경로를 쉽게 찾을 수 있다 .
  그러나, 모든 분기되는 수를 다 저장하다보니 공간을 많이 써야하고, 모든 걸 다 보고 오다보니 시간이 더 오래걸릴 수 있다.