꿈 꾸는 누렁이

일단, 위의 그래프 기본들을 기반으로 작성되기 때문에.. 링크해둔다.

뭐 BFS니 DFS니 이상한 용어 써가면서 아는 척 오졌던 학과 동기들 보면 이제 이렇게 생각하라. 

대단한 친구들이네

근데 사실, 이상한 용어가 나와서 오히려 겁 먹고 어려울지 모르겠지만 조금만 이해하면 그렇게 어렵지 않다. 

BFS 나 DFS 모두 Search의 일종이다. 뭐 말로만 Search지 순회다 순회. 순회하면서 원하는 값이 나오면 조건문으로 캐치하면 그게 Search이지 무엇이겠는가?

아무튼 두 개념 모두 순회인데, 순회하는 방법이 다르다. 그래서 두 가지를 모두 동시에 기록해 두려고 한다.

DFS (Depth First Search)

DFS는 Depth First Search 로 깊이 우선 탐색이다. 말 그대로 우선적으로 그래프를 깊게 깊게 파고 들어간다는 것이다. 그렇게 전부 파고 들어 갔다면 다시 되돌아 나오면서 깊게 파면서 놓쳤던 주변을 살펴보며 나오는 형식이다.

위 그림과 같은 식인데, 윤성우 교수님의 자료구조 책에서는 다음과 같이 표현한다. "너니까 이야기해주는거야" 하면서 깊고 친한 관계라고 생각하는 친구들에게만 비밀 이야기를 전달한다. 그러다보니 3번과 같은 정점에게도 퍼져있는 비밀 이야기가 소문이 나는 상황에 비유를 하셨다ㅋㅋ

중요한 것은 돌아 나오는 것과 각 정점들의 방문 여부이다. 이 둘을 어떻게 관리하고 코드로써 표현할 것인지가 큰 쟁점이다.

첫째로 돌아 나온 다는 것은 그 발자취를 기록하면 된다. 기록할 때 그냥 순서대로 기록하고 기록한 순서대로 다시 보는게 아니라 돌아나가는 것은 역재생하는 것과 같으므로 스택 자료구조를 이용한다.

둘째로 정점들의 방문 여부는 인덱스 값과 정점 값을 매칭 시킨 flag 역할을 1차원 배열로 처리를 하면 된다.

참고>>

이런 경로 또한 가능하다. 구현해 보면 알겠지만 하나의 정점에 연결된 정점들 중 어떤 것을 선택하는지에 대한 로직은 순회 로직에 들어가지 않는다. 그러니까 시작 정점에서 왼쪽 정점으로 갈지, 오른쪽 정점으로 갈지를 중요시 하지 않는다는 소리이다. 이는 정점간 연결을 나타내는 자료구조 내에서 어떤 순서로 연결 정보를 저장했는지에 따라서 다르게 나온다. 그니까 어떤 경로든 해당 탐색의 기본 원리에만 들어 맞다면 경로 순서의 맞고 틀리고를 따지는건 의미가 없다는 소리이다.

BFS (Breadth First Search)

반면에 BFS는 Breadth First Search 로 너비 우선 탐색이다. 말 그대로 우선적으로 넓게 넓게 퍼뜨리며 그래프를 파고들겠다는 것이다. 그러니까 어떤 정점을 순회하기만 했다 하면 바로 그냥 그 해당 정점에 연결된 모든 정점에게 방문하는 것이다. 

이건 약간 예로 들자면, 정책 발표에 따른 메시지 퍼짐이다! 출발 지점에서 정책을 발표한다. 그 양 옆 정점은 그 해당 정책을 티비를 통해 실시간으로 들은 정점들이고, 그리고 나서 그 실시간으로 들은 정점들이 지인을 만날 때마다 그 정책에 대해서 이야기하는 모습 같다고 비유할 수 있다.

중요한 것은 방문/순회 차례에 대한 기록과 각 정점들의 방문 여부이다. 이 둘을 어떻게 관리하고 코드로써 표현할 것인지가 큰 쟁점이다. 

첫째로 물론 각 정점들의 방문 여부는 위에서와 마찬가지로 flag 역할의 1차원 배열로 충분하다. 

