바다에 퐁당 Ꙭ̮ ꉂ ◡̈⋆*

https://boycoding.tistory.com/250

 
모든 멤버 함수는 함수가 호출된 객체(인스턴스)를 가리키는 this 포인터를 가지고 있다.
호출된 객체의 주소를 가리키는 상수 포인터다.
상수 포인터 자료형이므로 포인터 자체가 다른 것을 가리키도록 할 수는 없다.
모든 과정은 컴파일러에 의해 자동으로 수행된다.
 
그러나, 명시적으로 this를 참조해야 하는 경우가 있다.
 
- 첫째, 멤버 변수와 이름이 같은 매개 변수를 가진 생성자(또는 멤버 함수)가 있는 경우, this를 사용해서 구분할 수 있다. 

class Something
{
private:
    int data;

public:
    Something(int data)
    {
        this->data = data;
        // this->data는 멤버 변수이고,
        // data는 매개 변수
    }
};

 
- 둘째, 클래스 멤버 함수가 작업 중이던 객체(인스턴스)를 반환하는 방식이 유용할 때가 종종있다. 이렇게 하면 같은 객체의 여러 멤버 함수를 연속해서 호출할 수 있는 방법이다.
만약 각각의 멤버 함수가 *this를 반환한다면 체이닝 기능이 있는 새로운 버전의 Calc를 만들 수 있다.

class Calc
{
private:
    int m_Value = 0;

public:
    Calc& Add(int value) { m_Value += value; return *this; }
    Calc& Sub(int value) { m_Value -= value; return *this; }
    Calc& Mul(int value) { m_Value *= value; return *this; }

    int GetValue() { return m_Value; }
}

int main()
{
    Calc calc;

    calc.Add(5).Sub(3).Mul(4); //함수 체이닝

    cout << calc.GetValue() << endl; // 8
    return 0;
}

출처: https://boycoding.tistory.com/250 [소년코딩:티스토리]

- Priors are a key component of Bayesian modelling. 

The Gaussian prior on the coefficients

→  coefficients are assumed to be distributed according to Gaussian/Normal distribution.

!= Gaussian prior over the error terms

→  Those are two different assumptions with very different effects

https://stats.stackexchange.com/questions/476706/what-does-it-mean-to-have-a-gaussian-prior

- recoloring이든 reconstruction이든, 부모를 검은 색으로!!!
 

레드블랙트리는, 자가 균형 이진 탐색 트리 중 하나이다.

Properties of Red Black Tree

1. 모든 노드는 빨간색 혹은 검은색이다.
2. 루트 노드는 검은색이다.
3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
4. 빨간색 노드의 자식은 검은색이다.
   == No Double Red(빨간색 노드가 연속으로 나올 수 없다)
5. 모든 리프 노드에서 Black Depth는 같다.
   == 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다

 
레드-블랙 트리에 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다. 
이렇게 되면 4번 조건이 위배되는 상황이 발생한다. 즉, 빨간색 노드가 연속으로 2번 나타날 수 있다(Double Red)
 
레드 블랙 트리는 이러한 Double Red 문제를 해결하기 위해 2가지 전략을 사용한다.
 

새로 삽입할 노드를 N(New), 부모 노드를 P(Parent), 조상 노드를 G(Grand Parent), 삼촌 노드를 U(Uncle)라고 하자. 즉, 삼촌 노드는 말 그대로 부모의 형제라고 생각하면 된다. 
 
Double Red가 발생했을 때 

• 삼촌 노드가 검은색이라면 -> Restructuring을 수행하면 된다.
• 삼촌 노드가 빨간색이라면 -> Recoloring을 수행하면 된다.

Restructuring

1. 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다.
2. 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다.
3. 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.

Recoloring

1. 새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.
   1-1. 조상(G)이 루트 노드라면 검은색으로 바꾼다.
   1-2. 조상(G)을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.

1-1) simple reconstruct 결과 root가 빨간색이 되어버린 경우

1-2) simple reconstruct 결과 부모 위에서 double red가 나타난 경우

-> double red가 나타난 지점 중 아래 노드를 기준으로, uncle을 살펴본다 (uncle이 검은 색이면 reconstruct, 빨간 색이면 recolor)
 

https://code-lab1.tistory.com/62

