인프런 커뮤니티 질문&답변
작성한 질문수
트리 구현 방식에 대한 질문
해결된 질문
작성
·
171
·
수정됨
1
안녕하세요.
트리를 클래스로 구현하는 것과 배열로 구현하는 것에 차이가 있나요? 이제 막 코딩테스트를 처음 공부하고 있는데 구현 방법에 따라서 활용도가 어떻게 다른지 궁금합니다.
제가 짧게 혼자 공부햇을 때에는 배열로 트리를 만들고 인덱스를 기준으로 부모와 자식을 찾아가는 방식으로 공부했는데요.
강사님 강의를 들어보니 클래스로 구현하는게 훨씬 직관적으로 보여서요.
이런 구현 방식들이 각각 어떻게 장단점이 있는지 궁금합니다.
제가 정리하기로는 배열은 완전 이진 트리만 구현이 가능하고 부모와 자식을 찾아가기에 용이하다... 클래스 형식으로 트리를 구현하면 루트부터 시작할 때 용이하다...라고 정리를 햇는데 잘 이해하고 있는 건가요?
배열로 트리를 구현하게 되면 bfs랑 dfs 탐색을 할 때에도 인덱스를 타고 타고 넘어가도록 코드를 작성하면 되나요?
그리고 용어들이 조금 헷갈리는데 연결리스트로 트리를 구현하는 방식이 클래스로 구현하는 것과 같은 의미인가요..?
답변 1
0
안녕하세요 우주사막님.
열심히 하시는군요!! 질문들이 좋네요.
트리를 클래스로 구현하는 것과 배열로 구현하는 것에 차이가 있나요?
트리를 Node 클래스를 이용해서(linked list의 개념을 활용) 구현할 수 있고, 배열을 이용해서 구현할 수 있고 (보통 완전이진트리를 구현할 때), 해시테이블을 이용해서 구현할 수 도 있습니다.
상황에 따라서 편하게 구현할 수 있는 걸 선택하시면 될 것 같아요. 완전이진트리를 구현할 땐 배열을 이용하는게 편할 것 같고, 커스터마이징을 많이 해야되는 상황이라면 직접 Node클래스를 구현하는게 좋을 것 같고, 빠르게 구현해서 간단히 사용할거면 해시테이블을 이용해서 구현해도 될 것 같아요.
배열로 트리를 구현하게 되면 bfs랑 dfs 탐색을 할 때에도 인덱스를 타고 타고 넘어가도록 코드를 작성하면 되나요?
구현방식에 따라서 코드를 다르게 작성해야될 것 같아요. 하지만 기본적인 bfs, dfs의 알고리즘은 동일하기 때문에 조금 고민해보시면 충분히 구현할 수 있을거에요!
혹시 더 궁금한점이 있으시면 질문주세요~