꿈 꾸는 누렁이

C++에서도 자바스크립트 처럼 익명 함수, 클로져 쓰듯, 사용할 수 있다는게 웹 개발을 해봤던 나로서는 너무 신기하고 놀라웠다. 함수처럼 사용되는 객체 등으로 이미 지원이 되긴 했지만, 

위와 같이 준비를 해야 사용이 가능하므로 불편하긴 마찬가지긴 하다. ( 다른 언어에 비하면 )

자 그럼, 람다 표현식은 다음과 같다.

형식은 위와 같은데, 캡처라는 부분이 사실 처음에 잘 와닿지 않았다. 그런데 자세히 보니, 캡처란? 람다 표현식의 바디 내에서 사용할 외부 변수를 지정해주는 구간일 뿐이었다.

바로 예시를 들겠다.

몸살 감기로 아팠다. 그래서 기념으로 좀 쉬고, 일어나서 포스팅한다ㅠ

먼저, C++ 언어에서의 L-Value와 R-Value에 대해서 정리할 필요가 있다. 너무나도 당연하다고 생각해왔던 것들을 새삼스럽게 정리를 하려고 보니 좀 어려운 면이 없지 않아 있다.

L-Value와 R-Value란?

위의 그림에서와 같이 대입 연산자를 기준으로 왼쪽의 특성을 갖는 요소는 무조건 L Value라고 한다. 이 말은 오른쪽에 위치해도 L Value라고 할 수 있다는 소리다. 그 반대로 대입 연산자를 기준으로 오른쪽의 특성을 갖는 요소는 무조건 R Value라고 한다. 그러나 R Value는 대입 연산자 기준으로 왼쪽에 올 수 없다.

아마 특징과 예시를 보면 L Value와 R Value가 무엇인지 알 수 있을 것이다.

L-Value와 R-Value의 특징

먼저, 그 특징이다.

L value는 보통 변수를 대부분의 예로 들 수 있으며, R value는 임시 객체 혹은 주소 +, - 등의 연산 결과 등이 있다.

그런데 C++에서는 R Value에서 임시 객체라고 하는 것들, 요 부류에 해당하는 것들이 꼭 문제가 된다. 왜냐하면 다음과 같은 경우를 보자.

R-Value에서 문제가 되는 부분

대충 이러한 클래스가 있다.

이 클래스를 기반으로 여러 가지 생성과 동시에 초기화를 할 것이다. 그 생성과 동시에 초기화를 할 때, 두 가지 경우를 보자.

1번의 설명대로, 생성과 동시에 초기화하는 두 경우는 문법 상, 복사 생성자가 호출되는 것이 맞다. 왜냐하면 초기화할 값의 대상으로 객체가 넘어오기 때문이다. 위의 클래스에서처럼 인스턴스화 할 때 동적 할당을 해야하는 경우에는 깊은 복사가 필수이므로, 복사 생성자가 호출되어야 한다.

그런데 자세히 보면 효율적이지 못한 부분이 있다.

AAA b(AAA("ccc")); 이 문장의 경우에는 분명 괄호 안의 AAA("ccc")는 R value 로 임시 객체이며 곧 사라진다. 그렇기 때문에 b 내부의 str을 또 동적 할당하고~, 임시 객체의 str 내용을 또 b의 str에 복사하는 이런 작업을 하지 말고, 2번 처럼 그냥 임시 객체의 str의 주소 값을 b의 str 에 넣어버리고 임시 객체는 그냥 소멸해버리면 되는 것 아니냐?? 어차피 사라질 놈이니까! 

만약에 깊은 복사가 이루어지는 것이 뭐 단순 str 같은 것들이 아니라 100MB 정도되는 동영상이라고 생각해보자. 객체 하나 복사하는데 100MB 짜리가 막 두개 였다가 하나였다가 메모리가 아주 들쑥날쑥 할 것이다.

그러나 실제로는 2번과 유사하긴 하지만 조금 다르게 복사 생략(copy elision)이라는 현상이 발생한다.

또한 이런 경우도 존재한다.

