꿈 꾸는 누렁이

미루고 미뤄왔던 보간 탐색에 대한 포스팅이다!!!

위에는 보간 탐색의 기반이 될 탐색의 원리를 설명해 놓은 글이다. 무려, 4개월 ~ 5개월 전에 내가 작성했던 글이다. 지금 봐도 상당히 디테일하게 잘 작성한 것 같은데 , 코드라던가 실행 결과 등을 제대로 올리지는 않았더라.

그래서 이번 포스팅에서 보간 탐색과 함께 이진 탐색의 재귀적 구현, 이진 탐색의 반복문 구현까지 원쁘라스투(1+2) 형태로 포스팅 들어간다.

먼저, 보간 탐색이 Main 이니 보간 탐색에 대해 살펴보도록 한다.

보간 탐색이란?

이진 탐색을 살짝 더 효율적으로 개선한 것이다! 기존의 이진 탐색의 경우 다음과 같이 탐색이 진행되는데,

3번의 이진 탐색이 진행되었고, 그 3번의 이진 탐색 안에는 수 많은 계산들과... 수 많은 조건 검사 등으로 인해 그냥 선형 순차 탐색만도 못한 효율이 나와버렸다. 그 이진 탐색 시켜주려고 정렬까지 한 것을 생각해보면 억울하다. 

물론.. 미미한 성능 차이이고, 데이터가 더 많고, 타겟이 더 안쪽에 있었을 때에는 분명히 이진탐색이 개쩔긴하다ㅋㅋ 예를 들기 위해서 극단적으로 말해본 것이다.

왜 위와 같이 선형 순차 탐색보다도 못한 결과가 일어났을까? 왜냐하면...

첫 번째, 데이터가 생각보다 앞에 있었기 때문이다.
두 번째, 죽으나 사나 수행하는 반 절 나누기로 인해서 절반 지점부터 시작하는 탐색 시작 위치가 문제이다.

그래서 데이터가 극 초반이나, 극 후반에 존재할 경우에도 계속 반절부터 시작할꺼냐! 라는 생각에서부터 시작되었다.

첫 번째 원인은 타겟이 치우져 있는 것은 우리가 어떻게 할 수 없는 것이다. 사용자가 찾겠다고 하는 타겟이 거기 있는걸 무슨 수로 해결하는가?

그렇다면 두 번째, 앞으로 절반 지점부터 시작하지 않으면 되지않을까? 

그래서 이렇게 바꿔봤다. 이 공식은 아마도 수학 센세들이 힘들게 연구한 공식이 아닐까 한다. 저 공식은 

"내가 찾는 값과 그 값이 저장되어 있는 위치는 비례하기 때문에 전체 길이에서
대충 이 정도 어디쯤에느으으은~~ 있지 않겠는가?"

를 이야기하는 공식이다. 그럴 수 밖에 없는게 이진 탐색과 마찬가지로 정렬되어 있는 데이터 세트를 대상으로 하기 때문에 당연히 전체 길이에서 찾으려는 값은 어림잡아 이쯤에 있겠거니 하고 추측해볼 수 있는 것이지 않겠는가?

그래서 그걸 실제로 구현해 본 예이다.

그런데 다음과 같은 예에서 탈출 조건에 문제가 있다. 

위의 조건대로 데이터 세트와 타겟을 2로 조정하여 실행해보면 실행이 무한 루프에 빠진다. 즉, 탈출 해야하는데 탈출 조건을 충족시키지 못해서 무한 루프에 빠지는 것이다.

그렇다면 왜 이전 탈출 조건인 start <= end 조건은 먹히지 않는걸까? 그 이유를 아래에 정리해 보았다.

그도 그럴 것이, 새로 정의된 공식으로 인해서 정해지는 index 값은 "너가 찾는 타겟 값은 전체 길이 중에 대충 어디어디 쯤에 있어~" 라고 이야기해주는 것과 같다. 그렇다보니, 아무리 start 와 end 가 갱신된다고 하더라도 이전과 비슷한 index 값을 계산해서 내놓을 확률이 높다. 더군다나 start가 1밖에 증가하지 않은(범위가 겨우 인덱스 하나 줄어든) 상황에서는 더더욱 그럴 확률이 높다. 이런 와중에 갱신된 범위가 target이 포함되지 않는 상황까지 되어버린 것이다. 그러면 아주 그냥 삼위일체이다.

