Develop & Dream

Breadth First Search (너비 우선 탐색) 응용, 미로 탈출

Right Hand Rule(우수법) 미로 탈출

난수를 생성해서 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);

}

C언어, Queue, pop() 구현하던 도중 shallow copy와

비슷한 문제 발생

내가 구현해본 pop은 첫번째 노드의 데이터를 리턴함과 동시에 Queue 에서 제거하는 함수로

1. char * Data 에 첫번째 노드 데이터를 복사하고 그걸 나중에 리턴한다 

2. Queue의 Head가 첫번째 노드의 다음 주소를 임시 노드에 담아둔다

3. 첫번째 노드를 free 해준다

4. Queue 사이즈 1 감소시킨다

5. 첫번째 노드에 임시노드에 적혀있던 주소를 담는다, 이로써 다음 노드가 첫번째 노드가 된다

6. 데이터를 리턴한다

그러나 1번 char * Data 에 첫번째 노드 데이터를 담고 그걸 나중에 리턴할때 쓰레기값 또는 이상한 값이 출력 됐다.

원인

데이터를 복사한게 아닌, 데이터(char 배열)의 주소를 복사하게 됐다

C++ 에서는 동일한 클래스 타입의 두개의 인스턴스가 존재할때 복사 생성자를 통해서, 인스턴스가 가지고 있는 데이터들을 다른 인스턴스에 복사할 수 있다, 문제는 이때 컴파일러가 만들어주는 기본 복사 생성자를 쓰게되면, 순수하게 데이터 변수들의 값만 복사하게 되고, 주소를 가지고 있는 타입도, 주소를 복사 하게 된다, 그리고 두개의 데이터가 동일한 주소를 가리키는 사태가 벌어진다. 이렇게 되면 원본이던 사본이던 간에 어느 한쪽이 소멸되어 주소가 사라지면, 복사 받은 쪽에서도 주소가 사라져서 결국 이상한 주소를 가리킨다.

그리고 실제로 196번 라인에서 _pQueue->pHead 의 메모리를 해제할때

_pQueue->pHead->data 조차 사라지며, 그걸 담아 뒀던 char* Data 도 사라진 주소를 가리켜 결국

이상한 주소를 가리키게 됐다

해결

pop의 인자로 배열을 input 으로 넣고 해당 배열에 data를 복사하도록, 그리고 주소를 대입하는게 아닌, strcpy_s를 사용해 실제 문자열을 복사하도록 했다

이후 pop한 데이터가 쓰레기 값을 출력하는 사태는 없어졌다.

Array vs LinkedList

Array(배열)

1. 중간 삽입, 중간 삭제는 링크드 리스트에 비해서 어렵고 느림

2. 삽입할 때 마다, 메모리 동적 할당 삽입을 하지 않기 때문에, 데이터를 삽입하는 속도는 링크드 리스트에 비해서 빠름

3. 인덱스로 접근 가능 하므로, random access(무작위 접근, 비순차적 접근 가능), sequential access(순차적 접근) 할 필요 없음, 데이터의 위치에 관계없이 접근시간이 일정함

※random access : 무작위 접근, 임의 접근, 비순차적 접근 이라고도 함, 어떤 데이터를 기억장소에 기록하거나 거기에서 읽어 낼 때에, 기억 장소에 관계 없이 동일한 접근 시간이 걸리는 접근 방식

sequential access : 순차적 접근, 데이터를 순차적으로 접근하는 방식, 데이터의 위치에 따라 접근 시간이 달라짐

LinkedList(링크드 리스트)

1. 중간 삽입, 중간 삭제는 배열에 비해서 쉽고 빠름

2. 삽입할 때 마다, 메모리 동적 할당으로 삽입을 하기 때문에, 데이터를 삽입하는 속도는 배열에 비해서 느림

3. sequential access(순차적 접근) 만 가능, index 개념이 없음, random access 불가능, 데이터의 위치에 따라 접근 시간이 달라짐

