경일 메타버스 20220627 13주차 1일 수업내용. 자료구조와 알고리즘-이진검색, 그래프

자료

https://docs.google.com/document/d/1wUms27Vj8si-jEjfRQJwSvsQ2CJNCv4IU6GOtesY4TE/edit

이진 검색(Binary Search)

• 검색할 범위를 절반으로 줄여가며 검색하는 방법이다.

• 이진 검색은 정렬된 선형 리스트에서만 사용할 수 있다.

  1. 정렬되어야 하고

  2. 임의 검색이 가능해야 한다.

• 시간 복잡도는 O(logN)이다.

  • 리스트를 두 부분으로 반복해서 나누어준다.

  • 나눌 때마다 그 중간값을 기준으로 검색할 부분을 고른다.

    2022. 06. 27 이진 검색 예시

• STL에서도 이진 검색을 제공한다.

  • bsearch

  • 목록 : https://en.cppreference.com/w/cpp/algorithm#Binarysearch_operations.28on_sorted_ranges.29

    2022. 06. 27 STL 제공 이진 검색 예시

그래프(graph)

• 관계에 특화된 자료구조

• 정점(Vertex)과 간선(Edge)으로 구성되어 있다.

• 정점은 고유하게 식별되는 객체

• 간선은 정점 간의 관계를 표현한다.

종류

1. 방향 그래프(Directed Graph)

• 간선이 방향성을 가진다.

2. 무방향 그래프(Undirected Graph)

• 간선이 방향성을 가지지 않는다.

3. 가중치 그래프(Weighted Graph)

• 간선이 단순 연결 이상의 정보(가중치)를 가진다.

• 네트워크(Network)라고도 한다.

• 출처 : https://pangtrue.tistory.com/147

용어

• 인접(Adjacent)하다 :
  정점끼리 간선으로 연결되어있다.

• 연결된 정점에 부속(Incident)되어 있다 :
  간선이 정점끼리 연결해주고 있다.

• 차수(Degree) :
  정점에 부속되어 있는 간선의 수.

  • 진입 차수(In-degree) :
    정점으로 들어오는 방향의 간선 수, 차수.

  • 진출 차수(Out-degree) :
    정점에서 나가는 방향의 간선 수, 차수.

• 경로(Path) :
  한 정점에서 다른 정점까지 간선으로 연결된 정점을 순서대로 나열한 리스트.

  • 경로 길이(Path length) :
    경로를 구성하는 간선 수.

  • 단순 경로(Simple Path) :
    모두 다른 정점으로 구성된 경로.

    • 사이클(Cycle) :
      단순 경로 중 경로의 시작 정점과 마지막 정점이 같은 경로.

  • 정점끼리 연결(Connected)되었다 :
    정점끼리 경로가 있으면 정점끼리 연결(Connected) 되었다고 한다.

    • 연결 그래프(Connected Graph) :
      모든 정점이 연결되어 있는 그래프

    • 단절 그래프(Disconnected Graph) :
      모든 정점이 연결되어 있진 않은 그래프

표현

• 연습 예시 코드

  2022. 06. 27 그래프 표현 예시 코드

• 인접 행렬(Adjacency Matrix)

  • 정점이 N개 있을 경우 N x N 크기의 2차원 배열로 그래프를 표현.

  • 배열의 원소는 간선의 가중치를 나타내게 된다.

  • 구현하기 쉽다.

  • 2차원 배열을 사용하기 때문에 그래프에 간선이 적다면 그만큼 메모리를 낭비하게 된다.

    • 희소 그래프(Sparse Graph) :

      간선이 적은 그래프.

    • 밀집 그래프(Dense Graph) :

      간선이 많은 그래프.

• 인접 리스트(Adjacency List)

  • 각 정점에 연결된 정점의 ID만 저장하는 방식으로 그래프를 표현.

  • 필요한 만큼만 메모리를 쓸 수 있다.

  • 구현 난이도가 있다.

순회

• 그래프 순회(Graph Traversal) :

  • 한 정점에서 시작해 그래프에 있는 모든 정점을 한 번씩 방문하는 것.탐색(search).

  • 깊이 우선 탐색(Depth First Search, DFS)과
    너비 우선 탐색(Breadth First Search, BFS)이 있다.

깊이 우선 탐색(Depth First Search, DFS)

• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속하는 방법.

• 스택을 사용.

너비 우선 탐색(Breadth First Search)

• 시작 정점에 인접한 정점을 모두 차례로 방문하고 나서 방문했던 정점을 시작으로 다시 인접한 정점을 차례로 방문하는 방식.

• 큐를 사용.

탐색의 구현 : DFS, BFS

1. 방문 여부를 저장할 변수를 생성한다.
   ⇒ 왜> 재방문을 막기 위해

2. DFS라면 스택을 만들고, BFS라면 큐를 생성한다.
   ⇒ 스택이나 큐에 저장되는 데이터는 다음에 방문할 정점

3. 더 이상 방문할 정점이 없을 때까지 방문한다.

백준 풀이

2022. 06. 27 그래프 예제 : 백준 1260 DFS&BFS

오답노트 : 백준 5430, 백준 1654, 백준 10816

• 백준 5430 AC
  명령어의 수행은 간단했지만, 문자열의 처리가 곤란했다.
  string 헤더의 isdigit 함수 : 문자가 숫자인지 아닌지 판별.
  별개 string에 숫자로 판별된 문자를 모아넣고 stoi 실행.
  다른 알고리즘도 참고하자.

• 백준 1654 랜선 자르기
  나이브하게 생각했을때 선형 검색을 했을 문제라면, 이진 검색을 활용할 수는 없는지 고민해보자.

  2022. 06. 27 이진 검색 예제 : 백준 1654번 랜선 자르기 풀이

• 백준 10816 숫자 카드 2
  lower_bound와 upper_bound를 그대로 써, 그 포인터 주소의 차를 사용하였기에 시간이 많이 걸린다.
  더 나은 알고리즘은 없을지 다른 사람들의 알고리즘도 참고하면서 고민해 보자.