위와 같은 경우도 결국 s 혹은 z 객체는 곧 사라질 객체이기 때문에 새로 생성되는 임시 객체에 값을 전달할 때, 복사 생성자가 호출된다. 

위 경우들 모두 어차피 사라질 객체들이므로, 객체 내의 깊은 복사가 필요한 부분은 그냥 사라질 객체 내의 str 변수의 메모리 주소만 보존하여 가지고 와서 갱신해주고, 객체는 소멸 시켜버리면 된다.

그래서 나온 개념이 r-value 레퍼런스와 이동 생성자이다.

r-value 레퍼런스, 이동 생성자

205라인은 const & 참조자를 이용해 예외적으로 R-value를 잡을 수 있었다. 그러나 [11]부터는 211 라인에서 처럼 r - va lue를 잡을 수 있는 r value 레퍼런스가 등장했는데, 이를 이용하여 r-value가 해당 라인이 종료된 후에도 소멸되지 않고 잡아둘 수 있을 뿐만 아니라, 값의 변경까지 허용한다!

이를 이용하여 만들어진 것이 이동 생성자이다!

이동 생성자와 복사 생성자를 함께 보도록 하자.

위의 이동 생성자로 인해 다음과 같이 복사 생성자의 호출을 막고, 메모리가 새로 할당되고, 복사하고 이런 과정을 막았다. 이는 매우 효율적이다!

결론적으로 이동 생성자는 다음과 같이 보면 된다.

C++ 11에서는 바로 이러한 이동 생성자라든가, R value 레퍼런스 등의 문법 덕분에 자원 문제가 해결되었다. 아래의 내용을 기록하려고 위를 기록한 것이다 결국..

STL 컨테이너 등을 사용할 때, 위처럼 대입하는데에만 복사 생성자가 2번 넘게 호출되며 메모리가 들쑥날쑥할텐데 이동 생성자라든가, 복사 생략 등으로 인해서 자원 효율이 좋아진다는 점이다.

RVO & NRVO

RVO는 Retrun Value Optimization 의 약자이고, NRVO는 Named Return Value Optimization의 약자이다.

뭔가 리턴 값을 최적화 한다는 소리인 것 같은데 다음의 예제를 보자.

위의 두 경우의 함수가 있다. 앞에는 컴파일러에 의해 NRVO 가 적용되는 함수이고, 뒤에는 컴파일러에 의해 RVO가 적용되는 함수이다.

이를 호출할 경우, 두 경우 반환하는 형태가 모두 참조형으로의 반환이 아니기 때문에 복사 생성자가 호출된다!

그러나 실제로는 그렇지 않다.

그렇다고 해서 이동 생성자가 호출된 것도 아니고, 실제로 이동 생성자가 호출되지도 않는다

RVO, NRVO는 반환되는 값에 대해서 최적화하여 복사 생성자가 호출이 되지 않게 하는 것이다. 이동 생성자나 복사 생성자보다 더 우선순위 있게 실행이 된다. 당연하게도 최적화기 때문에 우선순위가 높은 것이다.

그러면 위에서 이동 생성자가 호출된 NRVO 함수 호출은 무엇이었을까?

위의 예시처럼 NRVO가 실행이 안 되는 경우에는 이동 생성자가 호출되는 것이다. 

근데 이게 컴파일러마다 조금씩 다르다 VS 2019 와 g++ 컴파일러에서는 다르게 표현되는 경우도 있고 한 것 같다. 하 이게 정말 별거 아닌 개념인 것 같은데 컴파일러마다 다르고, 이미 올라와있는 11 내용이랑 17, 20에서 바뀐 표준안이랑 살짝 충돌되는 경우들도 있어서 알아보느라 너무 힘들었다 정말.

아래는 사용한 코드이다. 

자 드디어 마지막이다. 지긋지긋하다 정말 ㅋ

코드와 실행결과이다.

지난 포스팅에서 순회까지 끝냈다. 이제 탐색과 삭제가 남았다.

바로 이어서 탐색을 보자.

이진 탐색 트리의 탐색

이진 탐색 트리에서 탐색과 순회는 다르다. 순회는 모든 노드를 방문하는 것을 이야기하지만, 탐색은 가장 효율적이고 적은 깊이로 노드를 방문하여 원하는 값을 찾는 것인가이다.

