🌈 [Section2] 5. 자료구조3

📕 오늘 배운 내용!

• 트리 순회 (Tree traversal)
• 그래프 탐색 ( BFS / DFS )
• Deque
• 배열 / Linked List
• Hash Table )

[참고] https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
( 먼저, 여기는 알고리즘이 메모리에 어떻게 저장되고 생성되는지 눈으로 볼 수 있는 사이트! )

---

✏️ 트리 순회 (Tree traversal)

• 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것
  ( 순서는 항상 왼쪽 ➜ 오른쪽 )

 

1. 전위 순회 (preorder traverse)

👉 루트 노드 ➜ 왼쪽 자식 노드 ➜ 오른쪽 자식 순서

 

2. 중위 순회 (inorder traverse)

👉 왼쪽 자식 ➜ 루트 노드 ➜ 오른쪽 자식 순서

 

3. 후위 순회 (postorder traverse)

👉 루트 노드 ➜ 왼쪽 자식 노드 ➜ 오른쪽 자식 순서

---

✏️ 그래프 탐색 ( BFS / DFS )

• 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적
  ( 그래프의 데이터는 배열처럼 정렬이 되어 있지 않기 때문에 하나씩 모두 방문하여 찾아야함 )
  

 

1. 너비 우선 탐색 BFS ( Breadth-First Search )

➜ 가까운 점부터 모두 탐색 후, 그 다음으로 가까운 점 탐색
➜ 두 정점 사이의 최단 경로를 찾을 때 사용
➜ 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 사용
➜ 검색 속도 자체는 DFS에 비해 더 빠름
➜ 보통 Queue를 이용해 문제 품

 

2. 깊이 우선 탐색 DFS ( Depth-First Search )

➜ 하나의 경로를 끝까지 탐색 후, 다음 경로로 넘어가 탐색
➜ 검색 대상 그래프가 정말 크다면 사용
➜ 각각의 경로마다 특징을 저장해둬야 할 때, 중간에 장애물이 있을 때 사용

   ( BFS는 경로의 특징을 가지지 못함 )
➜ 보통 Stack이나 재귀를 이용해 문제 품
   ( Stack의 경우 데이터가 쌓여있을 때 막히면 그거 없애고 다른 경로 다시 쌓음 )
   ( 재귀의 경우 장애물에 막히면 이전 재귀호출 시점으로 돌아가서 경로 찾음 )

---

✏️ Deque (Double Ended Queue)

• 양방향으로 열려있는 구조
  
  
• Queue와 비슷한 모습을 가지고 있고 Stack과 Queue의 특징을 모두 가짐
  ➜ 어느 쪽에서도 들어가고 나갈 수 있음 !
  ( 앞에서 In 했을 때, 같은 방향으로 Out 한다면 Stack과 같은 구조 / 다른 방향으로 Out 한다면 Queue와 같은 구조 ( Out 먼저 했을 때도 같음 ))
  
  
• 양방향 끝에서 데이터 추가, 삭제가 용이
  ➜ 양방향 끝이 아닌 임의의 데이터만 추가하거나 삭제하는 건 불가능

---

✏️ 배열 / Linked List

1) 배열

• 연속된 공간 안에 메모리를 차지
• 메모리 중간에 데이터를 넣으려면 그 뒤의 데이터들이 모두 한칸씩 뒤로 이동해야함

 

2) Linked List

• 흩어져 있는 공간에 노드들의 연결 (모든 노드가 서로의 주소값들로 연결)
• 직접 주소값을 가지고 있어야 다음 노드로 접근 가능
  ➜ 노드값 찾으려면 전체 순회해야함
  ( 메모리에 흩어져 있기 때문에 쉽게 접근 불가 )
  ( 순회 전까지는 첫번째 노드인 head node의 정보만 알고, 전부 순회해야 마지막 요소 확인 가능 )
• 마지막 노드는 가리킬 곳이 없어 null 가리킴
• 노드의 추가/삭제가 빠르고 쉬움
  ( 넣을 위치 앞 뒤 노드의 주소값을 해당 노드의 주소값으로 변경하기만 해주면 가능 )

---

✏️ Hash Table

• 해시함수(hash function)를 사용하여 변환한 해시(hash)를 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조
  ( 필요한 데이터의 키(key)를 해시함수를 사용해 별도의 해시(hash)로 바꿔 주고, 해당하는 데이터(value)를 함께 저장 )
• 데이터를 다루는 작업이 매우 빠름
• 해시 충돌 발생 가능성 있음 / 데이터 저장 전 미리 공간 만들어놔야 함
  ➜ 공간 효율성 떨어짐
• 해시 함수가 복잡할 경우 해시값 만들어내는 데 많은 시간 소요

 

✔ Hash Table 구조

• 키(key)와 해시함수(hash function), 해시(hash), 데이터(value)로 이루어짐

- 키(key)
➜ 해시 함수의 입력값인 고유한 값 ( 다양한 길이의 값이 들어올 수 있음 )
➜ 해시 함수를 통해 변환하지 않은 상태로 저장소에 저장이 되면 다양한 길이만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장

- 해시함수 (hash Function)
➜ 키(key)를 해시(hash)로 바꿔주는 역할
➜ 다양한 길이를 가지고 있는 키(key)를 일정한 길이를 가지는 해시(hash)로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와줌
➜ 해시 충돌을 일으키는 확률을 최대한 줄이는 것이 중요
( 해시 충돌(hash Collision) - 서로 다른 키(key)가 같은 해시(hash)가 되는 경우 )

- 해시 (hash)
➜ 키(key)를 해시함수(hash function)를 사용하여 만들어진 결과물
➜ 저장소에서 데이터(value)와 매칭되어 저장 변환된 값을 배열의 색인(index)과 같이 사용

- 데이터 (value)
➜ 저장소에 최종적으로 저장되는 값
➜ 색인(index)과 매칭되어 저장

---

🌈 느낀점

사실 개념적으로는 괜찮다 문제에 응용하기 어려울 뿐!!
Section2되고 나서 컨텐츠가 뭔가 개념만 설명이 되어있고 어떻게 응용하는지는 나와있지 않아서 직접 하나하나 다 찾아보며 학습을 해야하는 것 같다ㅠ
개념에 비해 문제 난이도가 너무 어렵다구여ㅠㅠ 어떻게 푸는지 감을 잡으면 괜찮은데
그런 예제들이 없으니 감을 잡기가 쉽지 않다,,
그래도 오늘은 어제보다 좀 더 빨리 이해했다! 그래도 문제를 풀 때에 그래프를 어떻게 활용하는지에 대한 큰 틀은 감이 잡힌 것 같다 ㅎㅎ

 

( 본 게시물은 2022/09/26에 작성한 글을 옮긴 글입니다. 원문은 요기에 있음! )

728x90