Develop & Dream

난수를 생성해서 50% 확률로 미로를 파는 방향을 정함

Graph(그래프) 기본 용어 정리 및 표현

Graph(그래프)란?

• 현실세계의 사물이나 추상적인 개념간의 연결관계를 정점(vertex)과 간선(edge)으로 표현한것

정점(vertex) : 데이터를 표현 (사물, 개념)

간선(edge) : 정점들을 연결 하는데 사용

G = (V, E) 

V = {A, B, C, D, E}      //정점들의 집합

E = {e1, e2, e3, e4, e5} //간선들의 집합

e1 = (A, B) //부속해 있는 정점들

e2 = (A, C)

e3 = (B, C)

e4 = (B, D)

e5 = (D, E)

코드로 표현하기

간선들의 가중치가 모두 동일하다는 전제하에 아래처럼 2차원 배열로 표현할 수 있다.

2차원 배열의 세로, 가로 모두 Vertex 들을 가리킨다

가로의 인덱스는 곧 vertex들의 순서이고

순서대로 A, B, C, D, E를 가리킨다

이때 0 또는 1로 표현하는데, 인접(adjacent)해 있다면 1로 표현하고

그렇지 않으면 0으로 표현한다

위와 같이 인접관계를 행렬(2차원 배열)로 표현한 것을 "인접 행렬" 이라고 한다

그외에도 2차원 배열이 아닌 리스트를 통해 인접관계를 표현한 것을 "인접 리스트" 이라고 한다 

그래서

vertex A는 인접해 있는 vertex가 B와 C 이므로

B index = 1

C index = 2

이기 때문에 1번째, 2번째 값에 1(true)이 들어간다

{0, 1, 1, 0, 0}, //A

vertex B는 A,C,D 이다

A index = 0

C index = 2

D index = 3

배열의 0번째, 2번째, 3번째에 1(true)이 들어간다

{1, 0, 1, 1, 0}, //B

이런식으로 정리하다 보면, 아래와 같이 정리가 된다.

{
    {0, 1, 1, 0, 0}, //A
    {1, 0, 1, 1, 0}, //B
    {1, 1, 0, 0, 0}, //C
    {0, 1, 0, 0, 1}, //D
    {0, 0, 0, 1, 0} //E
};

용어 정리

sparse graph : 노드의 수보다 엣지 수가 적은 그래프, vertex > edge

dense graph : 노드의 수 보다 엣지 수가 큰 그래프, vertex < edge

인접(incident), 부속(adjacent) : 위 그래프에서 vertex A와 C는 edge e2로 연결되어 있다, 이때 vertex A와 C는 서로 인접(adjacent)해 있다. 그리고 edge e2는 두 vertex A 와 C에 부속(incident)해 있다고 한다

degree : 하나의 vertex 에 연결된 edge 의 수

loop : 하나의 edge가 하나의 노드에만 부속해 있을때

isolated vertex : 하나의 vertex에 부속해 있는 edge가 전혀 없을때

adjacency matrix(인접 행렬) : 그래프 이론에서 인접 관계를 행렬로 표현한 것

adjacency list(인접 리스트) : 그래프 이론에서 인접 관계를 리스트로 표현한 것

빅오 표기법(Big-O Notation)

• 알고리즘의 시간 효율성과 메모리 효율성을 나타냄
• 빅오메가 : 하한 점근, 최선의 경우 표기법
• 빅세타 : 상한/하한점근, 정확한 성능 표기법
• 빅오 : 가장 최악인 상황에서 최소 보장되는 성능, 효율성을 상한선 기준으로 표기(최악의 효율)
• 알고리즘 효율성은 값이 클수록, 비효율적임을 의미함
• 알고리즘의 실제 러닝타임이 아니라, 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 나타내는것
• 상수는 항상 제외한다 O(2n) 인경우 O(n)으로 표기해야 맞는것이다
  

성능 순서(오른쪽으로 갈수록 성능이 안좋음)

   O(1) < O(log n) < O(n) < O(nlog n) < O(n²) < O(n³) < O(2ⁿ) 

HashSearch < Binary Search < Sequential Search < Quick Sort < 구구단 출력 함수 <Floyd-Warshall < 피보나치 수열

O(1) : constant time, 언제나 일정한 속도, HashSearch 

ex)

F(int[] n){

       return (n[0] == 0)? true : false;

}

// n의 크기에 상관없이 언제나 일정한 속도로 결과를 반환

가로축 : data의 크기

세로축 : 처리시간

데이터가 증가함에 따라 처리시간은 항상 일정한 것을 볼 수 있다

O(logN) : logarithmic time, 이진탐색(Binary Search)

ex)

F(k, arr, s, e){

       if ( s > e ) return -1;

       m = ( s + e ) / 2;

       if ( arr[m] == k ) return m;

       else if ( arr[m] > k ) return F(k, arr, s, m-1);

       else return F(k, arr, m+1, e);

}

// 이진 탐색

가로축 : data의 크기

세로축 : 처리시간

데이터가 증가하여도 처리시간이 크게 늘어나지 않는다

O(n) : linear time, n번만큼 동작하는 루프1개, sequential search

ex)

F(int[] n){

       for i = 0 to n.length

              print i

}

// n개의 data를 받으면 n번 만큼의 loop를 돌게된다, 즉 n의 크기에 비례해서 처리시간이 늘어남

가로축 : data의 크기

세로축 : 처리시간

데이터가 증가함에 따라 비례해서 처리시간도 증가함, 언제나 데이터와 시간이 정비례한다

O(nlogn) : log linear, Quick Sort

데이터가 증가함에 대해 처리 시간은 정비례보다 약간 더 많이 증가를함

가로축 : data의 크기

세로축 : 처리시간

데이터양에 따라 걸리는 시간은 제곱에 비례함

O(n²) : quadratic time, n번만큼 동작하는 이중 루프, 구구단 출력 함수

ex)

F(int[] n){

      for i = 0 to n.length

            for j = 0 to n.length

                      print i + j;

}

// n개의 data를 받으면 n번 만큼의 loop를 돌고 이것을 이중으로 함(이중루프)

가로축 : data의 크기

세로축 : 처리시간

데이터양에 따라 걸리는 시간은 O(n²)과 거의 유사하다

O(n³) : cubic time, n번만큼 동작하는 삼중 루프, Floyd-Warshall

ex)

F(int[] n){

     for i = 0 to n.length

          for j = 0 to n.length

              for k = 0 to n.length

                       print i + j + k;

}

O(2ⁿ) : exponential time, 피보나치 수열 

ex)

F(n, r){

      if (n <= 0) return 0;

      else if( n == 1) return r[n] = 1;

      return r[n] = F(n -1, r) + F(n - 2, r);

}