[자료구조] BIG-O 표기법, 그래프 기초

글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자입니다

 

목차

 

---

 

인프런 Rookiss님의 '자료구조와 알고리즘' 강의를 기반으로 정리한 필기입니다. 
😎 [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘 강의 들으러 가기!

 

 

 

BIG-O 표기법

 

---

 

BIG-O 표기법 의의

 

위의 그래프와 표는 입력 N값에 따라 걸리는 시간을 나타낸다. (= 시간 복잡도)

프로그램을 돌리는데 1초가 넘어가면 아주 느려서 쓰기 힘든 정도로 봐야한다.  n^2 같은 연산은 지양해야 한다. 제곱연산은 log함수 형태로 치환하여 연산하는게 유리하다.

 

출처: https://cooervo.github.io/Algorithms-DataStructures-BigONotation/

Big O cheat sheets

 

 

---

 

 

그래프의 개념

그래프는 현실 세계의 사물이나 추상적인 개념 간의 '연결 관계'를 표현한다. 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진다. 그래프의 예로는 '소셜 네트워크 관계도', 지하철 노선도 등이 있다.

• 정점(Vertex) : 데이터를 표현 ex. 사물, 개념 등
• 간선(Edge) : 정점들을 연결하는데 사용

 

---

가중치 그래프(WEIGHTED GRAPH)

본문내용넣기

ex. 지하철 노선도

 

 

 

 

---

 

방향 그래프(DIRECTED GRAPH)

ex. 일방 통행이 포함된 도로망, 두 사람 사이의 호감도

 

---

 

코드 예시

 

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;
 
void CreateGraph_1()
{
    struct Vertex
    {
        vector<Vertex*> edges;
        // int data;
    };
 
    vector<Vertex> v;
    v.resize(6);
 
    v[0].edges.push_back(&v[1]);
    v[0].edges.push_back(&v[3]);
    v[1].edges.push_back(&v[0]);
    v[1].edges.push_back(&v[2]);
    v[1].edges.push_back(&v[3]);
    v[3].edges.push_back(&v[4]);
    v[5].edges.push_back(&v[4]);
 
    // Q) 0번 -> 3번 정점이 연결되어 있나요?
    bool connected = false;
    for (Vertex* edge : v[0].edges)
    {
        if (edge == &v[3])
        {
            connected = true;
            break;
        }
    }
}
 
void CreateGraph_2()
{
    struct Vertex
    {
        // int data;
    };
 
    vector<Vertex> v;
    v.resize(6);
 
    // 연결된 목록을 따로 관리
    // adjacent[n] -> n번째 정점과 연결된 정점 목록
    vector<vector<int>> adjacent(6);
    adjacent[0] = { 1, 3 };
    adjacent[1] = { 0, 2, 3 };
    adjacent[3] = { 4 };
    adjacent[5] = { 4 };
 
    // 정점이 100개
    // - 지하철 노선도 -> 서로 드문 드문 연결 (양옆, 환승역이라면 조금 더 ++)
    // - 페이스북 친구 -> 서로 빽빽하게 연결 // 연결이 많은 경우 위의 방법이 좋지 않다.
 
    // Q) 0번 -> 3번 정점이 연결되어 있나요?
    bool connected = false;
    for (int vertex : adjacent[0])
    {
        if (vertex == 3)
        {
            connected = true;
            break;
        }
    }
 
    // STL
    vector<int>& adj = adjacent[0];
    bool connected2 = (std::find(adj.begin(), adj.end(), 3) != adj.end());
}
 
// 일반적인 방법
void CreateGraph_3()
{
    struct Vertex
    {
        // int data;
    };
 
    vector<Vertex> v;
    v.resize(6);
 
    // 연결된 목록을 따로 관리
    // [X][O][X][O][X][X]
    // [O][X][O][O][X][X]
    // [X][X][X][X][X][X]
    // [X][X][X][X][O][X]
    // [X][X][X][X][X][X]
    // [X][X][X][X][O][X]
 
    // 읽는 방법: adjacent[from][to]
    // 행렬을 이용한 그래프 표현(2차원 배열)
    // 메모리 소모가 심하지만, 빠른 접근이 가능하다.
    // 간선이 많은 경우 이점이 있다.
    vector<vector<bool>> adjacent(6, vector<bool>(6, false));
    adjacent[0][1] = true;
    adjacent[0][3] = true;
    adjacent[1][0] = true;
    adjacent[1][2] = true;
    adjacent[1][3] = true;
    adjacent[3][4] = true;
    adjacent[5][4] = true;
 
 
    // 정점이 100개
    // - 지하철 노선도 -> 서로 드문 드문 연결 (양옆, 환승역이라면 조금 더 ++)
    // - 페이스북 친구 -> 서로 빽빽하게 연결
 
    // Q) 0번 -> 3번 정점이 연결되어 있나요?
    bool connected = adjacent[0][3];
 
    vector<vector<int>> adjacent2 =
    {
        vector<int> { -1, 15, -1, 35, -1, -1 },
        vector<int> { 15, -1,  5, 10, -1, -1 },
        vector<int> { -1, -1, -1, -1, -1, -1 },
        vector<int> { -1, -1, -1, -1,  5, -1 },
        vector<int> { -1, -1, -1, -1, -1, -1 },
        vector<int> { -1, -1, -1, -1,  5, -1 },
    };
}
 
int main()
{
    CreateGraph_1();
    CreateGraph_2();
    CreateGraph_3();
}