위의 예시 상황으로 보자면 다음과 같은 입장들이 되는 것이다.

새 공식 曰 : target 2는 인덱스 0 쯤에 있어~, index = 0 ~
start, end 曰 : 오 마침 index가 0이고 index+1이 start로 넘어오니 결국, 범위가 하나 밖에 안 줄었네?
arr[start], arr[end] 曰 : 3 ~ 9 값이군.
target 曰 : 난 2인데!!!! 왜 3 ~ 9를 보고 있냐!!! 다음 재귀 호출 때 탈출해라!!!
                   [ 재귀 호출 ]
탈출 조건 曰 : 응~ start <= end 조건 성립해서 탈출 안 해 ~
새 공식 曰 : (범위가 하나 줄은 것 가지고는 결과는 그대로겠네..?) 음.. 뭐.. target 2는 인덱스 0쯤에 있어~, index = 0 ~
                   [... 무한 반복 ...]
컴파일러 曰 : '신발장 크레파스 놈들이!!!!!!!!!!!!!!!!!!!!! 꽥(무한 루프 터.짐.)'

위의 대화가 탈출 조건과 새 공식의 순서가 코드와 조금 다르긴 하지만 문제는 없다. 결국은 같기 때문이다.

뭐 위 대화까지 보고도 이해가 안된다면 내 잘못이다. 설명을 못한 것이다. 근데 이게 글로만 설명하기 겁나 애매하고 짜증난다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

아래는 코드와 실행결과이다. 탈출 조건까지 최종 수정된 보간 탐색과 이진 탐색의 재귀적 구현과 반복적 구현까지 모두 넣어 놓은 3종 세트인 것이다.

코드와 실행 결과

없는 값으로 인해 탐색 실패 결과

탐색 성공

기수 정렬이다. 드디어 정리할 시간이 다가왔다.

Q. 기수 정렬에서 기수란 무엇인가?

A. 숫자 표현(진법체계)에 기준이 되는 수를 뜻한다. 예를 들자면 16진, 10진, 8진, 2진 등을 기수라고 한다.

Q. 그럼 기수 정렬은 무엇인가? 기수를 통해서 어떻게 정렬을 이뤄내는가?

A. 예제를 통해서 보겠다.

정렬이 되는 대상들을 하나의 진법 속 요소들로 가정하고,

해당 진법 배열에 값을 모두 넣은 후, 단순히 순서대로 꺼내기만 한다.

이런 식으로 동일한 기수의 요소들끼리 해당 기수의 버킷을 이용하여 정렬이 이루어지는 것이 기수 정렬이다.

중요한 것은 해당 기수의 버킷에 넣고 다시 버킷의 처음부터 순서대로 꺼낼 뿐이다. 그러니까 값의 비교가 이루어지지 않는다는 것이다! 그렇기 때문에 정렬할 대상들에 따라 반복문을 여러 번 사용해야할 수도 있고, 중간에 갑자기 진행을 끊을 수도 있으며, 정렬할 수 있는 대상이 제한이 되기도 한다.

예를 들어, 1, -5, 100 이런 요소들에 대해서는 정렬이 불가능하다. - 를 기수 버킷으로 어떻게 표현할 것이란 말인가?

다음으로 간단한 숫자 정렬하는 예제를 보겠다.

코드 및 실행 결과

지난 이야기..

문제점

뭐 위와 같은 문제들이 있다. 위의 문제의 전제는 등록되는 수는 100명도 안되고, 거의 그대로지만 번호만 오지게 큰 스케일로 변환되는 경우이다. 

해결 아이디어

그러면 어떻게 하면 될까? 

큰 인덱스 키 값의 크기를 줄이면 된다!

<인덱스를 축소 변환하는 과정>