선형 자료 구조(연결 리스트, 스택, 큐 등): 순차적으로 요소에 접근

트리 자료구조는 노드들을 방문하기 위해 다른 방식을 사용해야 함

트리 순회(Tree Traversal): 트리의 모든 노드들을 방문하는 과정 - 주로 세 가지가 있음: 전위 순회, 중위 순회, 후위 순회

전위 순회와 후위 순회 모두 Recursion을 통해 간단하게 구현 가능.

특히, 두 순회는 print 코드가 Recursion 코드의 이전에 있는지 / 이후에 있는지에 따라 나뉨.

1. 전위 순회(Preorder Traversal)

: Work at a node is performed before its children are processed

2. 후위 순회(Postorder Traversal)

: Work at a node is performed after its children are processed

https://yoongrammer.tistory.com/70

macOS에서 memory leak 체크하려다
-valgrind는 너무 유용하고 간단한 툴이지만: 리눅스 환경에서만 실행된다는 소식...
-sanitizer는 과제 환경인 g++ 컴파일러가 아닌 clang 컴파일러에서만 실행된다는 소식...

그렇게 알게된 게 'leaks'
macOS에서 valgrind의 역할을 해주는 요긴한 친구다 ❤️
하지만 leaks를 실행하기 위한 코드를 컴파일코드의 '어디'에 넣어야 할지 몰랐고, 이를 이해하면 과제에서 주어진 makefile의 문법을 알아야 했다. 역시 프로그래밍은 성급히 하면 오히려 꼬이고 세 배의 시간이 소요된다는 것.. ㅎㅎ 처음부터 찬찬히 해보니 성공했다!

1. makefile 친숙해지기 (아래링크에서 완벽 정리)
https://hwan-shell.tistory.com/188

나의 makefile

CC = g++-11 --std=c++17
RD = rm -f
DoublyLinkedList.o: DoublyLinkedList.h DoublyLinkedList.cpp
	$(CC) -c DoublyLinkedList.cpp

part1_main.o: part1_main.cpp DoublyLinkedList.h
	$(CC) -c part1_main.cpp

part1_main.out: DoublyLinkedList.o part1_main.o
	$(CC) DoublyLinkedList.o part1_main.o -o part1_main.out

part2_main.o: part2_main.cpp DoublyLinkedList.h
	$(CC) -c part2_main.cpp

part2_main.out: DoublyLinkedList.o part2_main.o
	$(CC) DoublyLinkedList.o part2_main.o -o part2_main.out

clean:
	$(RD) *.o

→ 근데 결론은,, Makefile을 수정하지 않아도 됐더라는 것..! ㅋㅋ
그래두 이제 Makefile 읽을 수 있음
 
1. 일단 첫 번째는 DoublyLinkedList.o를 만들기 위한 코드임.
2. 두 번째는 part1_main.o를 만들기 위한 코드임. 앞에 Make 쳐주면 됨.
 
하지만, 내가 실제로 커맨드로 입력하는 코드는 $make part1_main.out (과제 명세) 임.

2. brew install leaks

사랑스러운 leaks를 mac에 설치하는 커맨드임

3. 아래 영상을 따라함

https://www.youtube.com/watch?v=bhhDRm926qA

이 영상이 진짜 최고임...
 
+추가 →근데 이거 볼 것도 없음. 위 영상에서 다 설명해줌.
https://stackoverflow.com/questions/59122213/how-to-use-leaks-command-line-tool-to-find-memory-leaks

커맨드라인에 이하를 입력

export MallocStackLogging=1 

→ memory leak과 관련된 모든 log를 터미널창에 출력해주도록 설정하는 것(option)

 
make part1_main.out

→ executable file 생성

 
leaks --atExit -- ./part1_main.out

→ 현재 디렉토리의 part1_main.out를 실행하는데, memory leaks을 detect하고 그 결과를 보고하라!
 

• leaks -atExit : tells which leaks exist, but not where any leaked allocation came from
• MallocStackLogging : creates logs that can tell me where the leaked allocations came from, but the logs are automatically deleted when the program exits, and leaks -atExit runs, obviously, at exit

실행 결과

