[클라우딩 어플리케이션 엔지니어링 TIL] 240408 - 240411 자료구조/알고리즘 학습

Intro

---

데브코스 firebase 강의도 벅찼는데 자료구조/알고리즘 강의까지 있어서 듣느라 조금 힘들었다.

알고리즘 문제를 풀고 해설 강의까지 들어야 했는데 문제를 푸는 데도 시간이 오래 걸리기 때문이다.

시간 상 어려운 문제들은 조금만 고민하고 풀이를 보곤 했다.

여유로울 때 다시 풀어봐야지! 

 

 

 

오늘 학습한 내용

---

스택 (Stack)

: LIFO (Last In First Out)

 

큐 (Queue)

: FIFO (First In First Out)

• shift 함수 사용은 지양
• front, rear, index 변수를 지정해서 변수를 꺼내면 front++ 이런 식으로 구현하면 됨

 

해시 테이블

: 입력받은 값을 특정 범위 내 숫자로 변경하는 함수

ex. “gender” ⇒ 172461724 …

 

 

⚠️ 만약 해시 함수의 결과가 동일하여 겹친다면??

• 선형 탐사법
  • 한 영역에 몰리는 문제점이 발생할 수 있다.
  • 충돌이 발생하면 옆으로 한 칸 이동
• 제곱 탐사법
  • 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동
• 이중 해싱
  • 충돌이 발생하면 다른 해시 함수를 이용하기
• 분리 연결법
  • 버킷의 값을 연결리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가

해시는 주로 출석부 관리 등에 사용됨

 

 

자바스크립트에서 해시 테이블 사용하는 방법

 

• Array (추천하는 방식은 X)

const table = []
table['key'] = 100
table['key2'] = 'hello'
console.log(table['key'])
delete table['key']

 

• Object

const table = {}
table['key'] = 100
table['key2'] = 'hello'
delete table['key']

 

• Map: 다양한 타입을 넣을 시 유리 (object도 key로 쓸 수 있음), 편한 메소드와 편한 순회 가능

const table = new Map()
table.set('key', 100)
table.set('key2', 'hello')
table.get('key')

 

• Set: 집합 연산 (중복 X)

const table = new Set()
table.add('key')
table.add('key2')
table.has('key')
table.clear()

 

 

그래프

: 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조

 

정점 집합과 간선 집합으로 표현할 수 있다.

ex) 페이지랭크 알고리즘

 

그래프의 특징

• 정점은 여러 개의 간선을 가질 수 있다.
• 크게 방향 그래프와 무방향 그래프로 나눌 수 있다.
• 간선은 가중치를 가질 수 있다.
• 사이클이 발생할 수 있다.

 

무방향 그래프

• 간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다.
• 표현하기에 (a, b)와 (b, a)는 같은 간선으로 취급한다. (양방향 통행 도로)

 

방향 그래프

• 간선에 방향성이 존재 함
• (a, b)와 (b, a)는 다른 간서으로 취급한다.

 

연결 그래프

• 모든 정점이 서로 이동 가능한 상태인 그래프

 

비연결 그래프

• 특정 정점쌍 사이에 간선이 존재하지 않는 그래프

 

완전 그래프

• 모든 정점끼리 연결된 상태인 그래프
• 한 간선의 정점 수 = 모든 정점의 수 - 1

사이클

• 그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분

그래프 구현 방법

: 인접 행렬이나 인접 리스트 방식 사용

 

 

트리

: 방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조를 가지고 있다.

ex) 조직도, 파일 디렉터리 구조

 

트리의 특징

• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.
• 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.
• 루트에서 특정 정점으로 가는 경로는 유일하다.

이진 트리

: 각 정점이 최대 2개의 자식을 가지는 트리

• 이진트리
• 완전 이진트리
• 포화 이진트리
• 편향트리

 

이진 트리 특징