1. 어차피 등록되는 인원은 100명이 안될 것이기 때문에 20171300 ~ 20171399 라고 범위를 어림 잡는다 
2. 그러면 말이 20171300 부터 20171399까지 이지 결국엔 0부터 99까지라고 봐도 문제가 없다.
3. 그렇다면 인덱스를 대입하기 전에 20171300이 오면 무조건 0으로 변환해주고, 20171344가 오면 무조건 44로 변환해주며, 20171399가 오면 무조건 99로 변환해주어 인덱스에 대입되도록 하면 어떨까?
4. 등록번호 % 100 을 한 결과라면 무조건적으로 위의 결과를 얻는다.
5. 그렇다면 user acc[100] 을 그대로 넣고 acc[uid%100] 으로 접근하면 배열의 크기를 비정상적으로 늘리는 고민을 해볼 필요도 없게되는 것이다.

이러한 과정에서 축소 변환해주는 역할을 하는 것을 해쉬(hash)라고 하며, 해당 역할을 하는 함수를 해쉬 함수라고 한다.

해쉬 함수는 다음과 같다. 겁나 간단하다.

이러한 해쉬 함수는 위에서 밑줄 친 것처럼 다양한 값의 형태에 따라 달라진다. 해쉬되어야 할 키 값의 상황? 문맥? 에 따라서 적용되는 해쉬 함수의 내용이 달라지고, 정답이 없다는 뜻이다.

적용된 코드 분석

등록을 할 때에 hash 함수를 이용하며,

값을 꺼낼 때에도 hash 함수를 이용하여 인덱스를 축소 변환하여 인덱싱한다.

전체 코드 및 실행 결과

그런데 또 문제점

짜증나게 또 문제가 발생하는 것이다.. 이번엔 등록해야하는 수가 갑자기 늘어나 버려서 다음과 같은 현상이 발생하는 것이다. 

1. 한 200명~300명 정도 난다.
2. 그래서 배열의 길이를 넉넉하게 user acc[400]; 정도로 주었다.
-> 이 방법 또한 썩 마음에 들지 않는다. 왜냐하면 등록 수가 늘어날때마다 계속 변경을 해줘야 하기 때문이다.
3. 그런데 문제는 여기서부터이다. 20171350과 20171450의 해쉬 결과는 50으로 같다.
-> 왜냐하면 100으로 나눈 나머지이기 때문에!(직접 나눠보라)
4. 20171350 등록 번호인 사람과 20171450 등록번호인 사람의 해쉬 결과가 50으로 같으므로 둘다 acc[50]에 정보가 등록될 것이다.. 그러니까 먼저 저장되는 값은 손실 된다는 의미이다. 원래 기대 결과는 20171350은 [50]에 20171450은 [150] 에 저장되는 것을 기대했는데 말이다.

지금 두 가지 문제가 발생하였다.

첫 번째는 문제는 등록되는 수가 넘쳐날 때마다 테이블의 크기를 갱신해야하는 상황이 발생한다.

두 번째는 문제는 분명히 다른 등록번호임에도 불구하고, 해쉬된 결과로 같은 인덱싱 번호가 나왔다. 

먼저, 두 번째 문제와 같이 같은 해쉬 결과가 나오는 것을 충돌(Collision)이라고 한다. 이러한 충돌을 막으려면 어떻게 해야할까? 해쉬 함수를 기가 막히게 잘 만들어야 한다. 해쉬 함수는 해쉬하려고 넘어오는 키 값의 범위나 종류나 형태, 양상에 따라 달라질 수 있기 때문에 매우 주관적이며, 답이 없다. 

A회사에서 만든 해쉬 함수가 기가 막히게 성능이 잘 나오다가도 B회사에서 A회사의 해쉬 함수를 쓰면 동작이 잘 안될 수도 있다. 그렇지만 최대한 공통으로 적용할 수 있는 여러 알고리즘? 들이 존재한다.

자릿수 선택, 폴딩 방법, 선형 조사법, 이차 조사법, 이중 해쉬, 체이닝 ... 등

이렇게 여러 방법들이 존재하지만 이 방법들의 공통점은 해쉬 해야할 키 값을 어떻게 변환해야 충돌이 덜 일어나는가에서부터 시작하는 방법들이다.

