스택
- Last In First Out
- 스택 메모리
- 스택은 Array (push, pop) / Linked List (top = head) 로 표현 가능하다.
- 스택의 개념으로 count +1, -1을 사용하여 스택 배열 생성 없이도 문제를 풀 수 있다.
연습문제 올바른 괄호
큐
- First In First Out
- Linear Queue, Circular Queue
- 현실에 비유하자면... 대기열
- Linear Queue (Array)
DeQueue, EnQueue ... 메모리 차지 (DeQueue로 비워진 앞 배열을 채워간다면 O(n) 시간이 소요) - Linear Queue (Linked List)
index 에 대한 고민을 하지 않아도 됨.
shift 함수를 쓰지 마세요! (shift는 O(n) 시간이 걸리기 때문에, 제대로 큐를 사용하는 것이 아닙니다.) - Circular Queue (Array) ... Linked List 구현에 큰 이점이 없음
연습문제 프린터
해시 테이블
- key를 index로 변환하여 값을 넣는다.
- 키와 값을 받아 키를 Hashing 하여 나온 index 에 값을 저장하는 선형 자료구조
- 삽입, 삭제, 탑색 O(1)로 수행한다.
- 해시 함수 ... 입력 받은 값을 특정 범위 내 숫자로 변경하는 함수
- 해시 충돌 ... 해시 함수의 결과가 동일 할 때 발생하는 문제점
해결법
선형 탐사법: 충돌이 발생하면 한칸 뒤의 index 로 이동한다. (O(n) 소요)
제곱 탐사법: 선형 탐사법에서 특정 영역에 데이터가 몰리지 않게끔 충돌이 발생한 횟수의 제곱만큼 뒤의 index로 이동한다.
이중 해싱: 충돌이 발생하면 다른 해시 함수를 사용한다.
분리 연결법: 충돌이 발생한 경우, 연결 리스트로 리스트에 값을 추가한다. - 인원 정보를 저장하는데 유용하게 사용할 수 있다.
- 객체를 이용하는게 가장 간단하고 정석적인 방법이다. (map의 set, get으로도 사용 가능)
연습문제 베스트앨범
그래프
- 정점과 정점 사이를 연결하는 간선 (비선형 자료구조) ... 정점(Node) 집합과 간선(Edge) 집합으로 표현
- 인물 관계도와 비슷하다.
- 특징
정점은 여러개에 간선을 가질 수 있음 (비선형 자료구조)
방향 그래프 / 무방향 그래프 로 나뉨
간선은 가중치를 가짐
사이클이 발생할 수 있음 (무한루프에 빠지지 않도록 주의!) - 무방향 그래프
정점끼리 양방향으로 이동이 가능 (양방향 통행) - 방향 그래프
간서에 방향성이 존재하여 다른 간선으로 취급되는 간선이 2개 이상 있어야 양방향 이동이 가능 (일방 통행) - 연결 그래프: 모든 정점이 서로 이동 가능한 상태의 그래프
비연결 그래프: 특정 정점 사이에 간선이 존재하지 않는 그래프
완전 그래프: 모든 정점끼리 연결된 상태의 그래프
사이클: 점점과 간선의 부분집합에서 순환이 되는 부분 - 그래프는 인접 행렬, 인접 리스트 의 두가지 방식으로 표현할 수 있다.
연습문제 가장 먼 노드
트리
- 방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조
- Node(각 정점), Root(최상위 정점), Leaf Node(자식이 없는 정점), Level(Root로 부터 깊이의 단계), Degree(한 정점에서 뻗어가는 간선의 수)
- 조직도, 디렉토리 구조
- 특징
루트 노드를 제외한 모든 노드는 반드시 하나의 부모 노드를 가진다.
정점이 N개라면, 반드시 N-1개의 간선을 가진다.
루트에서 특정 정점으로 가는 경로는 유일하다. - 이진트리: 탐색을 위한 알고리즘에 주로 응용
이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리
이진트리는 배열 혹은 링크가 2개 존재하는 연결 리스트로 구현이 가능하다.
left = index 2
right = index 2 + 1
parent = floor(index / 2)
스택과 큐를 이용한 알고리즘 문제 풀이를 배웠고, 특히 스택 문제에서는 스택 배열을 만들지 않고 스택의 개념만 가지고서 문제를 푸는 방법도 있구나 알 수 있게 되었습니다.
큐를 사용할 때, shift 사용은 피해야 한다는 점은 처음 접하게 되는 사실이였습니다. 이제껏 큐를 통한 문제를 풀면서 간단하고 쉽기때문에 shift 를 사용하고 있었습니다..
이는 시간 복잡도떄문에 제대로 큐를 사용하는게 아님을 처음 알게 되었습니다. shift 를 쓰지 않고 구현하는 큐 자료구조를 충분히 익히려 합니다.
연결 리스트 공부를 해야합니다.. 배열만 쓰다보니 너무 생소합니다 ㅜㅜ. 주말 혹은 늦어도 다음주중에 연결 리스트를 정리할 계획입니다.
해시테이블과 그래프 트리 또한 주말에 시간을 내어 더 정확히 이해하도록 노력해 보겠습니다!
연습문제가 아직 어렵습니다... 🥲
프론트엔드