member initializer list 사용시 주의

또다른 HEAP CORRUPTION DETECTED 문제 발생

컨테이너 클래스 vector를 만들었는데

resize 함수에서 , 동적 할당된 배열이므로, delete[] m_pArray를 했는데 HEAP CORRUPTION DETECTED 발생

원인

member initializer list 를 통한 초기화를 할때

m_iSze, m_iCapacity, m_pArray 순으로 초기화 되길 바랬지만, 컴파일러는 멤버 변수 선언 순서대로 초기화 한다, 그래서 m_pArray 부터 초기화를 했고 m_iCapacity가 0값인 상태에서 m_iCapacity + 2를 했으니 실상

2만큼의 크기를 가지는 배열을 초기화 한것

선언 순서를 바꾼뒤 다시 빌드했다

이후 더 이상 HEAP_CORRUPTION_DETECTED 런타임 에러가 발생하지 않았다.

결론

member initializer list 를 통한 멤버 변수 초기화를 할때는, 

생성자()

 : 순서1, 순서2, 순서3  // 이런순으로 초기화 되는게 아니라

{}

멤버 변수 선언 순서로 초기화를 하기 때문에 주의를 하자

template

• 템플릿 매개 변수에 대해 제공하는 인수를 기반으로 컴파일 시간에 일반 형식 또는 함수를 생성하는 구문

• 함수 또는 클래스에 사용되는 자료형이, 특정 자료형에 의존하지 않게 할때 쓰임 ( Generic Programming )

• 여러가지 자료형에 대해서 비슷한 코드를 반복해서 작성하는 것을 방지해줌

함수 템플릿