1번 : 찾으려고 하는 5 값이 루트 노드의 10 값보다 작으니, 왼쪽 서브 트리를 대상으로 하고 인덱스를 옮긴다.
2번 : 찾으려고 하는 5 값이 노드의 4 값보다 크니, 오른쪽 서브 트리를 대상으로 하고 인덱스를 옮긴다.
그 이후 발견.

위와 같이 서브 트리를 대상으로 옮기고, 또 서브 트리의 서브 트리로 대상을 옮기고 하는 과정에서 봤을 때, 재귀로 해결할 수 있다! 탐색 또한 마찬가지로 순회처럼 재귀를 이용하여 문제를 해결해갈 것이다.

코드를 보면 다음과 같다.

매개 변수인 sub_root에는 서브 트리의 루트 노드가 항상 들어온다. 이 서브 트리의 루트 노드와 값을 비교하여 같으면 탐색 완료, 작으면 다시 왼쪽 서브 트리 재탐색을 위한 재귀 호출, 크면 다시 오른쪽 서브 트리 재탐색을 위한 재귀 호출 순서로 조건 및 연산 수행을 진행하면 된다.

이진 탐색 트리의 삭제

아.. 삭제는 ㅋㅋ 여러 유형으로 나뉜다 쉽지가 않다. 왜냐하면? 자식이 없는 단말 노드를 삭제할 경우, 그냥 해당 단말 노드만 제거하면 끝나는 문제이지만 자식 노드가 존재하는 노드를 삭제할 경우 문제가 커진다. 

일단은 그림 형태로 유형 별로 확인한 뒤 코드를 보자.

삭제할 타겟이 단말(리프) 노드인 경우

간단하다. 그냥 끝에 있는 노드이므로 바로 삭제를 하면 되는데, 다만! 삭제할 타겟의 부모의 링크(left or right)가 NULL을 가리키도록 설정해주면 된다. 다음의 그림과 같이 말이다.

위에 해당하는 코드는 다음과 같다.

삭제할 타겟의 자식 노드가 하나만 존재하는 경우

이 경우 또한 간단하다. 아래의 그림과 같은 경우인데 삭제할 타겟의 부모의 링크와 삭제할 타겟이 가지고 있는 하나의 자식 노드를 연결해주면 된다.

위에 해당하는 코드는 다음과 같다.

삭제할 타겟의 자식 노드가 두 개 모두 존재하는 경우

이 경우는 좀 답이 없다. 물론 설명하기 답이 없다는 것이다. ㅋㅋ 좀만 생각해보면 쉽다! 

먼저, 이전의 노드 삭제 유형들처럼 타겟을 삭제하고 부모와 자식을 연결해주는 등의 간단한 방법으로 끝날 문제가 아니다.

삭제할 타겟 노드가 자식 노드를 두 마리나(?) 가지고 있는 바람에 왼쪽 자식 노드의 서브 트리와 오른쪽 자식 노드의 서브 트리를 만족할 수 있는 값으로 대체 노드 선별해야한다. 

아 그러면? 삭제할 타겟 노드의 자식들 중 하나로 선택하면 되는 것 아니냐?

응 안된다. 왜냐하면 그림에 자세히 설명을 해 놓았다. 아래의 그림에서 두 번째 케이스에 해당하는 경우다. 혼돈하지 말아야 한다.

그러면 자식 중에 아무나 하나를 그냥 올리면 안되면 어떻게 올려야 하나?

왼쪽 서브 트리에서 가장 큰 값을 갖는 노드를 대체 노드로 선별하거나,
오른쪽 서브 트리에서 가장 작은 값을 갖는 노드를 대체 노드로 선별해야한다.

두 경우 중 하나를 선택해야 한다. 그 선택은 뭐 개발자 마음이고, 코드 작성자 마음이다. 선택했다면 다음과 같은 순서를 떠올릴 수 있다.

1. 대체 노드의 링크들을 타겟 노드의 링크로 전부 동기화 한다.
2. 대체 노드의 부모의 링크를 적절한 포인터(노드 혹은 NULL)로 변경한다.
3. 타겟 노드를 제거한다.

