본문 바로가기
728x90

전체 글206

[자료구조] 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.
[자료구조] 03 트리 ▶ 트리 (Tree) : 계층적 관계를 표현하는 자료구조 ▶ 용어 노드 (Node) 트리의 구성요소 간선 (Edge) 노드와 노드를 연결하는 연결선 루트 노드 (Root Node) 트리 구조에서 최상위에 존재하는 노드 단말 노드 (Terminal Node) 아래로 또는 다른 노드가 연결되어 있지 않는 노드 내부 노드 (Internal Node) 단말 노드를 제외한 모든 노드 부모 노드 (Parent Node) 특정 노드의 상위 노드 자식 노드 (Child Node) 특정 노드의 하위 노드 형제 노드 (Sibling Node) 같은 부모 노드를 둔 노드 조상 노드 (Ancestor) 특정 노드 기준 위로 모든 노드 후손 노드 (Descendant) 특정 노드 기준 아래로 모든 노드 레벨 (Level) 트리.. 2021. 3. 15.
[자료구조] 02 스택, 큐 ▶ 스택 (Stack) : LIFO (후입선출) 구조의 자료구조 : ex) 접시 쌓기 ▶ push : 삽입 (마지막 요소 위에) pop : 삭제 (마지막 요소를) ▶ 구현 종류 배열 기반 스택 / (단순) 연결 리스트 기반 스택 ▶ 구현할 만한 예시 : 계산기 (중위 표기법 → 후위 표기법) 전위 표기법 + 5 / 2 7 중위 표기법 5 + 2 / 7 후위 표기법 5 2 7 / + ▶ 큐 (Queue) : FIFO (선입선출) 구조의 자료구조 : ex) 선착순 줄 서기 ▶ enqueue : 큐에 데이터를 삽입 연산 dequeue : 큐에서 데이터를 꺼내는 연산 ▶ 배열 기반 큐 : 원형 큐 (Circular Queue) : 배열의 끝에 도달하면 처음으로 순환할 수 있게 논리적 원형으로 구현한 큐 : 하지.. 2021. 3. 15.
728x90

티스토리툴바