가장 좋은 해쉬 방법을 만드는 것은 키 값의 부분을 활용하여 해쉬된 키 값을 만들 것이 아니라, 키 값의 전체를 활용하여 해쉬된 키 값을 만들어야 한다는 것이다.

위의 예제에서도 키 값의 마지막 두 자리 수만 가지고 장난질 했기 때문에 문제가 되었다. 키 전체를 활용할수록 콜리전이 발생할 확률이 매우 낮아진다.

첫 번째 문제는 해쉬 함수의 구현에 따라 달라진다. 해쉬 함수를 통해 변환되는 해쉬된 키 값의 범위를 어떻게 정하느냐에 따라 적절한 할당 크기를 정할 수 있기 때문이다.

테이블과 해쉬 등은 성능은 좋지만 이러한 충돌(collision) 문제로 인해, 그리고 키를 이용하여 제어해야하는 곳에서만 주로 사용해야하기 때문에 사용되는 곳이 제한된다. 

테이블과 해쉬를 살펴봤는데 해쉬 테이블은 기본 동작 원리나 문제점 그리고 적용 가능한 작업의 특징 정도로만 공부하고 넘어가는게 좋을 것 같다.

자 오늘은 테이블과 해시이다.

자료구조는 자료를 저장하는 구조를 나타내는 것이지만, 그 구조 속에 들어 있는 값을 찾아서 꺼내는 것 또한 자료 구조의 영역 범위 내이다.

그래서 배열 리스트, 연결 리스트, 스택, 큐, 그래프, 트리 등에서 탐색에 해당하는 부분을 구현해왔다. 그 중 테이블이라는 자료구조에 대해 볼 것인데, 이 구조는 특별하다. 탐색 속도가 어마어마하게 빠르다. 기록해보자.

테이블이란 무엇인가?

이것이 테이블 자료구조이다. 키와 값으로 구성되어 있는 구조를 테이블 자료구조이다. 보통 언어에 따라 다르지만 키와 값으로 구성되어있는 자료구조를 사전(Dictionary), 맵(Map) 구조라고도 한다.

테이블 자료 구조에서의 핵 중요한 규칙

1. 테이블 자료구조에서는 키와 값이 한 쌍의 형태로 이루어 저장이 된다.
이 때 값은 뭐 하나가 되어도 좋고 여럿이 되어도 좋다.

2. 테이블 자료구조에서는 키 값은 중복되어서는 아니 된다.
아래의 그림을 보자

학생을 관리하는 테이블이다. 소위 말하는 학번이라는 것은 각 학생들에게 부여되는 고유 번호이다. 그러니까 학번 1번을 외치는 것만으로도 수 많은 학생들 중에서 '나루토'를 특정 지을 수 있어야한다. 이것이 실생활에서 적용되는 예이다. 

그런데 위의 테이블에서 학번 3번을 부르면 네! 하고 손을 드는 학생이 에렌과 아르민으로 두 명인 상황이 만들어졌다. 이런 경우에는 학번을 부르고 나서 이름까지 불러야 그제서야 에렌과 아르민을 특정 지을 수 있는 것이다.

만약 이런 상황에서 3번으로 중복되는 에렌과 아르민이 포함되어 있는 전교생 수천명이 시험을 본다고 생각하자. 그러면 자동적으로 OMR 채점을 진행할텐데 이 때 기계는 각 학생들을 구분할 때, 학번을 이용하여 학생을 특정 짓지만 에렌과 아르민 자식들이 포함되어 있는 경우가 존재하기 때문에 모든 학생들을 대상으로 학번과 이름을 한 번에 확인해야한다.

테이블 자료구조에는 보통 키 값을 이용하여 데이터를 특정짓기 때문에 위와 같은 경우를 만들지 않기 위해서 키의 중복을 허용하지 않도록 하겠다. (뭐 허용을 시키는 경우도 있긴 하지만 말이다.)

3. 키가 없으면 값을 저장할 수 없다.

키를 활용해 값을 특정 지어야 하기 때문에 키를 비울 수는 없다.

4. 값을 특정 짓는다는 것의 의미.

위 그림을 봤을 때, 3번이라는 학번을 통해 에렌을 특정 지었는데 달리 말하면 탐색이 완료되었다는 소리이다. 

