개발이나하자../algorithm (4) 썸네일형 리스트형 [Data Structure] 이진트리 순회 (깊이우선탐색) : 전위순회, 중위순회, 후위순회 | Tree traversal : preorder, inorder, postorder Tree는 부모노드와 왼쪽 자식노드, 오른쪽 자식도드가 있는 구조다. 이렇게 하나가 기본 단위다. 이진트리를 순회하는 방법은 3가지가 있다. 전위순회(pre-order traversal), 중위순회(in-order traversal) 그리고 후위순회(post-order traversal) 아래 이진트리로 연습을 해보겠다. 노드는 1 ~ 7까지다. Root node는 1 전위순회를 먼저 알아보겠다. 어떻게 1 2 4 5 3 6 7 이 나오는 것일까? 그 과정을 정리해봤다. 슬라이드를 천천히 보면서 설명을 읽어본다면 이해할 수 있을것이다. 트리는 stack과 재귀를 이용해서 탐색한다는것을 이해했다. 중위순회(in-order traversal) 후위순회(post-order traversal) 원리만 안다면 쉬.. [Data Structure] Heap : Max Heap, Min Heap | 최대힙, 최소힙이란 Heap 은 만드는데 worst case로 O(n log n) 까지도 걸린다. 하지만 제일 큰값과 작은 값을 찾을 때는 O(1)이다. 그리고 Heap sort는 inline sort를 (추가 배열 불필요) 할 수 있어서 아주 강력한 소팅 알고리즘이다. Heap의 종류는 두가지가 있다 Max Heap과 Min Heap Max Heap의 조건은 다음과 같다. - 9는 root node이다. - 8과 7은 parent node인 9보다 작다 - 2와 3은 parent node인 8보다 작다 - 5와 6을 parent node인 7보다 작다. Min heap 은 Max와 반대다. 자식이 부모보다 작아야함 [algorithm] 파이썬 후위표기식 연산 | 스택 후위표기식 연산 | how to calculate postfix expression using stack https://paigeblog.tistory.com/29 [algorithm] 후위표기식 | postfix expression | 중위표기식에서 후위표기식으로 변환하기 | infix to postfix e 우리가 흔히 아는 표현식은 중위 표현식이라고 한다. 3+5와 같이 연산자가 피연산자 사이에 있으면 중위 표현식이라고 한다. 중위 표현식을 후위 표기법으로 바꾸는 알고리즘을 공부해 보겠다. paigeblog.tistory.com 중위 표기식에서 후위표기식으로 변환하는 방법을 위 포스팅으로 작성했다. 그러면 후위표기식은 어떻게 연산을 할까..? 352+*9- 가 주어졌을때 연산하는 방법을 알아보겠다. 원리를 알면 정말 쉽고 clever하다. 개발자들 정말 대단해 ~~!! 파이썬 코드로 짜보았다. 알고나면.. [algorithm] 후위표기식 | postfix expression | 중위표기식에서 후위표기식으로 변환하기 | infix to postfix expression using python 우리가 흔히 아는 표현식은 중위 표현식이라고 한다. 3+5와 같이 연산자가 피연산자 사이에 있으면 중위 표현식이라고 한다. 중위 표현식을 후위 표기법으로 바꾸는 알고리즘을 공부해 보겠다. 처음에는 뭐지? 했는데 보다 보니깐 이해했다. 이런 거 어떻게 생각해 냈는지 아무리 생각해도 신기하다. Rule이 있음 1. 피연산자는 무조건 res로 이동 2. 연산자와 괄호 ()는 stack으로 이동하는데 조건이 있다 2-1. * 와 / 는 +와 - 보다 우선순위가 높다 2-2 )가 나오면 ( 후에 들어간 연산자들을 stack에서 pop 하고 res로 옮긴다. ( 와 )는 res로 옮기지 않는다. 3. 피연산자를 다 옮겼다면 남아있는 연산자들을 res로 옮긴다. 슬라이드를 넘기면서 보면 이해하기 쉬울 것이다. cod.. 이전 1 다음