"template <typename T>" 또는 "template<class T>" 를 함수위에 한줄 작성, 여기서 T는 자료형으로 매크로(#define)처럼 치환될 타입이름, 아직 정해지지 않은 타입이름이다, 많이 쓰이는 이름으로 T가 쓰인다, 꼭 T를 쓰지 않고, T1, T2 등으로 써도 컴파일된다. 

T가 매개변수의 타입으로도 쓰일수 있고, 함수 스코프 안에서 자유롭게 T를 사용할 수 있다

T는 함수 호출할때 , 함수이름<자료형>(); 이런식으로 미리 정해서 호출할 수도 있고

정하지 않고도 81번라인~ 85번라인의 코드처럼 함수를 호출 해도 템플릿 코드가 동작한다.

74번 라인의 경우, OutputType<int>(); 는 T가 int로 치환된것이다

int, float 말고도 사용자 정의 자료형(class)이 들어갈 수 있다.

주의

사용자 정의 자료형을 함수 템플릿의 T로 쓸때 주의할 점은 함수 안에서 비교, 산술 등등의 연산자를 사용하는 경우 사용자가 정의한 클래스에 연산자 오버로딩이 되있어야 한다.

그렇지 않을 경우 error C2676 이 발생 한다

※error C2676 이란? https://docs.microsoft.com/ko-kr/cpp/error-messages/compiler-errors-2/compiler-error-c2676?view=vs-2019

IsSame을 실행 할 수 있게 MyClass에 == 연산자 오버로딩을 해주고, int 형 멤버 변수를 만든뒤, 생성자로 기본값을 설정해야 선언 할 수 있게 만들었다

정상 작동하는걸 볼 수 있다, 즉 template 함수에 내가 만든 클래스형을 인자로 호출 할때는 함수 안에서 연산자를 쓰는지 여부를 잘 파악해야 하며, 연산자를 쓴다면 연산자 오버로딩이 필요하다.

또한 위처럼 typename을 여러 개 둘 수 있다.

클래스 템플릿

클래스를 디자인할때 템플릿을 사용할 수 있다,

단 클래스 선언시에 클래스옆에<자료형>을 붙여서

어떤 자료형이 오게 될지를 먼저 정해줘야 한다.(Template은 컴파일 시간에 동작하기 때문에)

또한 템플릿 클래스의 메소드(멤버 함수)들은 T를 자유롭게 사용할 수 있다.

tem2의 T는 float로 정해졌기 때문에 tem2의 메소드 Output2 인자로 float를 요구하는 걸 볼 수 있다.

주의

template 클래스에서는 위와 같이 헤더파일과 .cpp 파일 분리를 해도, 원활한 분리가 되지 않는다.

빌드를 하면 아래와 같은 링크 에러가 발생한다.

원인

헤더 파일을 .cpp 파일에 include 하게 되면 헤더파일의 내용을 cpp 파일의 맨앞부터 복사 해서 붙여놓은 것과 같다, 컴파일은 .cpp파일에서 하게 되어있다. 필요한 함수 또는 변수 선언이 있다면 헤더파일에서 찾는것이다.

그래서 Template_2_main.cpp 파일의 경우 6번라인에 있는 클래스 CTemplate 을 "CTemplate.h" 파일에서 찾은뒤 T를 int 로 치환해서 instance를 생성한다

문제는 Output 함수의 body를 컴파일 할때는 CTemplate.cpp에서 컴파일을 하는데

CTemplate.h 만 include 한 CTemplate.cpp 파일의 경우 main 함수에서 int 를 T로 정했다는 걸 알 수가 없다. 즉 CTemplate.cpp 에 T를 쓰는함수들은 여전히 동일하게 T인것이다.

그래서 Output 함수를 컴파일 할때 T를 int 로 치환을 안하게 된다

해결책

explicit instantiation

CTemplate.cpp 파일에 위와 같이 explicit instantiation(명시적 인스턴스화)을 해주면 된다.

explicit instantiation 하는법

template 클래스이름<특정자료형>::함수이름(특정자료형 매개변수이름) ;

c++ typeid 연산자

출처 https://docs.microsoft.com/ko-kr/cpp/cpp/typeid-operator?view=vs-2019

typeid(type-id)

typeid(expression)

• typeid 연산자를 사용 하면 런타임에 개체의 형식을 확인할 수 있음
• typeid 의 결과값은 const type_info& 이다, 

출처 https://docs.microsoft.com/ko-kr/cpp/cpp/type-info-class?view=vs-2019

class type_info {

public:

    type_info(const type_info& rhs) = delete; // cannot be copied

    virtual ~type_info();

//--연산자 오버로딩

    _CRTIMP_PURE bool operator==(const type_info& rhs) const;

    type_info&            operator=(const type_info& rhs) = delete; // cannot be copied

    _CRTIMP_PURE bool operator!=(const type_info& rhs) const;

//연산자 오버로딩--

_CRTIMP_PURE int before(const type_info& rhs) const;

    size_t hash_code() const;

    size_t hash_code() const noexcept;

    _CRTIMP_PURE const char* name() const;

    _CRTIMP_PURE const char* raw_name() const;

};

typeid(자료형 또는 변수이름 또는 함수이름 또는 인스턴스 등등).name() 을 실행하면

자료형의 이름을 리턴한다

또한 리턴하는 자료형의 이름은 const char* 라는 것을 알 수 있다

혹시나 해서 const의 위치까지 구분해서 리턴하는지 테스트 해봤는데

const 의 위치까지 따로 구분해서 리턴하지는 않는다

참고로 포인터 변수는 const의 위치에 따라서 아래와 같이 수정 가능한 부분이 다르다

 const 자료형*  : 역참조 값을 수정 X , 가리키는 주소는 수정 O

 자료형* const  : 역참조 값을 수정 O, 가리키는 주소 수정 X

 const 자료형* const : 역참조값 수정 X, 가리키는 주소 수정 X

그러나 typeid(자료형).name() 으로 위 사항들까지는 구별 할 수 없다.

그저 자료형 앞에 const 가 있으면 출력할때

"자료형 const" 으로 출력하고

포인터 변수인 경우 "자료형 * const" 로 출력한다