2 7
1 1
R
L
P 2
L
L
P 3
V
1 2 1 3 
part2_main.out(10555) MallocStackLogging: stack logs deleted from /tmp/stack-logs.10555.1008e8000.part2_main.out.0iRX5O.index
Process 10555 is not debuggable. Due to security restrictions, leaks can only show or save contents of readonly memory of restricted processes.

Process:         part2_main.out [10555]
Path:            /Users/USER/*/part2_main.out
Load Address:    0x10082c000
Identifier:      part2_main.out
Version:         0
Code Type:       ARM64
Platform:        macOS
Parent Process:  leaks [10554]

Date/Time:       2023-10-23 14:19:02.367 +0900
Launch Time:     2023-10-23 14:18:53.129 +0900
OS Version:      macOS 13.1 (22C65)
Report Version:  7
Analysis Tool:   /usr/bin/leaks

Physical footprint:         3585K
Physical footprint (peak):  7601K
Idle exit: untracked
----

leaks Report Version: 4.0, multi-line stacks
Process 10555: 228 nodes malloced for 117 KB
Process 10555: 0 leaks for 0 total leaked bytes.

leaks(10554) MallocStackLogging: stack logs deleted from /tmp/stack-logs.10554.104b18000.leaks.MUDEON.index

0 leaks for 0 total leaked bytes. !!!!

나의 소중한 코드에세서는 다행히 leak이 detect되지 않음...🥰🥰🥰

0. 주의

- 단순 BST 문제와 & Optimal BST 문제는
- 다루는 자료구조 자체는 BST로 동일하지만, 주목하는 특징이 서로 다르다.
 
(1) BST의 경우 Search가 궁극 목적이다. 즉 Binary Tree 자료구조를 통해 우리가 아는 Binary Search(이진 탐색)을 해내는 게 핵심이다. (ex. 숫자 맞추기 게임에서 Up/Down를 알 수 있다고 하면, 일반적으로 가능한 범위를 반으로 잘라서 정중앙의 숫자를 말하는 것이 가장 효율적 - 점차 정답의 범위를 반씩 좁혀나감) 따라서 각 노드에 저장된 숫자(키/데이터)의 양적 비교가 중요하다.
 
(2) Optimal BST의 경우 
형태는 BST로 똑같다. 그러나 이 경우 노드에 저장된 숫자의 양적 비교가 중요하지 않다. 오히려, 각 노드에 저장된 데이터는 문자열과 같이 더 다양한 데이터가 들어갈 수 있고, 우리가 '양적 비교'의 대상으로 고려해야 할 수치는 데이터 자체의 값이 아니라 메타데이터, 즉 데이터의 '검색 빈도(확률)' 및 각 데이터의 검색을 위한 '함수 호출 횟수'이다. 이들을 계산하여 '평균 검색 시간'을 최소화하는 트리 구조로 업그레이드시키는 것이 핵심이다.
 
따라서 완성된 Optimal BST의 모습을 보면, 1번 이진트리와 같이 숫자가 정렬된 상태가 아니다. 오히려 노드 데이터 자체는 마구잡이로 unsorted되었을 가능성이 높다. 노드의 정렬 기준이, 메타데이터 연산 결과를 Minimize하는 것이어야 하기 때문이다.

1. BST (Binary Search Tree) 이진 탐색 트리 (이진 트리 중 하나)

 
BST: ordered set (순서 가능한 집합)에 속한 원소(key)로 이루어진 Binary Tree
* Binary Tree: 각 노드의 자식의 수가 최대 2개인 트리
- 이진 트리 (Binary Tree: 각 노드의 자식의 수가 최대 2개인 트리) 이다.
- 왼쪽 자식 노드의 값은 자신의 값보다 작아야 한다.
- 오른쪽 자식 노드의 값은 자신의 값보다 커야 한다.
- 서브트리도 BST이다.
- 값이 중복되는 노드는 없다.
 
BST는 그 나름대로 풀어야 할 문제들의 특징이 있다!
 
https://gsmesie692.tistory.com/m/115

2. Optimal Binary Search Tree 최적 이진 검색 트리

→ Dynamic Programming으로 최적화
 

Goal: 평균 검색 시간이 제일 낮은, 가장 효율적인 트리를 찾자

1) 전제: 각 검색어의 검색 빈도(확률)이 다를 수 있다
ex) Crystal = 0.1 / Daisy = 0.2 / Beatrice = 0.3 / John = 0.4
 
2) 평균 검색 시간: 각 검색어의 검색 빈도(확률) p와, 검색을 위한 함수 호출 횟수(시간 복잡도) c의 가중합

- '평균'이라는 말에 마지막에 개수로 나눠야 하지 않는가 하고 생각할 수 있지만, 이미 '확률'을 곱하여 더하므로 그 자체로 평균이 됨
- 각 검색어의 검색 빈도는 상수임 (고정된 Input)
- 따라서 검색어들을 어떤 형태의 BST로 구성하느냐에 따라 c가 달라져서 전체 평균 검색 시간이 달라지는 것!
ex)

왼쪽: (0.1*1) + (0.2*2) + (0.3*2) + (0.4*3) = 2.3
오른쪽: (0.1*4) + (0.2*3) + (0.3*2) + (0.4*1) = 2.0
 

Problem Solving - Algorithm

1. brute-force

: 모든 경우의 수는 2^(n-1) →exponential
 

2. Dynamic Programming

- Bottom up
- 시간 복잡도: n^3 (for문이 3겹)
- Optimal Substructure: 어떤 BST의 왼쪽, 오른쪽 서브트리가 각각 최적 BST여야, 해당 BST도 최적이다. 
- 메모를 위한 Table(Tabular) 2개 & for문만이 필요하다!!
 
노드(Key)가 1~n개 있다고 하자: K_1 ~ K_n
 

1) Table A:

 K_i부터 K_j까지 최적의 BST로 정렬되어있다고 한다면, optimal 평균 검색 시간을 A[i][j]에 메모
- 원소가 하나인 트리의 경우, 원소를 찾는데 비교를 딱 한 번 하므로 A[i][i] = p_i
 

어떤 Optimal BST가 있고 그것의 root가 Key(Node)k라고 하자.
그러면 그것의 left subtree가 최적이고, right subtree 또한 최적이다.
(최적이 아니라면 그걸 cut 하고 더 최적인 subtree로 paste하면, 현재보다 더 좋은 bst가 된다. 그러나 이는 현재가 optimal bst라는 가정에 모순된다)
 
왼쪽 서브 트리의 최적 값은 A[1][k-1]로 메모되어 있음
오른쪽 서브트리의 최적 값은 A[k+1][n]로 메모되어 있음
- 이때 Key k를 트리의 root로 추가해서 전체 트리를 만든다면, 각 서브 트리에서의 비교 횟수는 기존의 비교 횟수에 추가로 한 번만 더 비교를 하면 됨(각 subtree의 노드마다, 검색을 위한 함수 호출 횟수가 1씩 늘어나기 때문임)
- root에 대한 평균 검색 횟수는: 1(depth) x p_root = p_k
→ 둘을 합친 전체 트리의 최적 값은 (A[1][k-1] + p_1 + ... p_k-1) + p_k + (A[k+1][n] + p_k+1 + ... + p_n)

2) Recurrence Relation

수많은 경우의 수 중 최적의 값은 반드시 존재한다(최솟값)

→ 1부터 n까지가 아니라 i번째부터 j번째까지의 key로 일반화

이 식을 이용해서 2차원 table A를 채워나가서, A[1][n] 의 값을 얻으면 그것이 최적 BST의 평균 검색 시간(최적값)이 됨

3) Table R:

R[i][j]:  K_i부터 K_j까지 최적의 BST로 정렬되어을 때, optimal BST의 root의 인덱스 메모 (A 배열에 최적값을 넣는 순간의 k값)
 
- R의 필요성: A만으로 최적값은 구할 수 있지만 최적 BST의 모양을 알 수 없음
- root 인덱스가 저장되어 있으면, root 이후의 노드 인덱스는 어떻게 아는가? Recursion에 의해 채워진다. 즉, 루트가 된 노드가 k번 노드라고 치면 그 왼쪽 서브트리의 루트노드 (즉 k번 노드의 left child)는 R[1][k-1], 오른쪽 서브트리의 루트노드는 R[k+1][n] 이 된다. 이런 식으로 R 배열의 값들을 이용해 재귀함수를 호출해주면서 노드를 만들어나가면 최적 BST가 만들어진다.
 

https://gsmesie692.tistory.com/m/116 
⭐️⭐️

https://hi-guten-tag.tistory.com/73