이 개념들을 숙지한 채로 아래의 예시를 보면 된다.

기본적인 테이블 예시

테이블이 될 구조체 정의

구조체 정의를 이용하여 배열로 선언하면 테이블 형태의 구조를 만들 수 있다.

테이블에 데이터를 등록하는 함수

인덱싱이 특이하다는 것을 확인할 수 있다.

메인 함수 실행 부분

임의로 입력된 값을 키 값으로 활용한다.

49번 줄에서는 키 값을 이용해 원하는 값을 바로 뽑아낸다. 이런 것이 가능한 이유가 무엇인가? 

데이터를 삽입할 때, 키의 값 '번째'에 해당하는 배열 칸에 넣었으니,

값을 뽑아올 때에도 키를 인덱스로 던져주면 키의 값 '번째'에 해당하는 배열 칸에서 뽑아온다.

말이 탐색이지, 사실 탐색이라고 할 것도 없이 그냥 인덱싱일 뿐이다. 그냥 *(배열이름+인덱스(키값)) 이렇게 연산해주면 접근 가능하기 때문에 포스팅 초반에 겁나 빠르다고 한 것이다.

전체 코드 및 실행 결과

문제점

근데 위와 같은 테이블은 빠른건 빠른거지만 중요한 문제가 있다.

1. 학번이 원래 0부터 100까지의 자리였지만 갑자기 년도+번호와 같은 식으로 변해버리면 분명히 문제가 된다.
원래 99번이었던 번호가 20210099로 바뀐다면 이 또한 문제가 될 것이다. 

기존의 방법대로라면 user acc[20210100]; 이렇게 선언을 해야, 20210099 같은 인덱스가 먹혀도 먹힐 것이다. 그런데 이러한 크기의 배열 선언이 과연 정상일까?

모든 키가 0부터 시작해서 뭐 적절히 1,000 값으로 끝나면 좋겠지만 실제로는 그렇지가 않다. 학번은 보통 해당 년도와 고유 번호를 합쳐서 만든다. 군번은 말할 것도 없다 이런 번호 키들을 수용하기 위해서 user acc[20210100]; 이렇게 비정상적인 배열 선언을 할 수도 없는 노릇이다.

이를 다음 포스팅 때 해결하고자 한다.

앞선 내용들을 바탕으로 진행하기 때문에 읽고 나서 읽는 것을 추천한다. 설명을 잘 하지 못해서 읽어도 모를 수도 있다. 이 글들은 복습을 위한 기록이니, 잘 못 알아 듣겠으면 다른 곳 가서 읽기를 권한다ㅋㅋㅋㅋ ㅜㅜ

일단 먼저 BFS가 뭔지에 대한 내용은 위 링크 중 땡땡 우선 탐색이라는 글에 좀 더 자세하게 정리되어 있고, 이 글에서는 BFS 방법으로 순회하는 과정을 나타낼 것이다.

중요 핵심

일단 너비 우선 탐색은 깊이 우선 탐색과 달라도 너무 다르다. 현재 정점 하나에 연결되어 있는 모든 정점에 순회를 해야하다보니 현재 정점에 연결된 각 정점마다 순서를 매겨서 기록해야 한다.

깊이 우선 탐색은 현재 정점에서 다음으로 갈 타겟을 정하기만 한다면 정점 방문(순회)과 현재 정점의 갱신이 한 번에 발생한다. 

그러나 너비 우선 탐색의 경우에는 정점 방문이라는 개념을 좀 더 확장해야한다. 단순히 방문만 하는 것이 아니라, 방문 후에 방문한 해당 정점을 큐 자료 구조에 넣는 작업까지가 정점 방문이라고 생각해야한다.

그리고 정점 방문과 현재 정점의 갱신이 동시에 발생하지 않는다. 정점 방문과 현재 정점의 갱신을 동시에 해버리면 나머지 연결되었던 정점에 접근할 기회가 박탈된다.

