C++로 알고리즘 풀기 - 2주차 과외내용 정리

안녕하세요? 이화입니다. 최근 국민대 알고리즘 대회를 준비하고 있어요! 그래서 지인 분께 알고리즘 과외를 받으면서 C++ 공부를 하고 있습니다. 매일은 아니지만, 일주일에 두 번(과외 받은 거 정리 / 숙제 정리)이상은 이렇게 글로 정리해 보려고 해요!

이번엔 다음과 같은 내용을 배웠습니다!

• 그래프 자료구조에 대해서 배웠습니다.
• DFS와 BFS에 대해서 배웠습니다.

그럼, 시작해 보겠습니다.

 

0. 몬스터 에너지 드링크

지금 마시고 있습니다. 제로가 최근 나왔죠? 카페인이 정확히 100mg 들어있네요. 카페인의 LD50은 약 200mg/kg니까 몬스터로 죽으려면 저는 200캔 정도 마셔야겠네요. 이 정도면 다 마시기 전에 배가 터져서 죽을 거에요. 위는 대충 2L 정도의 용량을 가지고 있거든요.

1. 그래프란 무엇인가.

그래프는 정점과 간선으로 이루어진 자료구조입니다. 대충 다음과 같은 꼴이라고 보시면 돼요.

그래프 G = ( V, E )

V : 정점 { 1, 2, 3, 4 }

E : 간선 { (1, 2), (1, 3), (1, 4), (2, 3), (2, 4)}

이 그래프를 시각화하면 다음과 같습니다.

간단하게 생겼네요!

2. 그래프의 분류

그래프에는 여러 분류가 있는데요, 이번에 배운 건 유향/무향 그래프와 가중치가 있는/가중치가 없는 그래프였습니다. 한 번 살펴볼까요?

먼저 유향 그래프와 무향 그래프입니다, 다시 말해서, 방향이 있는 그래프와 없는 그래프입니다. 그림을 보면 바로 알 수 있을 거에요.

왼쪽이 유향 그래프, 오른쪽이 무향 그래프

바로 이해가 가지 않으시나요? 그리고 무향 그래프는 유향 그래프로 나타낼 수 있다는 특징이 있습니다. 한 번 볼까요?

위의 무향 그래프를 유향 그래프로 나타내 보았습니다.

이렇게, 무향 그래프는 양방향으로 연결된 유향 그래프라고 할 수 있겠네요.

다음은 가중치가 있는 그래프인데요, 말 그대로 각 간선에 가중치가 있습니다.