이러한 순서를 떠올렸는데 여기서 약간의 꼼수(?)를 쓴다고 하며, 지혜를 발휘한다고 읽는다. 뭐냐하면, 대체 노드를 굳이 드러내어 타겟이 있던 자리로 옮겨서 링크를 수정할게 아니라, 타겟 노드의 값만 대체 노드의 값으로 바꿔준다면 링크들을 굳이 변경할 필요가 없기 때문이다. 

1번 연산이 굉장히 부담 그 자체이다. 헤깔려죽겠는데.. 2번과 3번은 어차피 대체 노드에 대해서 해야할 작업이기 때문에 그렇다 치더라도, 1번 연산은 안 해도 될 일을 하는 것과 다름이 없다! ㅋㅋ

그래서 뭐 어찌 되었든 간에 왼쪽/오른쪽 중에 선택을 했다면, 다음 그림으로 그 선택 이후의 과정을 설명한다. 번호 순서대로 색깔과 연관 지어서 차근 차근 읽으면 된다.

이에 따른 코드는 아래와 같으며, 타겟 노드를 루트 노드로 한 서브 트리의 오른쪽 자식의 서브 트리 군에서 가장 작은 값을 선택하여 타겟 노드의 자리에 대체하기로 하였다.

하.. 이로써 삭제까지 끝이다.

일요일에 정말 집중도 안되고, 포스팅을 하면 할수록 코드 작성 때는 떠 올리지도 않았던 세세한 부분까지 의구심이 들어서 시간이 두배, 세배 드는 것 같다.

뭐 다음 시간에는 코드와 실행 결과만 올린다.

여기에 이어서 이진 탐색 트리에 대해서 분석하고 기록할 것이다.

준비 및 구성

먼저, 이전 포스팅에서의 개념과 조건들을 토대로 어떻게 준비할 것인가이다!

트리 구성의 준비물이 되는 노드이다! 노드의 구성은 다음과 같다.

크게 설명할 것이 없다. 이 노드 구조체를 통해서 값과 이진 탐색 트리 조건에 맞는 자식 노드를 가리킬 포인터 2개의 구성이 끝인 것이다. 

이런 구조체로 노드를 생성할 때에는 꼭 다음과 같은 상태로 초기화되는 것이 보장되어야 한다.

트리에 접근하는 방법(루트 노드에 접근하는 방법)

삽입 연산을 하기 이전에 트리에 접근할 때에는 무조건 루트 노드부터 접근을 시작해야한다. 그 루트 노드로의 접근을 어떤 식으로 할 수 있는지, 그 루트 노드를 어떻게 정하는지를 기록한다.

위 코드는 메인 함수 내에서 실행되는 코드로 root 라고 하는 포인터로 트리의 루트 노드를 가리키도록 설계해놓았다.

트리에 노드 삽입 연산

먼저, 삽입 연산은 그림으로 나타냈을 때, 아래와 같다.

위 삽입 연산에 해당되는 코드를 함께 보는게 좋을 것 같다.

먼저, 트리에 노드가 0개 일 때 의 노드 생성이다.

트리에 노드가 1개 이상일 경우에는 다음처럼 삽입 연산을 수행한다.

트리 순회 연산

트리에 노드를 추가만 해서는 뭘 하는가! 순회도하고 탐색도 할 수 있어야, 탐색 트리이지. 먼저, 순회 연산에 대해 알아본다.

하.. 일단(ㅋ) 순회 연산은.. 여러 종류가 있다. 이 여러 종류의 연산 과정을 내 블로그 내에서 최초 도입한 신개념 비디오 장치를 통해 촬영된 것을 올릴 것이다.

일단 트리에서의 순회는 조금 특이하다. 

첫 노드인 루트 노드를 기준으로 한 큰 트리가 존재하지만, 첫 노드의 자식을 기준으로 또 하나의 서브 트리가 존재한다. 이 서브 트리를 하나의 대상으로 연산이 이루어지고, 또 그 자식 노드를 기준으로 또 서브 트리가 존재하며 단말 노드가 될 때까지 서브 트리 군이 형성된다. -> 재귀적으로 문제를 풀 수 있다는 것이다.