둘째로 방문/순회 차례에 대한 기록은 위 DFS와는 조금 다르다. 방문한 정점과 연결된 정점들을 모두 방문하고, 그 다음 순서까지 정한 뒤 넘어가야헌다 그것이 BFS에서의 순회라고 보면 된다. 그러기 위해서는 꼭 순서를 기록해야한다. 그렇지 않으면 순회에 비효율이 생길 수 있다. 이 때 사용하는 것이 큐이다

이렇게 두 개념을 코드를 통해 구현해 볼 것이다 

공부하고 나면 그 때 그 때 정리해야한다는 것을 뼈저리게 느끼는 시작이다..

이번에 정리할 내용은 단순 배열 리스트이다. 다만, 그냥 배열을 쫘르륵 순회하고, 삭제 띡 하고, 추가하고 그러면 일반 배열 사용법을 정리하는 것과 다를 바가 없으므로, 약간 형식이 있는 리스트 틱한 배열로 만들어 정리한다ㅋㅋ

일단은 정의와 특징, 장 단점을 간단하게 상기시키며 넘어가도록 하겠다.

단순 배열 리스트란?

말 그대로 단순한 배열이다. 그런데 리스트라는 자료구조 형태이므로 메모리 공간 뿐만 아니라 삽입, 삭제, 탐색에 대한 함수를 추가 보완함으로써 하나의 자료 구조로 완성을 시킬 셈이다.

배열 리스트의 장점

Random Access, 임의 접근이 인덱스를 기반으로 가능하기 때문에 데이터의 참조가 쉽다.  O(1) <- 개쩐다ㄷㄷ

배열 리스트의 단점

배열의 길이가 초기에 결정되며, 이 길이는 변경이 불가능하다.
삭제 과정에서 데이터의 이동이 매우 많이 일어난다.
탐색할 경우 최악의 경우에는 O(n)이다. <- 매우 성능이 나오지 않는 것이다. 데이터의 수에 매우 정비례하여 시간이 늘어나기 때문이다.

코드 구현 및 실행

---

---

클래스와 배열 및 this 포인터

• 객체 배열

객체 배열은 다음과 같이 일반 배열 방식으로 선언할 수도 있으며, 동적 할당을 통한 방식으로 선언할 수 있다.

다만, 동적 할당이든 일반 배열이든 객체 배열을 선언할 때에는 각 배열의 요소 객체들마다 생성자 및 소멸자를 호출하지만 생성자의 경우 호출할 생성자를 명시하지 못한다 인자 전달이 불가능하고 무조건 인자가 없는 생성자만을 호출한다. 즉, 인자가 없는 생성자가 반드시 정의되어 있어야 한다. 각 배열의 요소를 초기화 시키기 위해서는 일일이 초기화를 시켜줘야 한다.

• 객체 포인터 배열

객체 포인터 배열은 객체의 주소 값 저장이 가능한 포인터 변수로 이뤄진 배열이다.

• this 포인터

this 포인터는 객체 자신을 가리키는 용도로 사용되는 포인터로 멤버 함수 내에서 this라는 이름으로 사용할 수 있는 포인터이다. 객체 자신의 주소 값을 나타내는 포인터이다.

11번 라인에서 출력한 this 포인터를 출력한 결과와 17번 라인의 객체 a의 주소 값을 출력한 결과가 같은 것으로 보아 this 포인터는 객체 자기자신의 주소를 나타내는 포인터이며 다음과 같이 활용한다.

• 자기 참조자의 반환

This 포인터를 이용하여 자기 참조가 가능하도록 참조 정보를 반환할 수 있다. 17번 라인에서 참조 정보가 반환되고, 30번 라인에서 거듭된 접근 연산을 통해 멤버 함수를 호출하는데 이는 참조 값을 반환하고 그 반환된 참조 값을 이용해서 다시 접근하기를 반복하기 때문에 가능하다.

28번 라인에서 대입 연산자를 기준으로 a의 참조 정보(참조 값이) rA 참조자에 전달이 된다.

포인터와 배열

