본문 바로가기
728x90

Baekjoon/[정리] 윤성우의 열혈 자료구조7

[자료구조] 07 그래프 ▶ 그래프 (Graph) 방향 그래프 무방향 그래프 완전 그래프 가중치 그래프 부분 그래프 ▶ 그래프 G의 정점 집합 V(G) = {A, B, C, D} 무방향 그래프 G의 간선 집합 E(G) = {(A, B), (A, C), (A, D)} 방향 그래프 G의 간선 집합 E(G) = {, , } ▶ 구현 방법 (2가지) : 인접 행렬 기반 그래프 (정방 행렬 활용) : 인접 리스트 기반 그래프 (연결 리스트 활용) ▶ 탐색 깊이 우선 탐색 (Depth First Search) (DFS) 너비 우선 탐색 (Breadth First Search) (BFS) ▶ 깊이 우선 탐색 (DFS) : 한 사람에게만 연락을 취한다. (PUSH 떠나는 노드) : 연락할 사람이 없으면, 자신에게 연락한 사람에게 이를 알린다... 2021. 3. 15.
[자료구조] 06 테이블 ▶ 테이블 (Table) : 저장되는 데이터는 키와 값이 하나의 쌍을 이룬다. : 키가 존재하지 않는 '값'은 저장 불가 : 모든 키는 중복되지 않는다. : ex) 사전(단어-키, 설명-값) ▶ : 배열의 인덱스 값을 키 범위로 사용하기에 적당하지 않다. : 왜냐하면 매우 큰 배열이 필요하기 때문 : 이를 해결해주는 것이 '해쉬 함수' ▶ 해쉬 함수 (Hash Function) : 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할 : 좋은 해쉬 함수는 데이터가 메모리에 골고루 분포하여 충돌 활률이 낮다. ▶ 좋은 해쉬 함수 만드는 법 : 키의 특성에 의존되기 때문에 정답은 없다. : 키의 일부분 참조항여 해쉬 값을 만들지 않고, 키 전체를 참조하여 해쉬값 만들기 ▶ 해쉬 충돌 (Hash Collision.. 2021. 3. 15.
[자료구조] 05 정렬, 탐색 ▶ 정렬 (Sort) : 버블 정렬 (Bubble Sort) : 선택 정렬 (Selection Sort) : 삽입 정렬 (Insertion Sort) : 힙 정렬 (Heap Sort) : 병합 정렬 (Merge Sort) (분할(Divide) → 정복(Conquer) → 결합(Combine) 기반 구현) : 퀵 정렬 (Quick Sort) (분할(Divide) → 정복(Conquer) → 결합(Combine) 기반 구현) : 기수 정렬 (Radix Sort) ▶ 순차 탐색 (Linear Search) : 정렬 되지 않은 대상을 기반으로 하는 탐색 ▶ 이진 탐색 (Binary Search) : 정렬된 대상을 기반으로 하는 탐색 ▶ 보간 탐색 (Interpolation Search) : 데이터의 값과 그 데.. 2021. 3. 15.
[자료구조] 04 우선순위 큐, 힙 ▶ 우선순위 큐 (Priority Queue) : 산입 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. : ex) 응급상황 ▶ 배열 기반 우선순위 큐 (단점) : 데이터 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야 한다. : 삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있다. ▶ 연결 리스트 기반 우선순위 큐 (단점) : 삽입의 위치를 찾기 위해서 첫 번째 노드에서부터 시작해서 마지막 노드에 저장된 데이터와 우선순위의 비교를 진행해야 할 수도 있다. ▶힙 (Heap)을 이용하는 우선순위 큐 구현 : 위와 같은 단점들로 인해 힙을 이용한다 ▶ 힙 (Heap) : '이진 트리'이되 '완전 이진 트리'이다.. 2021. 3. 15.
728x90

티스토리툴바