macOS에서 memory leak 체크하려다 -valgrind는 너무 유용하고 간단한 툴이지만: 리눅스 환경에서만 실행된다는 소식... -sanitizer는 과제 환경인 g++ 컴파일러가 아닌 clang 컴파일러에서만 실행된다는 소식...
그렇게 알게된 게 'leaks' macOS에서 valgrind의 역할을 해주는 요긴한 친구다 ❤️ 하지만 leaks를 실행하기 위한 코드를 컴파일코드의 '어디'에 넣어야 할지 몰랐고, 이를 이해하면 과제에서 주어진 makefile의 문법을 알아야 했다. 역시 프로그래밍은 성급히 하면 오히려 꼬이고 세 배의 시간이 소요된다는 것.. ㅎㅎ 처음부터 찬찬히 해보니 성공했다!
→ 근데 결론은,, Makefile을 수정하지 않아도 됐더라는 것..! ㅋㅋ 그래두 이제 Makefile 읽을 수 있음
1. 일단 첫 번째는 DoublyLinkedList.o를 만들기 위한 코드임. 2. 두 번째는 part1_main.o를 만들기 위한 코드임. 앞에 Make 쳐주면 됨.
하지만, 내가 실제로 커맨드로 입력하는 코드는 $make part1_main.out (과제 명세) 임.
3. '$make part1_main.out'는 part1_main.out를 만드는 makefile 문법이 반영된 커맨드임. 이걸 터미널에 입력하면, makefile의 세 번째 코드가 실행됨. 세 번째 코드의 오른쪽 부분을 살피면, "part1_main.out를 만들기 위해서는 DoublyLinkedList.o와 part1_main.o가 필요하다"는 것을 알 수 있음. 이를 위해, 아까 언급한 첫 번째 두 번째 코드가 실행되는 것임.
→ 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
- 단순 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이다. - 값이 중복되는 노드는 없다.
1) 전제: 각 검색어의 검색 빈도(확률)이 다를 수 있다 ex) Crystal = 0.1 / Daisy = 0.2 / Beatrice = 0.3 / John = 0.4
2) 평균 검색 시간: 각 검색어의 검색 빈도(확률) p와, 검색을 위한 함수 호출 횟수(시간 복잡도) c의 가중합
⭐️
- '평균'이라는 말에 마지막에 개수로 나눠야 하지 않는가 하고 생각할 수 있지만, 이미 '확률'을 곱하여 더하므로 그 자체로 평균이 됨 - 각 검색어의 검색 빈도는 상수임 (고정된 Input) - 따라서 검색어들을 어떤 형태의 BST로 구성하느냐에 따라 c가 달라져서 전체 평균 검색 시간이 달라지는 것! ex)
- 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
https://hi-guten-tag.tistory.com/73
어떤 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차원 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가 만들어진다.
C++에서 cin을 사용하여 입력을 받을 때, 기본적으로 공백 문자(스페이스, 탭, 개행)을 기준으로 데이터를 분리함
→ 띄어쓰기(스페이스)는 cin에서 입력을 구분하는 구분자로 작용함
예시
#include <iostream>
using namespace std;
int main() {
int a, b, c;
cout << "정수 a, b, c를 입력하세요: ";
cin >> a >> b >> c;
cout << "입력된 값: a=" << a << ", b=" << b << ", c=" << c << endl;
return 0;
}
"1 2 3"로 입력하면 cin은 이를 공백 문자를 기준으로 각 변수에 할당함
사례
#include <iostream>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
cout << "N: "<< N <<", M: " << M << endl;
char a;
cin>>a;
if (a=='*'){
int b;
cin>>b;
cout<<b<<endl;
}
return 0;
}
For a given nonlinear mappingΦ(𝑥), the input data spaceℝ𝑛can be mapped into the Feature space
Φ : ℝ𝑛 ↦ Feature space 𝑥 ↦ Φ(𝑥)
The feature map is an arbitrary map into thefeature space𝐻.
For example, if𝐻isfinite dimensional(say, of dimension𝑚), you can pick anorthonormal basisfor it,
and think ofeach component ofΦin that basisas afeature. This is what scalar features are.
Inner product space
orthonormal basis
In mathematics, particularly linear algebra, an orthonormal basis for an inner product space V with finite dimension is a basis for V whose vectors are orthonormal, that is, they are all unit vectors and orthogonal to each other.
For example, the standard basis(표준기저) for a Euclidean space R" is an orthonormal basis, where the relevant inner product is the dot product of vectors. The image(공역) of the standard basis under a rotation or reflection (or any orthogonal transformation) is also orthonormal(=standard basis를 가지고 rotation과 같은 orthogonal transformation을 하면 그 transformed vector들도 orthonormal이다), and every orthonormal basis for R" arises in this fashion.
*standard basis: 유클리드 공간에서 직교 좌표계의 축을 향하는 단위 벡터의 집합
Every vector a in three dimensions is a linear combination of the standard basis vectors i, j and k.
standard basis i, j, k or R3
* basis: 벡터 공간을 선형생성하는 선형독립인 벡터들이다. 달리 말해, 벡터 공간의 임의의 벡터에게 선형결합으로서 유일한 표현을 부여하는 벡터들
For a general inner product space V, an orthonormal basis can be used to define normalized orthogonal coordinates on V. Under these coordinates, the inner product becomes a dot product of vectors. (The inner product는 dot product의 일반화된 버전 toabstract vector spacesover afieldofscalars, being either the field ofreal numbers or the field ofcomplex numbers)
orthogonal (직교)
orthonormal
Two vectors are said to be orthogonalif their dot product is zero Orthogonal vectors areperpendicularto each other