그래서 이 순회에서는 재귀를 통해 순회를 진행할 것이다. 삭제 또한 마찬가지이나 다양한 방법들을 넣기 위해서 순회에만 재귀를 적용하도록하고, 삭제에서는 반복문을 통해 삭제를 진행한다.

전위 순회 : 루트 노드를 기준으로 먼저 루트 노드의 값을 읽고, 그 다음 순차적으로 왼쪽 트리를 방문하고, 그 뒤에 오른쪽 트리를 방문하는 방법이다.

서브 트리의 루트 방문(값 Get) -> 왼쪽 링크를 통한 왼쪽 서브 트리 방문 -> 오른쪽 링크를 통한 오른쪽 서브 트리 방문

중위 순회 : 루트 노드를 기준으로 먼저 왼쪽 트리를 방문하고, 그 다음 해당 루트 노드의 값을 읽고, 그 다음 오른쪽 트리를 방문하는 방법이다.

왼쪽 링크를 통한 왼쪽 서브 트리 방문 -> 서브 트리의 루트 방문(값 Get) -> 오른쪽 링크를 통한 오른쪽 서브 트리 방문

후위 순회 : 루트 노드를 기준으로 먼저 왼쪽 트리를 방문하고, 그 다음 오른쪽 트리를 방문한 뒤에 해당 루트 노드의 값을 읽는 순회이다.

왼쪽 링크를 통한 왼쪽 서브 트리 방문 -> 오른쪽 링크를 통한 오른쪽 서브 트리 방문 -> 서브 트리의 루트 방문(값 Get)

레벨 순회 : 레벨 순회는 레벨 1부터 트리의 말단 리프 노드들이 있는 레벨까지 큐 자료 구조에 순서대로 넣고 출력하여 순회하는 간단한 순회 법이며, 레벨 순서 & 왼 -> 오 순으로 순회가 이루어진다.

각 순회의 실제 결과

다음 포스팅은 이진 탐색 트리에서 탐색과 삭제 연산을 포스팅할 것이다.

오늘은 이진 탐색 트리이다. 

이전까지는 선형 자료 구조를 공부했었다. 뭐 예를 들어, 일반 배열 리스트, 연결 리스트, 스택, 큐 등의 선형 구조만 포스팅했는데, 드디어! 비 선형 자료 구조이다. 

데이터가 선형으로 연속되지 않는만큼 삽입, 삭제, 탐색 연산에 신경쓸게 더 많다. 그래도 이렇게 선형을 끝내고 비선형을 진행하는게 뿌듯하긴 하지만 이게 들이는 시간에 비해 결과가 그렇게 크지 않아서 비선형 자료구조를 여러 가지의 예제로 다양하게 진행하지는 못할 것 같고, 핵심만 파악할 수 있는 그런 알찬 예제로 기록을 해 둘 것이다.

나중에 다시 봐도 아~ 이게 트리지 할 수 있도록.

일단은 나는 연결 리스트 기반의 이진 탐색 트리를 구현할 것이며, 데이터의 삽입, 삭제, 탐색(레벨 순회, 전위 순회, 중위 순회, 후위 순회)까지 구현할 것이다. 

배열 기반의 이진 트리는 Heap 자료 구조에서 구현이 될 것인데, 아래의 링크에서 Heap 구조를 알 수 있다. 기본은 Heap이지만 내용은 거의 우선 순위 큐이다. 다만, 큐 형태로 Wrapping만 하지 않았을 뿐...

특이사항이라면,

이전과 마찬가지로 메모리 관리는 기존에 공부했던 배열 기반 스택을 통해 이루어진다. 
레벨 순회를 위해서 배열 기반 원형 큐를 이용한다.

트리를 제외하고 부가적으로 자료구조를 이용할 때에는 메모리를 할당하지 않는 배열 기반으로 

그렇다면 군말없이 바로 시작해보자!

트리란? 

먼저 트리의 구조나 용어를 설명한다. 트리는 이러하다.

트리는 다음과 같이 여러 형태의 트리들이 올 수 있지만