l 배열 이름과 포인터의 관계

다음은 배열의 이름이 무엇인지를 나타내는 예제이다.

위의 소스에서 확인할 수 있는 부분은 배열의 이름 그 자체를 출력했을 때의 값과 배열의 [0]번째 요소의 주소 값이 같다는 점이다. 즉, 배열의 이름은 해당 배열의 시작 주소 값을 의미한다.

결국 배열의 이름 또한 ‘주소 값’을 지니고 있다는 관점에서 포인터와 그 개념이 매우 유사하다. 그렇다면 포인터 변수처럼 배열의 이름 또한 주소를 대입해볼 수 없을까? 배열의 이름에 주소 값을 대입하는 예제이다.

8번 라인에 새로운 변수 number를 선언하고, 10번 라인에서 배열의 이름에 number의 주소 값을 넣었다. 왜 배열의 주소가 아니라 일반 변수의 주소를 넣었느냐? 왜냐하면 배열의 이름은 배열의 ‘시작 주소’ 하나를 저장하기 때문에 배열 이름의 입장에서 보면 어떤 하나의 변수의 주소 값을 대입한 것과 다를 바 없이 보이기 때문이다. 그렇기 때문에 배열의 이름에 하나의 변수 number의 주소 값이 대입되는 것은 문제가 되지 않는다. 이렇게 배열의 이름에 변수의 주소를 넣은 결과, 10번 라인에서 배열 타입의 표현 식에 할당하는 부분에서 에러가 발생한다. 그 이유는 배열의 이름은 주소 값을 저장하고 가리키지만 처음 정해진 배열 이름의 값은 변경이 불가능하다. 즉, 배열의 이름은 상수 값이다. 그도 그럴 것이 특별하게 배열을 선언하여 만들었는데 그 배열의 이름을 대표하는 배열의 이름이 가리키는 요소를 마음대로 바꾸게 되면 무엇을 위해 배열 이름을 지정해가며 배열을 생성했겠는가?

다음은 위에서 배열과 포인터의 관계에 대해 내린 결론을 정리하여 나타낸 표이다.

배열 이름은 포인터 변수와 같은 특성들을 지니고 있지만 상수라는 차이점이 있다. 그래서 배열 이름을 ‘포인터 상수’ 라고도 표현한다. 포인터 변수와 배열 이름은 변수이냐, 상수이냐 의 차이점 밖에 없기 때문에 그 차이를 제외하면 포인터 변수와 배열 이름은 완전히 같다. 그렇기 때문에 다음의 예제가 가능하다.

10번 라인에서 배열 이름(포인터 상수)의 값을 포인터 변수에 대입시키고 있다. 이것이 가능한 이유는

1.     포인터 변수에 포인터 상수를 대입 -> 전혀 문제될 것이 없다.

2.     대입 연산자를 기준으로 l-value와 r-value의 형(type)이 같아야 한다.
-> l-value : int * / r-value : int * == int형 (시작) 주소 로 문제될 것이 없다.

배열 이름의 포인터 형은 배열의 이름이 가리키는 대상을 기준으로 결정되기 때문에 r-value 배열 이름의 자료형은 정수형 변수 공간의 시작 주소이므로 int * 가 맞다.

포인터 변수에 포인터 상수를 대입하게 되면 포인터 변수를 이용하여 배열 이름처럼 인덱스로써 접근하는 방법으로 각 요소에 접근을 할 수 있다. 즉, 포인터 변수를 배열의 이름처럼 사용할 수 있다는 것이 결론.

그렇다면 그 반대로 배열 이름(포인터 상수)을 가지고 포인터 연산을 할 수 있을까? 다음은 이에 관한 예제이다.

11번 라인에서 배열 이름과 ‘ * ‘, 애스터리스크 연산자를 이용한 포인터 연산이 진행되고, 12번 라인에서는 배열 이름과 인덱스를 이용한 배열의 0번째 요소에 접근하여 출력을 한다. 11번 라인에서는 배열 이름이 가지고 있는 값 즉, 배열의 시작 주소에 접근하여 해당 값을 출력하기 때문에 0번째 요소를 출력한다.

