알고리즘 study -24-

한창희·2021년 7월 21일

algorithm

algorithm study

목록 보기

24/26

<대표적인 자료구조>

<그래프>

-> 정점과 간선으로 이루어짐

정점 = node = vertex
간선 = edge
차수 = 하나의 정점에 몇 개의 간선
ex> 위 그림에서 노드2의 차수는 4
사이클 = 자기 자신으로 돌아올 수 있는 경로

<그래프가 중요한 이유>

-> 현실세계의 많은 것들을 그래프로 나타낼 수 있다
ex> 지하철 노선도, sns 친구관계

-->> 그래프와 관련된 문제가 매우 많다

-> 이전 자료구조에 비해 그래프는 어려우니 제대로 이해하고 넘어가자

<그래프에 관한 중요한 수학적 지식>

간선의 개수는 정점 개수의 제곱보다 작거나 같다
각 정점의 차수의 합은 간선의 개수의 2배와 같다

<그래프 구현 : 1. 인접행렬>

정점의 연결관계를 2차원 배열에 0,1 로 표현
0: 연결x /// 1: 연결o

주요질문
Q1) 정점 x, y 연결 되어 있나?
Q2) x와 연결된 정점은 몇개?

장점 :
연결 여부를 O(1)에 알 수 있다

단점 :

인접한 정점을 찾는데 O(n) 이 걸린다
(실제 인접한 정점 개수 상관없이 n개를 다 살펴봐야 한다)
간선 개수 상관없이 무조건 2차원 배열에서 n^2 개의 칸을 사용해야 함

<인접행렬 구현>

#include <stdio.h>
using namespace std;

const int MAX = 10;

bool isConnected(int myGraph[MAX][MAX], int x, int y){
  // x, y가 연결이 되어 있으면 true, 아니면 false
  // * 2차원 배열 넘길때 크기 적어주자
  
  return myGraph[x][y] == 1 ? true : false;
  
  
  // 조건 ? 값1 : 값2  -> true면 값1 출력
}

void getAdj(int myGraph[MAX][MAX], int n, int x){
  // 인접 정점   // n =총 정점 개수
  for(int i = 1; i<=n; i++){
    if(myGraph[x][i] == 1)
      printf("%d ", i);
  }
}

int main() {

  int n, m; // n-정점 개수   m-간선 개수
  
  int myGraph[MAX][MAX] = {0,};
  
  scanf("%d %d", &n, &m);
  
  for(int i = 0; i<m; i++){
    int a,b;
    scanf("%d %d", &a, &b); // a와b가 연결 됨
    
    myGraph[a][b] = 1;
    myGraph[b][a] = 1;
  }
  
  for(int i = 1; i<=n; i++){
    for(int j = 1; j<=n; j++){
      printf("%d ", myGraph[i][j]);
    }
    printf("\n");
  }
  
  // q1. 정점 x, y 연결 되어 있나?
  // q2. 정점 x와 연결이 되어 있는 모든 정점 출력
  
  printf("%d\n", isConnected(myGraph, 1,2));
  
  getAdj(myGraph, n, 2);
  
  

  return 0;
}

입력
5 6
1 2
1 3
1 4
2 4
4 5
3 5

출력
0 1 1 1 0
1 0 0 1 0
1 0 0 0 1
1 1 0 0 1
0 0 1 1 0
1
1 4

<그래프 구현 : 2. 인접 리스트>

-> 각각의 정점에 대하여 인접한 정점 번호를 저장

장점 :

인접한 정점 모두 찾을 때 필요한 만큼만 본다 (vs 인접행렬)
필요한 만큼만 공간 사용

단점 :

정점 인접 여부는 O(n)

<인접 리스트 구현>

각각의 정점에 대하여 인접한 정점 번호를 저장

-->> 라이브러리 사용!!

<STL = Standard Template Library>

유명한 자료구조 및 알고리즘이 구현된 코드 집합
캡슐화를 통해 구현되어 있다

<기초 STL>

<Vector 벡터>

크기 조절이 가능한 배열
#include < vector >

#include <stdio.h>
#include <vector>   // check!!

using namespace std;


int main() {
  
  vector <int> myArray(10);
  
  myArray[0] = 3;
  
  for(int i = 0; i<=9; i++)
    myArray[i] = i;
  
  myArray.push_back(10);  // 맨 끝에 한 칸 추가
  // 크기 조절이 가능!
  
  for(int i = 0; i<=10; i++)
    printf("%d ", myArray[i]);
  
  return 0;
}

vector <int> myArray(10,3) = 10칸을 모두 3으로 초기화

myArray.push_back(x) = 맨 마지막에 x를 추가

myArray.pop_back() = 맨 끝을 뺀다 / 공간도 사라진다

myArray.resize(x) = 크기를 x로 변경

myArray.size() = 현재 배열 크기 반환 / 원소가 있든 없든 모든 공간 크기



vector <int> myArray2() = 빈 공간의 배열 생성 (크기 0)

myArray2.resize(n, m) = n-1 인덱스 까지 늘리고 빈 공간은 m으로 모두 채운다

#include <stdio.h>
#include <vector>

using namespace std;

int main() {

  vector <int> arr;
  
  arr.push_back(1);
  arr.push_back(2);
  arr.push_back(3);
  
  printf("%d\n", arr.size());
  
  arr.pop_back();
  
  printf("%d\n", arr.size());
  
  arr.resize(10, 5);
  
  for(int i = 0; i < arr.size(); i++)
    printf("%d ", arr[i]);
  
  printf("\n");
  
  arr.resize(5, 3);
  
   for(int i = 0; i < arr.size(); i++)
    printf("%d ", arr[i]);
  
  printf("\n");
  

  return 0;
}

출력
3
2
1 2 5 5 5 5 5 5 5 5
1 2 5 5 5

<인접 리스트 구현 코드>

#include <stdio.h>
#include <vector>

using namespace std;

int main() {

  // 1: 2 3 4
  // 2: 1 4
  // 3: 1 5
  // 4: 1 2 5
  // 5: 3 4
  
  vector <int> myGraph[10];
  // vector <int> 가 10개 생성
  
  // myGraph[x] = x와 인접한 모든 노드를 저장
  
  int n, m;  // 노드 수, 간선 수
  
  scanf("%d %d", &n, &m);
  
  for(int i = 0; i<m; i++){
    int a, b;
    scanf("%d %d", &a, &b); // a 와 b 가 인접!
    
    myGraph[a].push_back(b);
    myGraph[b].push_back(a);
  }
  
  
  for(int i = 1; i<=n; i++){
    printf("%d: ", i);
    
    for(int j = 0; j < myGraph[i].size(); j++){
      printf("%d", myGraph[i][j]);
    }
    
    printf("\n");
  }

  return 0;
}