그 중에 이진 탐색 트리에 대해서 기록할 것이다. 위 그림에서 가운데에 있는 트리 구조가 가장 이진 탐색 트리를 잘 나타낸 이진 탐색 트리의 모형이라고 보면 된다.

그러면 이진 트리란?

이진 트리에 논하기에 앞서, 가장 작은 단위인 노드부터 자세히 살펴보면 다음과 같은 구조로 되어 있다.

이런 노드를 요리조리 이용하면 트리를 완성시킬 수 있는데, 노드가 이렇게 최대 두 개의 자식을 가질 수 있는 형태로 이루어져 있으며, 이러한 노드들로 구성되어 있는 트리를 이진 트리라고 한다.

그러면 이진 탐색 트리는 또 무엇인가? 이진 탐색 트리는 이진 트리이긴 한데, 탐색이 가능한 트리라서 이진 탐색 트리라고 한다! 그러기 위해선 일정 조건들이 추가 되어야 하는데 조건은 다음과 같다.

위와 같은 조건을 가지고 있는 이진 트리가 이진 탐색 트리가 될 수 있다.

다음 포스팅은 삽입, 삭제, 탐색을 적절히 나눠서 여러 차례 포스팅한다.

오늘은 덱? 디큐? 라고 불리우는 자료구조이다.

Dequeue 는 매우 혼종이다. 큐라고는 불리우는데 큐의 특징 이외에 스택의 특징을 가지고 있기 때문이다. 선입선출 / 후입선출 등의 개념을 모두 가지고 있다. 먼저 들어온 놈이 먼저 나갈 수 있고, 나중에 들어온 놈이 먼저 나갈 수도 있다는 것이다.

도데체 어떤 구조이길래 위와 같은 특징을 가지고 있을까? 다음과 같다.

위와 같은 구조이다. 뒤에서도 (tail의 사이드) 추가 및 삭제가 가능해야 하기 때문에 꼭 양방향 링크로 구성이 되어야 한다!!!!! 

그런데 뭐, 이제까지 다 다뤄봤던 구조들이기 때문에 예를 들어, 양방향 링크라든지 head와 tail이 함께 있는 구조라든지 어렵지 않은 부분들이므로 간단하게 설명한다.

초기화와 Dequeue의 비워짐 / 꽉 참의 확인

먼저, 초기화는 Head와 Tail 을 NULL로 초기화 하는 것으로 시작한다.

그리고 이러한 초기화에 따라서, Head와 Tail이 NULL 인 경우가 비워진 경우이고, 해당 Dequeue의 꽉 찬 상태는 확인할 필요가 없다. 왜냐하면 연결 기반의 큐이기 때문에 추가하는 수의 제한이 없다고 보면 되기 때문이다.

노드 추가

위 그림으로 설명이 충분하다고 생각한다. 노란색이 추가되는 노드이고, head와 tail 은 각각 옮겨가는 것을 표현한 것이다.

노드 삭제

노드 그림을 그리지 않고 코드로만 설명해도 되겠다고 판단하여 그림을 그리지 않는다. 코드의 주석만으로 충분한 설명이 되었다고 본다.

탐색

탐색은 다른 리스트들과 마찬가지로 링크들을 타면서 순회하는 것이기 때문에 딱히 구현하지 않았다.

메모리 관리

배열 기반의 원형 큐를 통해 메모리 관리를 한다.

소스 코드 및 실행 결과

다음과 같은 배열들을 순회할 것인데, 

전통적인(?), 일반적인 순회 방법과 auto 자동 추론을 이용한 반복과 범위 기반 반복을 각각 실험해본다.

일반적인 순회

일반적인 배열, 벡터, 포인터 배열을 순회하는 평범한 코드이다.

자료형 자동 추론을 통한 순회

auto 키워드를 통해서 인덱스 역할을 하는 변수의 자료형을 알아서 탐지한다.. 너무 편하다 정말

범위 기반 반복 for을 통한 순회

다른 언어에서 지원하는 것처럼 c++도 지원한다. 자바스크립트나 파이썬의 for in과 같고, 자바의 for each 구조와 같다.

전체 코드 및 실행 결과