자료구조 여름방학 1주차

 

트리

 

그래프의 특수한 형태로 노드와 엣지로 연결된다. 

순환 구조가 없고 1개의 루트노드가 존재한다. 

 

트리에서 임의의 두 노드를 이어주는 경로는 유일하다.

 

노드: 데이터의 인덱스와 값을 표현

엣지:노드사이의 연결

루트: 최상위 노드

리프노드:최하위에 존재하는 노드

자식노드: 두 노드 사이에서 하위노드에 해당하는 노드

 

tree 문제:

1) 그래프 풀이

   dfs, bfs 문제

2) tree만을 위한 문제

   이진트리, 세그먼트 트리,lca (최소 공통 조상)

      1차원 배열로 트리를 표현

      (자식으로 이동할 때는 index*2 or index*2+1 부모로 이동할 때는 index/2...)

 

[백준 11725]

 

인접리스트 자료구조 사용

일반적으로 dfs, bfs사용

dfs를 사용해 쉽게 해결 가능

 

깊이우선 탐색: 현재노드가 다음번 탐색한 노드의 부모 노드임.

 

깊이우선탐색을 해주면서 다음 미방문 노드로 갈때 부모노드는 현재노드임.

import sys

sys.setrecursionlimit(파이썬 코딩테스트 볼 때 사용해주기 )

 

• 방문 노드 저장 리스트
• 트리 인접 리스트 
• 정답 리스트

정의해주기

 

 dfs 함수를 일반적으로 작성하면서 정답리스트에 answer[i] (현재노드)=number(부모노드) 저장

 마지막에선 정답 배열을 활용해 부모노드를 출력해주면 정답 출력 가능

 

 

이진트리

이진트리: 자식노드의 차수가 2 이하로 구성된 트리

편향 이진트리: 한쪽으로 쳔향된 이진트리

포화이진트리: 단말노드가 모두 채워진 트리

완전이진트리: 마지막 레벨을 제외한 모든 레벨은 노드가 모두 채워져있고 마지막 레벨은 왼쪽부터 단말노드가 채워지는 트리

 

이진트리의 편리한 순차표현: 배열

 

부모노드 인덱스 i

자식노드 인덱스 i * 2, i * 2 + 1

인덱스의 계산으로 부모 자식 관계를 판별 가능하기 때문에 배열의 행태로 편리하게 관찰 가능

 

#계산을 위해 0번 인덱스는 비워둔다