표현가능한 이진 트리 (이진수 변환, 포화이진트리, 중위순회, 이분탐색)

2023. 4. 5. 12:18·Coding Test/programmers
728x90
 

세그먼트 트리, 인덱스 트리, 구간합

1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지

karla.tistory.com

 

 

  • 트리 중위순회
  • 노드갯수 len(n)
  • 트리높이 int(math.log(len(n), 2))
  • 포화이진트리 2ᴷ-1, 비어있으면 앞에 0추가
"""
이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며,
자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.
numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0

1 ≤ numbers의 길이 ≤ 10,000
1 ≤ numbers의 원소 ≤ 1015

"""
import math

# 이진검색
def search(n):
    length = len(n)
    mid = length // 2
    if length == 1 or '1' not in n or '0' not in n:
        return True
    if n[mid] == '0':
        return False
    return search(n[mid + 1:]) and search(n[:mid])


def solution(numbers):
    answer = []

    # 1. 이진수 변환
    bin_numbers = [bin(i)[2:] for i in numbers]

    for n in bin_numbers:
        # 트리높이 int(math.log(len(n), 2))
        tree_height = int(math.log(len(n), 2))
        # 포화이진트리 노드개수 2ᴷ-1
        digit = 2**(tree_height+1)-1
        
        # 이진트리에 빈공간 있으면 앞에 0추가
        n = "0"*(digit-len(n)) + n

        answer.append(1 if search(n) else 0)

    return answer

print(solution([58, 7, 42, 5, 63, 111, 95]))

 

 

 

 

728x90
저작자표시 (새창열림)
'Coding Test/programmers' 카테고리의 다른 글
  • 개인정보 수집 유효기간 (문자열, 구현)
  • 택배 배달과 수거하기 (그리디)
  • 이모티콘 할인행사 (완전 탐색, 조합)
  • 미로 탈출 명령어 (DFS, 백트래킹)
Karla Ko
Karla Ko
𝘾𝙤𝙣𝙩𝙞𝙣𝙪𝙤𝙪𝙨𝙡𝙮 𝙄𝙢𝙥𝙧𝙤𝙫𝙞𝙣𝙜, 𝘾𝙤𝙣𝙨𝙩𝙖𝙣𝙩𝙡𝙮 𝘿𝙚𝙫𝙚𝙡𝙤𝙥𝙞𝙣𝙜 𝙔𝙚𝙨!
    250x250
  • Karla Ko
    karlaLog
    Karla Ko
  • 전체
    오늘
    어제
    • Total (467)
      • Spring (19)
      • JPA (4)
      • Cloud & Architecture (15)
        • Kubernetes (5)
        • Docker (3)
        • MSA (2)
        • GCP (1)
        • AWS (4)
      • Devops (1)
      • Message Queue (4)
        • Kafka (2)
        • RabbitMQ (2)
      • Git (4)
      • DB (4)
      • Java (9)
      • Python (4)
      • CS (11)
        • OS (8)
        • Network (2)
        • Algorithm (1)
      • Coding Test (392)
        • programmers (156)
        • Graph (43)
        • DP (37)
        • Search (31)
        • Tree (13)
        • Data Structure (26)
        • Combination (12)
        • Implement (18)
        • Geedy (23)
        • Sort (7)
        • Math (21)
        • geometry (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    트리
    알고리즘
    힙
    최단거리
    월간코드챌린지
    LIS
    최소신장트리
    최대공약수
    구현
    동적계획법
    DP
    다익스트라
    조합
    큐
    스택
    프로그래머스
    DFS
    플로이드워셜
    BFS
    덱
    재귀
    정렬
    이분탐색
    Algorithm
    그리디
    파이썬
    백준
    구간합
    자료구조
    그래프
  • hELLO· Designed By정상우.v4.10.3
Karla Ko
표현가능한 이진 트리 (이진수 변환, 포화이진트리, 중위순회, 이분탐색)
상단으로

티스토리툴바