• 포인터 연산

포인터를 이용하여 참조 뿐만 아니라 증감 연산이 가능하다. 다만 일반 수를 이용한 연산에 비해서 연산이 많이 제한 된다.  -> 가능한 연산자 수의 제한

포인터 연산에서 중요한 포인트

1.     덧셈, 뺄셈, 참조 연산만 가능하다.
-> 곱셈, 나눗셈 등의 연산을 불가능하다.

2.     덧셈, 뺄셈 연산은 일반 수를 통한 덧셈, 뺄셈 연산과는 다르다.
-> 포인터 연산에서의 +1과 수에 대한 +1에서 1은 각각 의미가 다르다.

다음은 포인터에 + 연산자를 이용하여 1씩 더하는 예제이다.

int, char, double 자료형 별로 배열을 선언하고, 각각에 대한 포인터 변수를 선언하여 각 배열의 첫 시작 주소(배열 이름)를 대입시킨 상황에서 각각 포인터 연산을 진행하는 예제이다.

먼저, 자료형에 상관없이 배열 이름과 인덱스를 이용하여 요소별 주소 값을 출력한 결과와 포인터 연산에 대한 결과를 출력한 결과가 모두 동일함을 알 수 있다. 그렇다면 도대체 + 연산자를 이용하여 포인터 변수를 포인터 연산한 것이 어떤 의미가 있길래 각 요소의 주소를 출력한 결과와 같은 결과인가?

1.     A의 결과에서 pArr과 pArr+1 값의 차이는 4이다.

2.     B의 결과에서 pCrr과 pCrr+1 값의 차이는 1이다.

3.     C의 결과에서 pDrr과 pDrr+1 값의 차이는 8이다.

단순히 포인터 변수에 +1 연산을 했을 뿐인데 그 증가의 차이는 자료형 별로 다른 결과가 나타났다. 포인터 연산은 피연산자로 오는 그 대상이 메모리 주소인 만큼 메모리 주소에 대한 연산이 이루어지는데 이 메모리는 무작정 작은 단위인 1바이트 별로 보는 것은 의미가 없다. int 형의 경우에는 4바이트 전부 참조해야 비로소 값이 의미가 있듯이 자료형 별로 최소 참조 바이트가 존재한다. 그렇기 때문에 주소에 대한 연산인 포인터 연산은 자료형 별 최소 참조 바이트를 반영하여 증감을 진행한다. 각 자료형 별로 포인터 연산에 대해서 1의 의미가 모두 다른 이유가 바로 이 때문이다. 1의 증감은 최소 참조 바이트 한 블록을 증감한다는 의미가 되기 때문이다.

포인터 연산에서 1의 의미는 sizeof(해당 자료형)*1 이 된다.
포인터 연산에서 2의 의미는 sizeof(해당 자료형)*2 이 된다.
…
포인터 연산에서 n의 의미는 sizeof(해당 자료형)*n 이 된다.

그렇다면 다음의 예는 무엇을 의미하는가?

*(p + 1)
p는 임의의 변수를 가리키고 있는 포인터 변수

이는 다음과 같이 해석할 수 있다.

P가 가리키고 있는 주소에 sizeof(해당 자료형) * 1만큼을 더한 주소를 참조(*)한다.

 다음은 그 예제이다.

위와 같은 포인터 연산에서의 성질과 예제를 통해서 알 수 있는 결론은 다음과 같다.

배열 이름[i] == *(배열 이름 + i)
혹은
포인터 변수[i] == *(포인터 변수 + i)

완전히 같다.

• 문자열과 포인터

c언어에서 문자열을 표현할 때 두 가지 방법으로 표현한다.

1.     배열을 통한 문자열의 저장

2.     포인터 변수를 통한 문자열의 저장

먼저, 첫 번째 방법인 배열을 통한 문자열의 저장이다. 이 경우에는 str 배열의 길이가 자동 계산되어 각 인덱스 별로 문자를 하나씩 저장하여 해당 문자열의 끝에 ‘\0’을 저장함으로써 문자열의 저장이 비로소 완료되는 형태이다.

