[패스트캠퍼스 수강 후기] 올인원 패키지 : 컴퓨터 공학 전공 필수👉C언어인강 100% 환급 챌린지 48회차 미션

 

환급미션 48일째...

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 15. 그래프 - 그래프의 개념과 구현

소프트웨어 베이직 - 자료구조와 알고리즘 - 16. 그래프 - 깊이 우선 탐색

운영체제 - 가상 메모리의 이해 - 01. 가상 메모리 개념

운영체제 - 가상 메모리의 이해 - 02. 페이징 시스템

운영체제 - 가상 메모리의 이해 - 03. 다중 단계 페이징 시스템과 페이징 시스템 장점

 

 

 

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 15. 그래프 - 그래프의 개념과 구현

 

 

- 그래프 (Graph)의 개념

 

사물을 정점(Vertex)과 간선(Edge)으로 나타내기 위한 도구

 

2가지 방식으로 구현할 수 있다.

•인접 행렬 (Adjacency Matrix) : 2차원 배열을 사용

•인접 리스트(Adjacency List) : 리스트를 사용

 

 

 

 

* 인접행렬 예시

 

인접행렬(Adjacency Matrix) 예시

 

위의 그림에서 0,1,2 값이 있는 부분들을 각각 정점 또는 Node라고 하고

정점을 서로 이어주는 것들을 간선(Edge)이라고 한다.

 

오른쪽 배열을 살펴보면,

0번째 인덱스에서 0번째 인덱스로 가는 것은 비용, 즉 가중치가 0이다.

0에서 1로 가는 경우 비용이 3이다.

0에서 2로 가는 경우 비용이 7이다.

1에서 2로 가는 길은 없기 때문에 값이 무한으로 들어가게 된다.

 

 

 

 

* 무방향 비가중치 그래프와 인접 행렬

 

 

•방향성이 없고 연결만 되어있는 그래프를 '무방향 그래프'라고 한다.

•모든 간선에 가중치가 없는 그래프를 '비가중치 그래프'라고 한다.

•무방향 비가중치 그래프가 주어졌을 때, 연결상황을 인접행렬로 표현할 수 있다.

 

 

 

 

 

강의에서와는 코드의 출력부분을 조금 다르게 작성해봤는데,

 

강의에서는 해당 부분을

------------

for (int i=1; i<=n; i++)

{

 for (int j=1; j<=n; j++)

 {
  printf("%d", a[i][j]);

 }

 printf("\n");

} 

------------

위와 같이 작성했다.

즉, 강사님의 의도는 일부러 각 인덱스를 1부터 출발하도록 만드는 것이었다.

 

 

나는 위에서 사용한 예제를 그대로 사용해보고 싶어서

0부터 출력되게 만들었고,

 

원하는 결과가 출력되었다.

 

 

 

* 방향 가중치 그래프와 인접 리스트

 

 

•모든 간선이 방향을 가지는 그래프를 '방향 그래프'라고 한다.

•모든 간선에 가중치가 있는 그래프를 '가중치 그래프'라고 한다.

•방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 리스트로 출력할 수 있다.

 

 

 

 

 

 

위와 같이 코드를 작성했다.

 

사실 영혼없이 적다가 잘못 작성해서 

생고생 끝에 성공...

 

 

결과도 정상적으로 출력되었다.

 

 

 

 

 

 

 

정리

 

 

•인접 행렬

 

모든 정점의 연결 여부를 저장하여 O(V²)의 공간을 요구하므로 공간 효율성이 떨어지지만 (메모리를 많이 사용)

두 정점이 서로 연결되었는지 확인하는 데 O(1)의 시간을 요구한다. (즉시 확인)

 

•인접 리스트

 

연결된 간선의 정보만을 저장하여 O(E)의 공간을 요구하므로 공간 효율성이 우수하지만

두 정점이 서로 연결되었는지 확인하는 데 O(V)의 시간을 요구한다. (시간 오래걸림)

 

 

 

 

 

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 16. 그래프 - 깊이 우선 탐색

운영체제 - 가상 메모리의 이해 - 01. 가상 메모리 개념

운영체제 - 가상 메모리의 이해 - 02. 페이징 시스템

운영체제 - 가상 메모리의 이해 - 03. 다중 단계 페이징 시스템과 페이징 시스템 장점

 

 

 

 

 

 

 

 

올인원 패키지 : 컴퓨터 공학 전공 필수👉https://bit.ly/3i4sCVE