위의 예에서 현재 정점이 0이고 (ㄱ, ㄴ)처럼 1 정점을 방문한 뒤 바로 현재 정점으로 갱신을 해버리면 0 정점에 연결되어 있던 2 정점에 접근할 수 있는 기회가 사라진다. 그렇기 때문에 정점의 방문과 현재 정점의 갱신이 동시에 발생하지 않는 것이다. 

이러한 이유 때문에 진짜 설명하기에 겁~~나 헤깔린다. 이러한 핵심적인 특징을 인지한 상태로 프로세스를 봐야한다.

순회 프로세스

먼저 다음과 같은 그래프에서 순회를 시작할 것이다.

정점 0은 시작 정점이므로 일단 방문 처리가 자동으로 된다. 정점 방문에 해당하는 부분이 순회라는 표현이고, 이는 접근 + 큐 기록 까지를 의미한다. 접근했다는 의미 또한 방문 Flag 배열에 값을 갱신하는 조작을 의미하는 것이다.

현재 정점에 연결된 모든 정점을 순회하는 과정이다.

현재 정점인 0 정점에 연결된 모든 정점에 대해서 순회가 완료되었으니, 큐에서 값을 꺼내서 그 값을 현재 정점으로 갱신하고, 다시 순회를 시작한다.

그리고 큐에 정점이 여전히 존재하므로 다시 큐에서 값을 빼내어 현재 정점을 갱신하고, 순회를 재시작한다. 그런데 2 정점 같은 경우는 순회 가능한 인접 정점이 없으므로 그냥 나가리~

큐에 정점이 여전히 존재하므로 다시 큐에서 값을 빼내어 현재 정점을 갱신하고, 순회를 재시작한다. 4 정점이 마지막 정점이긴 하지만 그림을 한 눈에 보는 우리나 아는 것이지 컴퓨터는 4 정점이 마지막 이라는 것을 아직 모른다! 그렇게 때문에 4 정점이 마지막이어도 원래 규칙대로 큐에 넣는다.

큐에 정점이 아직 존재하니 뽑고, 뽑힌 값으로 현재 정점을 갱신한다. 그런데 현재 정점에서 순회를 하려고 보니, 순회 가능한 인접 노드가 없다. 

그렇게 더 이상 큐에 값을 넣지 못하고, 큐가 비었으므로 모든 그래프를 순회했으므로 종료한다. 

0 -> 1 -> 2 -> 3 -> 4 순으로 순회가 이루어졌다.

진짜 뇌리에 박히겠다 박히겠어 정말 ㅋㅋ

이제 관련된 부분 코드를 보도록 하겠다.

코드 분석

큐가 새롭게 사용되므로 큐에 대한 코드가 필요한데 이미 만들어놓았던 배열 기반의 큐 코드를 활용할 것이다. 그런데! 그냥 큐는 배열 관리가 까다롭기 때문에 더 효율적인 배열 기반의 원형 큐를 사용할 것이다!

깊이 우선 탐색 코드에 대해서 바뀌는 부분과 추가되는 부분을 기록하겠다.

너무나도 기쁘게도 이거 하나가 변경된다.

ㄱ~ㅅ 순서대로 읽으면 된다.

전체 코드 및 실행 결과

전체 코드는 배열 기반의 원형 큐와 연결 리스트 BFS로 인해 변경된 그래프 코드 순으로 업로드를 하겠다.

배열 기반의 원형 큐 ArrayBasedCircleQueue.h -- -- -- -- -- 

연결 리스트 linkedlistforgraph.h -- -- -- -- --

BFS 로 인해 변경된 그래프 코드 BreadthFirstSearchGraph.cpp -- -- -- -- --

아래는 실행 결과이다.

이 두 탐색을 이용한 최소 비용 신장 트리 부터 해서 트리 부분의 AVL 트리, 해쉬 테이블 등등 더욱 복잡한 것들은 지금까지 포스팅 한 것들을 복습한 이후에 조금씩 업로드를 진행할 것이다.

그노므 DFS! DFS! 드디어 깔끔하게 정리를 한다. 이 탐색 기법 하나에 워낙 들어가는 내용이 많기 때문에 바로바로 정리하지 않으면 다시 처음부터 공부하는 수준으로 공부를 해야한다 흑흑...

