재귀인데,값을 줄여나가는 방식
- 쿼드트리 문제 처럼. 값을 줄여나가는 방식인 경우, 범위도 함께 재귀의 인자로 보내자.
어떻게 풀까? 241030
- 문제를 보고, 생각해야 할 점이 , 이진트리로 만들어서 레벨 순회를 할 것인가??
아니면 굳이 위 생각처럼 해야하는가??? 에 대해서 생각해야 한다.
왜냐하면 반절씩 자르고, 또 반절의 인덱스의 value 출력만 하면 되기 때문이다.
-> 규칙성이 정해져 있다. 완전이진트리라는 규칙성!
공부해야 할 부분
1 이진탐색
2 트리
3 재귀
-> 이거를 알고 있는면 풀 수 있음.
풀이 전략
1) 가운데에서부터 뽑은 후, 3저장
2) s ~ mid , mid ~ e 의 가운데를 추출..
3) 재귀 동작하고 있음.
-
1) 트리 레벨(높이)에 대한 정보를 가지고 있어야 함.
: 레벨에 따라서 endl이 된 것을 확인할 수 있음. -
2) 입력 값을 어떻게 레벨에 맞춰서 넣을까에 대한 생각을 해야 함.
-
3) 중앙 부분에 대한 처리를 해야 하므로, start와 end값이
있어야 편하게 코드 작업 이 가능함.
🔥🔥🔥