그러나 두 번째 방법인 포인터 변수를 통한 문자열의 저장의 경우이다.  c언어 프로그램 상의 모든 상수는 CPU를 이용한 연산의 대상이 되기 위해서는 해당 상수가 메모리 상에 적재되어야 한다. “hello, my name is yoo seung ho!” 문자열은 상수로서 메모리에 적재되고, 그 시작 주소인 ‘h’의 주소 값이 반환되어 pStr 포인터 변수에 대입이 된다.

대입 연산자를 기준으로 l-value는 char * 형이고, r-value는 문자열의 시작 주소 값 즉, char * 이기 때문에 대입 연산에는 아무런 문제가 없다.

각 두 경우는 위 그림의 왼쪽과 오른쪽 형태로 동작한다. 배열의 이름의 경우 포인터 상수이기 때문에 가리키는 타겟 문자열을 변경할 수는 없지만, 변수 형태, 배열에 값이 저장되어 있기 때문에 대상이 되는 문자열의 내용에 대해서는 변경이 가능하다. 포인터의 경우 포인터 변수이기 때문에 가리키는 타겟 문자열을 변경할 수 있다. 그러나 그 대상은 상수 형태의 문자열이기 때문에 대상이 되는 문자열의 내용에 대해서는 변경이 불가능하다.

사실은 아래와 같이 되는 것이다.

• 포인터 배열

말 그대로 포인터 변수들로 배열을 이룬 형태를 말한다.

1차원 배열

• 배열

둘 이상의 변수를 모아 놓은 것.

• 배열의 선언

일반 변수의 선언과 같다.

‘ 자료형 + 배열 이름 + 길이 정보(인덱스) ‘ 형식.

위의 선언을 메모리 공간 상의 그림으로 표현하면 다음과 같이 나타낼 수 있다.

arr 배열

• 배열의 접근

배열의 인덱스는 배열의 개수를 [n] 으로 두었을 때, 0부터 시작하여 n-1까지 존재하며 [0]은 첫 번째 요소를, [n-1]은 마지막 요소를 나타낸다.

• 배열의 선언과 동시에 초기화

다음은 배열의 선언과 동시에 초기화하는 예이다.

여기에서 우리는 중괄호 내의 초기화 값 리스트를 ‘초기화 리스트’ 라 부른다. 8번 라인의 경우에는 일반적인 선언과 동시의 초기화 방법이다. 9번 라인의 경우는 배열의 길이 정보가 주어지지 않은 상태인데 이는 초기화 리스트를 보고 자동으로 계산하여 배열의 길이가 세팅 된다. (위의 예에서는 5) 마지막으로 10번 라인의 경우는 배열의 길이보다 적은 초기화 리스트가 오게 되는데 0번째 인덱스부터 순차적으로 초기화 리스트의 값들이 할당되고 할당할 초기화 값이 없는 인덱스 요소에 대해서는 전부 0으로 자동 초기화한다.

• 배열 이름을 대상으로 하는 sizeof 연산자

sizeof(배열이름); 을 실행할 경우, ‘ 바이트 단위의 배열의 크기 ’가 반환된다.

• 문자 배열과 문자열 배열

같은 ‘ hello ‘를 표현하는 배열인데 두 배열은 전혀 다른 배열이다. 9번 라인은 문자만을 저장한 문자 배열이고, 12번 라인은 문자열을 저장한 문자열 배열이다. c언어에서 배열에 문자열을 저장할 때에는 ‘\0’ 이라는 문자열의 끝을 나타내는 특수 문자인 널(null) 문자를 문자열의 제일 끝에 자동으로 삽입하여 대입 및 저장을 행한다. ( 이는 문자열을 입력 받는 라이브러리를 통한 변수로의 입력 시에도 마찬가지로 null 문자의 자동 삽입이 이루어진다. )
이 null문자를 이용하여 메모리 공간 상에서 배열 이름의 첫 번지부터 어디 까지가 의미 있는 문자열의 끝인지를 확인한다. 또한 이러한 문자열 배열에 대한 입출력 서식 문자는 ‘ %s ‘ 로 사용한다.