[SWEA] 이진탐색(tree 문제) (python)

SWEA Learning Club Tree 7차시 문제

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVJ-_6qfsDFAWg# 

SW Expert Academy

이진탐색 Tree 버전 문제

문제를 보고 정말 이진 탐색으로 구현하려하면 쉽지 않은 문제

트리의 N번과 N//2번에 저장된 값을 출력하는 문제

100% 내 생각으로 풀었는가?
→ X

중위 순회에 관하여 이해를 하고있는지를 묻는 문제였고, 중위 순회에 대한 개념 코드를 미리 알아두고 있으면 쉽게 풀 수는 문제

내가 푼 정답코드

def binary(a, b):
    global cnt
    if a <= b:
        binary(a*2, b) #재귀로 왼쪽 아래로 내려갈 수 없을때까지 탐색
        tree[a] = cnt  # tree[a]에 cnt 입력
        cnt += 1
        binary(a*2 + 1, b)

# 트리 탐색시 왼쪽아래는 인덱스*2 / 오른쪽은 인덱스*2+1
T = int(input())
for case in range(1, T+1):
    N = int(input())
    tree = [0] * (N + 1) # 1~N까지 넣을 트리 생성
    cnt = 1
    binary(1, N)
    print(f'#{case} {tree[1]} {tree[N//2]}')

트리 탐색시 왼쪽 아래는 인덱스*2, 오른쪽 아래는 인덱스*2 + 1 이란 점만 알면 재귀를 이용하여 해결 할 수 있는 문제였다. 중위 순회냐, 전위 순회냐, 후위 순회냐에 따라 binary 함수안에 있는 가운데 부분만 위아래로 바꿔주면 원하는 순서로 구할 수 있다.

---

느낀점

Tree에서 가장 중요한 부분중 하나인 순회의 개념에 대해서 배우기 좋은 문제였다. 다만 이걸 개념을 알고 있어도 어떻게 접근해야하지?라는 생각이 강했던 문제였던거 같은데, 인덱스*2와 인덱스*2+1로 왼쪽 오른쪽을 나눌 수 있다는 점을 알고 이를 활용만 한다면 재귀를 활용하여 풀 수는 있었겠지만, 아직 트리에 대한 개념과 구현 실력이 따라주지 않아서 그런지 어려움이 많았던거 같다..😥 트리 개념과 코드들을 여럿 봐봐야 알고리즘 풀이에 제대로 활용할 수 있겠다고 느꼈다.