자료구조/알고리즘 - 이진트리(1)
트리란?
뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조이다.
큐(Queue)와 스택(Stack)은 자료구조에서 선형 구조라고 한다.
선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미합니다.
비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어있습니다.
선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다.
트리구조는 위 그림에서 보는 것 처럼 폴더 구조와 같습니다.
이진 트리
이진 트리는 최대 두 개의 자식을 가집니다. ( 0, 1, 2 )
완전 이진 트리
완전 이진트리는 마지막 레벨을 제외 하고 모든 레벨이 완전히 채워져 있습니다.
마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 합니다.
완전 이진 트리는 배열을 사용해 효율적으로 표현 가능합니다.
o Level 0
o o Level 1
o o Level 2 # -> 이진 트리 O 완전 이진 트리 X
o Level 0
o o Level 1
o o o Level 2 # -> 이진 트리 O 완전 이진 트리 O완전 이진 트리 배열을 사용해 표현
8 Level 0 -> [8] 첫번째 레벨의 8을 넣고,
6 3 Level 1 -> [8, 6, 3] 다음 레벨인 6, 3을 넣고
4 2 5 Level 2 -> [8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 넣으면 됩니다!완전이진트리 이고, 레벨이 k 일 때, 노드의 개수 Level k -> 2^k 개
완전이진트리 이고, 높이가 h 일 때, 노드의 개수 1 + 2^1 + 2^2 + 2^3 + 2^4 ..... 2^h -> 2^(h+1) - 1
결론 시간복잡도 O(logN)
오늘 푼 문제
https://geonoo.tistory.com/102
[파이썬] 프로그래머스 - 예상 대진표
문제 [문제 설명] △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔
geonoo.tistory.com
https://geonoo.tistory.com/103
파이썬 알고리즘 인터뷰 - 이진 트리의 직경
문제 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. 입력 TreeNode [1,2,3,4,5] 출력 3 먼저 내 코드에서 테스트 해보려면 배열을 리스트로 만드는 과정이 필요했다. class TreeNode: def __init__
geonoo.tistory.com
https://geonoo.tistory.com/104
파이썬 알고리즘 인터뷰 - 가장 긴 동일 값의 경로
문제 동일한 값을 지닌 가장 긴 경로를 찾아라. 입력 Input: root = [5,4,5,1,1,5] 출력 Output: 2 처음에 지나온 노드의 개수 인줄 알고 엥? 왜 2개이지 한참 고민했다. 출력을 다시 생각해보니 간선의 개수
geonoo.tistory.com
https://geonoo.tistory.com/105
파이썬 알고리즘 인터뷰 - 이진 트리 반전
문제 이진 트리가 주어지면 root트리를 반전 하고 루트 를 반환합니다. 입력 root = [4,2,7,1,3,6,9] 출력 [4,7,2,9,6,3,1] 작성한 코드 # Definition for a binary tree node. class TreeNode: def __init__(..
geonoo.tistory.com
회고
사실 예제까지 포함하면 5문제를 풀어봤다. 처음 2~3문제는 접근조차 못하고 있었는데 계속 이해하려고 하고 다음 문제 다음 문제 풀수록 트리가 어떤 구조인지 머릿속에 그려지기 시작했다.
마지막에 내가 스스로 트리의 길이를 구하는 함수나 트리를 다시 리스트로 변환하는 함수를 만들고 그 문제를 풀었을 때는 기분이 정말 좋았다.
알고리즘 첫주차때는 이런식으로 공부하지는 않았다. 2주차되서야 이런식으로 공부하는 걸 적용했는데 확실히 이 방법이 나한태 더 기억에 잘 남을 것 같다.
앞으로도 이런 방식으로 공부해봐야겠다.