• 정점이 N개인 이진트리는 최악의 경우 높이가 N이 될 수 있다.
• 정점이 N개인 포화 또는 완전 이진 트리의 높이는 logN
• 높이가 h인 포화 이진트리는 2^h-1개의 정점을 가진다.
• 일반적인 이진트리를 사용하는 경우는 많지 않다.
  • 이진 탐색 트리
  • 힙
  • AVL 트리
  • 레드 블랙 트리

트리 구현 방법

: 인접 행렬, 인접 리스트로 구현 가능

배열 혹은 요소에 링크가 2개 존재하는 연결 리스트로 구현할 수 있다.

•  

 

 

우선순위 큐

: FIFO인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐

우선순위 큐는 자료구조는 아니며 단지 개념일 뿐이다.

 

힙

: 우선순위 큐를 구현하기 위해 적합한 방법

이진트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 바로 정렬되는 특징이 있다.

(힙 ≠ 우선순위 큐)

 

힙의 특징

• 요소가 추가될 때 트리의 가장 마지막 정점에 위치
• 추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다.
• 이 과정을 반복하면 우선순위가 높은 정점이 루트가 된다.
• 완전 이진 트리의 높이는 logN이기에 힙의 요소 추가 알고리즘은 O(logN) 시간복잡도를 가진다.

 

힙 요소 제거 알고리즘

• 요소 제거는 루트 정점만 가능하다.
• 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다.
• 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꾼다.
• 두 자식 정점이 우선순위가 더 낮을 때까지 반복
• 완전 이진 트리의 높이는 logN이기에 힙의 요소 제거 알고리즘은 O(logN) 시간 복잡도이다.

 

트라이 (Trie)

: 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

 

트라이 특징

• 검색어 자동완성, 사전 찾기 등에 응용된다.
• 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.
• L이 문자열 길이일 때 탐색, 삽입은 O(L)만큼이 걸린다.
• 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장공간을 더 많이 사용한다.

트라이 구조

• 루트는 비어있다.
• 각 간선은 추가될 문자를 키로 가진다.
• 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
• 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.

 

 

이진 탐색

선형 탐색은 순서대로 하나씩 찾는 탐색 알고리즘이고, 이진 탐색은 정렬되어있는 요소들을 반씩 제외하며 찾는 알고리즘이다.

 

이진 탐색 특징

• 반드시 정렬되어 있어야 한다.
• 배열 혹은 이진 트리를 이용하여 구현 가능
• O(logN) 시간복잡도 ← 매우 빠름

 

정렬

: 요소들을 일정한 순서대로 열거하는 알고리즘

• 정렬 기준은 사용자가 정할 수 있다.
• 크게 비교식과 분산식 정렬로 나눌 수 있다.
• 대부분 언어가 빌트인으로 제공해줌
• 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재

 

어떤 정렬이 제일 빠를까?

=> 정해져있지 않다!

 

비교식 정렬

• 버블 정렬: 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘 O(n^2)
• 선택 정렬: 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 알고리즘 O(n^2)
• 삽입 정렬: 선택한 요소를 삽입 할 수 있는 위치를 찾아 삽입하는 방식의 알고리즘 O(n^2)

분산식 정렬

분할 정복

: 문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능 할 때 처리한 후 합치는 전략 ⇒ 다양한 알고리즘에 응용됨

• 합병 정렬: 분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘 O(nlogn)
• 퀵 정렬: 분할 정복 알고리즘을 이요한 매우 빠르지만 최악의 경우가 존재하는 불안정 정렬 O(nlogn)

✅ Javascript에서 정렬은 sort() 사용

 

소수 구하기

1. 2부터 N-1까지 루트를 돌며 나눠보기 O(n)
2. 그 어떤 소수도 N의 제곱근보다 큰 수로 나눠지지 않는다. O(sqrt(n))
3. 에라토스테네스의 체: 가장 효과적인 알고리즘

 

 

마무리

---

강의를 들을 땐 아하! 하면서 이해가 잘되는데 막상 문제를 풀어보려하면 잘 안풀리고 막막한 것 같다.

여러 문제를 많이 풀어보면서 익숙해져야겠다.