궁금한 것들

Talk : 함께 대화해보면 좋을 것들

• 연결 리스트
• 활용예시:
• 양방향 연결 리스트의 장점
• 역방향 탐색이 가능
• 특정 인덱스 접근 시, 앞에서 접근 vs 뒤에서 접근
• 우선순위 큐 활용하는 곳 : CPU 스케쥴링
• 추상적 자료형(abstract data type, ADT) : 스택, 큐, 연결 리스트
 

• 트리
• 활용예시: dom 트리, 자동검색(트라이), 디렉토리 구조
• Red-Black 트리의 연산
• 트라이 vs 트리 문자열 탐색 시 시간 복잡도

• 그래프
• 활용예시:
• dfs, bfs 각각 언제 어떤 걸 쓰는지?
• 그래프 사이클 여부 확인 방법

• 해시테이블
• 활용예시: db 인덱스
[DS] 해쉬 테이블(Hash Table)이란?
해싱이란 임의의 길이의 값을 해시함수(Hash Function) 를 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다. 위 그림에서 dog 라는 문자열을 해시함수를 이용해 새로운 값으로 변환한 것을 볼 수 있는데 이 경우엔 암호화에 쓰이는 해시 알고리즘인 MD5를 사용한 것이다. 하지만 여기서 다룰 것은 암호화에 쓰인 방식이 아닌 자료구조로 사용하고자 하는 해시 테이블을 다루기 때문에 정수값으로 변환되는 해시 알고리즘을 사용한다.

https://baeharam.netlify.app/posts/data%20structure/hash-table

• 로드 팩터(충돌률 지표) 기준
• 해시테이블 충돌
• 궁금: 충돌방법에도 단점 존재 → 어떻게 해결?
• 결론: 해시 충돌을 완벽하게 막는 방법은 없다.
• 그래서, 해시충돌률이 낮은 해시함수를 채택해서 이용한다.
• 가장 많이 쓰는 해시함수: SHA256 알고리즘
1. 비트코인도 이 알고리즘 채택해 사용
2. 2의 256개의 고유 해시를 만들 수 있어서, 해시 충돌률이 상당히 낮음 (자세한 건 SHA256알고리즘 찾아보시면 됩니다)
 
• 해시 테이블 활용 예시

• 우선순위큐는 추상자료형
• 추상자료형이란?
[자료구조] 추상 자료형(Abstract Data Type, ADT)이란? (feat. 스택 & 큐)
추상 자료형(Abstract Data Type, ADT)이란? 구현하고자 하는 구조에 대해 구현 방법은 명시하지 않고 자료구조의 특성들과 어떤 Operations들이 있는지를 설명하는 자료구조의 한가지 형태. 즉, 일종의 '규칙'들의 나열이라고 쉽게 이해할 수 있다. ADT의 가장 대표적 예로는 스택(Stack)과 큐(Queue)가 있다. 스택(Stack) 이란? 영어 단어 Stack이란 쌓아 올린다는 것을 의미한다.

https://ontheway.tistory.com/23