260904(금)
허준이 교수 의견
때로는 제가 다른 사람들의 생각이 잠시 머물다 가는 그릇 같다는 생각을 한다. 생각이 이 그릇에서 저 그릇으로 옮겨 다니며 점차 풍성해지는 것이 신기하다. 마음이 맑은 날에는 제가 거대한 구조의 아주 작은 일부라는 것이 잘 느껴진다. 공동 연구가 훨씬 더 멀리 갈 수 있고 훨씬 더 깊이 갈 수 있다.
나는 문제가 안 풀리면 포기한다. 일종의 직관인데 ‘내가 이걸 조금 노력하면 몇 달 안에 풀겠다, 아니다’처럼 판단이 필요하다. 잘 포기하는 것도 굉장히 중요한 재능이라고 생각한다. 어떤 종류의 문제들은 개인이 이해할 준비가 안 됐거나 인류가 이해할 준비가 안 된 것일 수도 있다. 그걸 붙잡고 있는 것은 생산적이지 않다. 문제를 해결하고 풀어내는 것은 사실 우연이라고 생각한다. 지난주에는 전혀 이해하지 못하고 해법을 상상할 수 없었는데 오늘 갑자기 생각이 나는 경우가 있다
수학의 매력은 자유로움이다. 수학엔 논리가 맞아야 한다는 규칙이 있다. 그런데 그 규칙의 엄격함 때문에 다른 면에서 자유롭다. 어떤 대상을 연구할 것인지, 어떻게 이해하고 풀어야 하는지 정해진 규칙이 하나도 없다. 수학은 자유로움을 학습하는 일이다. 그래서 어렸을 땐 얽매이지 않고 많은 생각을 자유롭게 하는 훈련을 하면 좋을 것 같다
트리 탐색이란? 모든 노드를 체계적인 순서대로 순회하는 과정이다.
트리는 비선형적이어서, 탐색 방법은 여러 가지다.
각각의 방법은 어떤 문제를 어떻게 해결하는가?
depth: (Stack/Recursive) Search all possible paths
breadth: (Queue/Iterative) Search the shortest path, Connectivity Check, AI & Search Problems
ㅇ너비 우선 탐색 (BFS): Breadth First, layer by layer
ㅇ깊이 우선 탐색 (DFS): Depth First, Backtracking
대표 3가지
1. 선순서(Preorder): Top-Down (복제, 저장/직렬화)
2. 후순서(Postorder): Bottom-Up (삭제, 폴더 크기 계산)
3. 중순서(Inorder): Left-to-Right (BST 이진 탐색 트리의 데이터를 정렬 및 추출)
- 선순서 (Top-Down)
- 문제: 파일은 1차원, 트리는 2차원
- 하드 드라이브에 있는 파일은 선형적인 바이트 시퀀스다.
- 트리를 파일로 직렬화하려면, 2차원 분기 구조를 1차원 데이터로 만들어야 한다.
일반적으로, 자식은 부모의 주소를 저장하지 않는다 (예외: red-black tree 등등)
그래서 파일 로딩은 선순서가 타당하다.
- 후순서 (Bottom-Up) "폴더의 크기를 계산할 때, 폴더 하위의 모든 파일의 크기를 합산하는 게 먼저다"
- 중순서 (Left-to-Right)
linked-list 에서 head 가 포인터를 잃어버리면, 메모리 누수가 발생할 수 있는 것처럼,
tree 에서 root 를 잃어버리면, 메모리 누수가 발생할 수 있는 건가봐?
->
그렇다. 프로그램은 유일한 진입점을 잃어버린 상태다.
tree 를 안전하게 free() 하고 그 메모리를 OS에 반환하려면, tree 를 순회하며 모든 노드에 대해 free() 를 호출해야 한다.
만약 root 변수가, 덮어쓰이거나, NULL 로 설정되거나, free() 를 호출하지 않고 범위 밖으로 빠져나가면, 그 하위 노드들에 접근할 수 없다.
그 노드들은 프로그램이 실행되는 동안 RAM 에서 고립된다. 더이상 사용할 수도 없고, 주소를 잃어버려서 삭제할 수도 없다.
최신 OS 는 프로그램이 최종적으로 종료되고 셧다운될 때 프로세스가 할당한 모든 메모리를 자동으로 회수하지만,
오래 실행되는 서버 APP 의 경우, 사용 가능한 RAM 을 소모하여 시스템이 다운될 여지가 있다.
그래서 malloc 에 대응해서 결국에는 free 해야 하며, 항상 진입점 (head 또는 root) 을 보호해야 한다.
지금 말하는 tree는
main.rs 진입, main() 진입이랑 연관 있어?
->
맞다.
