13강은 데이터 구조 중 트리에 관한 강의이다.
트리 구조는 쉽다. root가 있고 자식이 있고 각각의 step을 노드로 부른다.
하지만 트리구조는 list 나 dictionary 처럼 key 나 index 로 search 할 수 없다.
그래서 트리 search를 위한 두가지 알고리즘이 존재한다. ( 강의 에서 바이너리 트리만 다뤘으므로 이 글에서의 트리는 기본적 바이너리 트리이다.-자식이 두개인 트리)
- depth-first
depth-first 알고리즘은 트리를 탐색할 때 왼쪽 자식부터 탐색하는것이다. 왼쪽 탐색을 마치면 부모의 오른쪽 자식을 탐색한다. - breadth-first
breadth-first 알고리즘은 레벨 별로 탐색하는 것이다. root 부터 자식, 자식, 자식 순으로 탐색한다.
특별히 두가지 알고리즘의 장단점은 없다.(depth-first 알고리즘이 복잡한 연산에서 더 빠른것 처럼 이야기하던데…)
그리고 Decision Tree가 나오는데 주어진 조건에 대해 가능한 경우의 수를 트리 구조로 표현한 것 이라고 이해하면 될 것 같다.
Decision Tree 를 만든 후에는 주어진 문제를 해결하기 위한 다양한 방법을 적용할 수 있었다.
주어진 문제는 knapsack problem 인데 무게와 가치를 고려해서 가방에 최대한으로 담을 수 있는 아이템을 찾는? 그런 문제였다.
강의가 마무리 된건 아니지만 강의 후반부에서 느끼는 건 이번 강의를 통해서 문제를 해결하는데 다양한 관점으로 생각할 수 있게 된점이 잘된점인 것 같다.
Search 를 할때 그 데이터 구조가 list 인지 tree 인지 를 고려해서 binary search 인지 merged search 인지 등 복합도를 계산해서 최적의 알고리즘을 찾거나 tree경우 decision tree 를 만들어서 문제를 해결하는 방법을 찾는 등 좋은 강의인것 같다.
알고리즘을 공부하는데 있어서 가장 큰 벽은 수학이고 두번째는 제귀적으로 생각하는 연습이 부족한 것 같다. solution 이 나와 있어도 제귀적으로 풀었다면 그것을 이해하는데 꽤 시간이 걸린다.
제귀적으로 생각하는 연습을 하는게 큰 도움이 될 것 같다.
이 강의가 끝나면 알고리즘 책 같은걸 사서 공부해야하나?