이전의 포스팅의 내용을 기반으로 작성되기 때문에 이전 부분을 포스팅을 참고하라고 올려놓겠다.

중요 핵심

일단은 깊이 우선 탐색은 아래 세 가지가 핵심이다.

1. 깊이 접근하는 것
2. 왔던 경로를 되돌아오는 것
3. 정점 방문 여부를 기록하는 것

이 세 가지를 핵심으로 기록하겠다. 사용되는 예시는 간단하게 다음과 같다.

첫 번째, 깊이 접근한다는 것은 한 정점에서 연결되어 있는 정점 중 하나의 정점을 선택해서 파고 들어가고 또 그 정점에서 연결된 정점 중 하나의 정점을 파고 들어가는 식의 방법을 이야기 한다.

1로 갈지, 2로 갈지는 중요하지 않다. 0이라는 정점에 연결 되어 있는 정점이 1 먼저 연결되있는지, 2 먼저 연결 되어있는지에 따라 다르다. 즉, 정점의 연결 정보를 나타내는 연결 리스트의 정렬 구조에 따라서 1 노드와 2 노드 중 어떤 것을 선택하게 될지 결정된다는 소리이다. 어찌됐건 우리는 순회 하는 것이 목적이므로 어딜 먼저 방문하는지는 의미가 없다.

두 번째, 왔던 경로를 되돌아오는 것은 되돌아오면서 놓친 정점을 순회해야하는 것이다. 이 때 경로를 다시 되돌아오려면 경로를 일단 기록을 해야하는데 역행이므로 스택의 형식대로 기록하면 된다. -> 방문 추적을 목적으로 스택을 사용한다.

세 번째, 정점 방문 여부를 기록한다는 것은 일반 순차 배열을 이용하여 기록한다. 다음 그림에 설명을 포함시키겠다.

주요 3가지 핵심에 대해서 살펴보았고 이번엔 그 순서대로 그려볼 것이다...

순회 프로세스

시작 정점 0을 방문된 상태로 시작한다. -> 방문 Flag 배열에서 정점 0을 True 처리.

연결된 인접 정점은 1 정점과 2 정점인데 방문 Flag 배열을 봐도 방문 처리가 False이기 때문에 두 정점 모두 접근이 가능하다. 이 예에서는 2 정점을 방문하겠지만 1 정점으로 방문해도 순회 순서만 다를 뿐 다른 의미는 없다.

2 정점을 방문하면서 방문 Flag 배열에서 2 정점을 True(방문) 처리하고, 떠나온 0 정점은 다시 돌아가기 위한 발자국으로 남기기 위해서 스택에 넣는다.

위와 마찬가지 과정을 통해 2 정점을 떠나면서 스택에 2 정점을 넣고, 3 정점을 방문한 뒤 방문 Flag 배열의 3 정점에 대한 방문 여부를 True로 변경한다.

또 마찬가지로 같은 과정을 반복하는데 3 정점에서는 1 정점과 4 정점에 접근 가능하다 어디로 가든 상관없지만 이번 예에서는 4 정점에 방문할 것이다.

4 정점에서는 인접한 정점이 모두 방문 처리 되었으므로 이제 스택에서 값을 POP 함으로써 되돌아 가면서 그냥 지나친 정점을 탐색한다.

3 정점으로 돌아왔을 때, 보니까 1 정점을 방문하지 않고 그냥 지나쳤었기 때문에 1 정점에 방문한다. 이 때, 1 정점에 방문하기 위해서 3 정점을 떠나는 것이니 1 정점 방문 이후 다시 돌아오기 위해 3 정점을 다시 스택에 넣는다. 그리고 1 정점에 대한 방문 처리를 진행한다.

그리고 1 정점에서 인접 정점 모두 방문 처리 되었으니 Pop을 통해 돌아가고, 3 정점에서도, 2 정점에서도 마찬가지로 인접 정점 모두 방문처리 되었으므로 Pop을 통해 돌아가다가 0 시작 정점까지 Pop하여 스택이 빈 경우 비로소 모든 순회가 끝난 것이다.

0 -> 2 -> 3 -> 4 -> 1 순으로 순회가 이루어졌다.

