C로 배우는 알고리즘 - 복습 겸 요약 4

3. 자료구조 - 스택, 큐, 트리

1. 스택

알다시피 선입후출형의 자료구조이다. 이것을 구현하는 걸 배열이나 연결 리스트로 할 수 있는데....

혼연C는 배열이 좋다고 하고 이 교재는 리스트가 좋다고 한다!!!

근데 난 혼연C가 옳다고 생각. 일단 구현은 쉬우니까. push()하고 pop()만 만들면 되는..

둘 다 장단점은 다 있으니까 여기서 스톱한다.

예제는 계산기. 전위식을 후위식으로 바꿔 스택에 저장한 후 계산하는 방식이다.

지금해도 만만찮지만, 예전에 한 번 만들어 본 적이 있다. 아.. 만들기 귀찮아..

근데 자료구조 풀다가 스택은 만들어 버렸다.. 동적할당을 지원하고 배열로 구현했다. 보라고 만든 건 아니다. 그냥 기념 -.-

아, 여기에 하나 주석. 왜 혼연C하고 C로.. 교재는 둘 다 스택 특이값을 -1로 잡았을까? 0으로 잡으면 안 되었을까?

나는 0으로 구현했다. 그러면 top하고 스택의 size비교가 쉽기 때문.

3-3.my_stack.cpp

2. 큐

큐는 스택과 달리 선입선출형이다. 이것도 역시 배열과 연결리스트로 구현할 수 있는데,  혼연C는 둘 다로 구현했다.

근데 연결리스트로 구현한 부분 중 Insert에서 큐가 커지면 어쩌려고 그러는지...

혹시 자료구조 개념만 중요한 거고 구현은 그닥 중요한 게 아닌 걸까?

설령 그렇다고 해도 구현을 하다보면 개념에 대해 더 이해가 깊어지는 경우가 있어 구현이 필요 없는 건 아니지만.. (연결리스트만 해도.. ㅡㅡ)

근데 두 교재 모두 이중연결 리스트로 구현을 했다. C로 배우는 알고리즘은 단순연결 리스트로 하면 put동작이 부자연 스럽다고 하는데, 그럼 적어도 혼연C의 구현에서는 단순 연결 리스트를 써도 되는게 아닌가 싶다.

실제로 prev가 쓰이진 않으니까... 그리고 head, tail을 유지하면서 단순연결리스트로 큐를 만드는 것도 그렇게 어렵진 않을 듯 싶다.

둘 다 예제는 없다. 넘어간다.

(사실 혼연C에서 시뮬레이션 예제가 있지만... 굳이 그것까지야;;)

데크는 STL에서 본 적이 있다. 좀 어이 없던 것은 큐가 데크의 상속 클래스 였던 것... 같은데. 나름 이유가 있겠지.

이것도 구현해보았다. 트리 층별순회에 써먹으려고 템플릿으로 만들어보려 했으나 처참하게 실패.

못 써먹었다. C++ 다 까먹은 느낌. 고등학교 교육과정 정말 필요한 걸까 ㄱ-?

3-4.my_queue.cpp

3. 트리

이제부터 생소해지기 시작한다. 무슨 책 먼저 볼까... (아니, 지금 어느 교재 독후감 쓰는 건데 ㅡㅡ;)

트리의 용어정의

트리: 어떠한 조건을 만족하는 노드Node와 링크Link의 집합

노드는 버텍스Vertex라고도 하며 링크는 에지Edge라고도 함.

노드는 정보를 담고 있고, 링크는 노드간의 연결을 나타냄.

경로: 트리 내에서 링크에 의해 연결된 일련의 노드의 집합. 뭐... 디렉토리 구조도 트리니까, 쉽다.

 graph와 차이점. 한 노드에서 다른 노드에 이르기까지의 경로는 단 하나밖에 없다.

부모, 자식, 조부모, 형제노드라는 표현도 있다. 족보 생각하면 쉽다.

내부노드 = 비종료노드, 외부노드 = 종료노드 = 잎

내부·외부 경로는 무슨말인지 잘 모르겠다. 나중에.

아... 오타 발견. 233p에 마지막에서 4번째 줄은 '꽉 차있는 이진 나무'가 아니라 '완전한 이진 나무'인 것같다.

다중 트리Multiway Tree: 무조건 어떤 정수 이하개수로 자식을 가지는 트리. 이진트리도 여기 속한다.

완전 이진트리Complete binary tree: 마지막 레벨 빼고 꽉 차있는 이진트리.. 라고 C로 배우는 알고리즘엔 적혀있는데!!!

혼연C를 보니, 순서대로 번호를 매겨서 빈 번호가 없으면 그게 완전이진트리다.

포화 이진트리Full binary tree: 모든 레벨이 차있다.

트리의 성질

1. 트리구조의 임의의 두 노드는 최소공통선조Least common ancestor를 갖는다.

   그 두 노드를 잇는 경로는 그 최소공통선조를 거치는 경로 하나밖에 없다.

2. N개의 노드를 갖는 트리는 N-1개의 링크를 갖는다. 노드 하나당 부모와의 링크 하나를 가지고 있고 맨 위의 root가 없으니까 N-1이 된다.

3. 이진트리의 높이(=최대 레벨)로 포함 가능한 노드 수를 나타내는 공식에서 반대의 경우도 가능하다는 것만 알아두자. 일단 답은 log₂N + 1

트리의 순회traverse

전위 순회PreOrder, 중위 순회InOrder, 후위 순회PostOrder가 있는데, 각각은 루트를 방문하는 순서로 나눈다. 모두 재귀호출로 구현가능하다.

다만 층별 순회LevelOrder는 BFS와 유사해 큐를 이용한다.

트리는 구현이 너무 다양하다고 한다. 예제는 C로.. 책에 계산기가 나왔는데, 내·외부 노드 구분이 정말로 쓰일 줄은 몰랐다...

게다가 후위식도 자유자재로 다루는 점에선 스택보다 깔끔한 것 같기도 하다.

이 트리의 순회는 다음에 나오는 재귀호출에서 예제로 많이 나오더라.