진짜 뇌리에 박히겠다 박히겠어 정말 ㅋㅋ

이제 관련된 부분 코드를 보도록 하겠다.

코드 분석

스택이 새롭게 사용되므로 스택에 대한 코드가 필요한데 이미 만들어놓았던 배열 기반의 스택 코드를 활용할 것이다. 스택 설명 기록은 아래의 링크에서 확인하면 된다.

먼저 바뀌는 부분과 추가되는 부분이다.

그래프 내의 방문 Flag 배열이 추가 된다.

방문 처리를 수행하는 함수가 추가된다.

깊이 우선 탐색을 수행하는 함수이다.

한 함수이지만 라인 수를 맞춰서 읽으면 된다... 이전 자료구조인 스택에 대한 사용 방법 또한 익혀야 하고 너무나도 추상적이라서 용어 설명이 너무 어려운 것 같다..ㅠ.ㅠ

그래프 종료 및 메모리 공간 해체 관련 코드이다.

전체 코드 및 실행 결과

전체 코드는 배열 기반의 스택과 변형된 연결리스트(오름차순으로 노드를 삽입; 이전에는 그냥 삽입했다.), DFS로 인해 변경된 그래프 코드 순으로 업로드 한다.

배열 기반의 스택 ArrayBasedStack.h -- -- -- -- --

변형된 연결 리스트 linkedlistforgraph.h -- -- -- -- --

DFS로 인해 변경된 그래프 코드 DepthFirstSearchGraph.cpp -- -- -- -- --

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

뭐 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에서의 순회라고 보면 된다. 그러기 위해서는 꼭 순서를 기록해야한다. 그렇지 않으면 순회에 비효율이 생길 수 있다. 이 때 사용하는 것이 큐이다

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

드디어 그래프의 기본 코드이다.

이전 포스팅에서 설명했듯이, 그래프를 표현하는 방법 중 인접 리스트 방법을 이용하여 기본적인 그래프를 구현해 볼 것이다. 그 인접 리스트에 해당하는 방법 또한 이미 이전에 포스팅 한 코드를 기반으로 만들 것이다. 해당 리스트 코드는 따로 첨부하도록 할 것이다.

먼저, 그래프를 만드는데 있어서 연결 리스트 자료구조를 이용한다. 그래서.. 하 골치 아프게거니 하다가 C++ STL의 리스트를 그냥 활용할까 했는데, 그래도 내가 전에 만든거 테스트도 할 겸, 그걸로 하자! 라고 생각해서 내가 만든 리스트를 100% 신뢰하며 쓰기로 결정했다. 

이미 구현된 자료구조는 100% 신뢰하며 쓰는 것이 국룰이다.

그래프 초기화 및 정점 추가

그래프를 초기화 한다는 것은 코드 작성자 나름이고 기능에 따라 더 무언가 있겠지만, 나는 정점을 추가하는 용도로 사용되었다. 

간선 추가 

이런 식으로 간선이 연결되며 연결된 그래프의 모양은 대충 다음과 같다.

그래프 출력

각 정점 노드 별로 리스트 내에 제공하는 show 관련 함수를 이용하여 출력을 해주면 된다!

출력 결과는 다음과 같다.

리스트 구현할 때, 헤드 부분을 바보 같이 잘못 이해하고 잘못 구현했었다.. 그냥 가리키는 포인터로 두면 될 것을 노드로 처리해버려서.. 아무튼 노란 부분은 무시해도 전혀 문제 없다.

그래프 소멸

그래프가 겁나 어려울 줄 알았는데 생각보다 구현하기 쉬웠다. 다만 탐색에 대한 부분들이 들어가 있지 않기 때문에 모르고 하는 소리일 수 있으나, 진짜 생각했던 것 만큼 어렵지는 않다. 다만 그래프는 이전 자료구조들을 많이 활용하기 때문에 처음부터 구현하기에는 조금 까다로운 것은 사실이다.

다음 포스팅은 탐색에 대해서 하나하나 기록해볼 것이다.

---

코드들이다. 그래프 실행 결과는 이미 위에 있기 때문에 코드만 업로드한다.

그래프 코드