[Programmers] 표현 가능한 이진트리 - Python

2023. 10. 23. 23:43·Algorithm (PS)
728x90

이진수로 변환하고 -> 이진수를 표현하는 포화 이진 트리를 만들고 -> 포화 이진 트리를 탐색 하는 총 3가지의 로직을 구현해주면 되는 문제이다. 

트리 란 비선형 자료구조들 중에서 자료 간 (= 노드) 계층 관계를 가진 자료구조이다. 

포화 이진 트리란 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 노드로 차있는 트리이다. 또한 각 노드들이 2개의 자식 노드들을 가지며, 홀수 개의 자식 노드를 가질 수 없다. 즉, 자식 노드가 0개이거나 2개이다. 

# 포화 이진 트리를 탐색
def check_tree(binary):
    root = len(binary) // 2  # mid
    if root == 0:  # leaf node
        return True
    if binary[root] == '0':
        if '1' not in binary:
            return True
        return False
    return check_tree(binary[:root]) and check_tree(binary[root + 1:])


def make_binary(n):
    reversed_binary = []  # 1. 이진수 저장 빈 문자열
    while n != 1:
        reversed_binary.append(str(n % 2))
        n //= 2
    reversed_binary.append("1")
    binary = "".join(reversed_binary[::-1])  # 나머지를 뒤집어서 이진수 만들기
    # 2. 포화이진트리 만들기 (2**0 + 2**1 + 2**2 + 2**3 ..)
    max_binary_tree = 1
    while max_binary_tree < len(binary):
        max_binary_tree = (max_binary_tree + 1) * 2 - 1
    binary = "0" * (max_binary_tree - len(binary)) + binary  # 부족한만큼 0 추가하기
    return binary


def solution(numbers):
    answer = []  # result

    for n in numbers:
        binary = make_binary(n)
        if check_tree(binary):  # True
            answer.append(1)
        else:
            answer.append(0)

    return answer

# 올바른 트리의 경우 : 부모 0 - 자식 0 는 가능
# 부모 0 - 자식 1 는 틀림
# 부모 1 - 자식 0 가능
# 부모 1 - 자식 1 가능

 

 

728x90

'Algorithm (PS)' 카테고리의 다른 글

[LeetCode] 13. Roman to Integer - Python  (0) 2023.11.12
[백준] 1261번: 알고스팟 (Python) - 0-1 BFS 탐색  (0) 2023.10.29
[프로그래머스] 파괴되지 않은 건물 (누적합|Python)  (1) 2023.10.15
[백준] 9466번: 텀 프로젝트 (DFS|Python) - 그래프에서 cycle을 찾기  (0) 2023.10.15
[백준] 10986번: 나머지 합 (Python) - 메모리 초과와 누적합  (0) 2023.09.29
'Algorithm (PS)' 카테고리의 다른 글
  • [LeetCode] 13. Roman to Integer - Python
  • [백준] 1261번: 알고스팟 (Python) - 0-1 BFS 탐색
  • [프로그래머스] 파괴되지 않은 건물 (누적합|Python)
  • [백준] 9466번: 텀 프로젝트 (DFS|Python) - 그래프에서 cycle을 찾기
minjiwoo
minjiwoo
Data Engineering과 Cloud Native 기술에 대해 Dive Deep 하는 플랫폼 엔지니어가 되는 것을 목표로 하고 있습니다. 경험과 공부한 내용을 기록하며 지속가능한 엔지니어가 되는 것이 꿈입니다.
minjiwoo
minji's engineering note
minjiwoo
전체
오늘
어제
  • 분류 전체보기 (611)
    • Data Engineering (42)
      • Apache Spark (11)
      • Databricks & Delta Lake (9)
      • Airflow (3)
      • SQL (6)
      • Trouble Shooting (2)
      • Hadoop (2)
      • MLOps (1)
    • Cloud Engineering (104)
      • AWS (23)
      • Linux 🐧 (29)
      • Docker 🐳 (21)
      • Kubernetes ⚙️ (20)
      • Ansible (10)
    • Computer Science (87)
      • 네트워크 (9)
      • 운영체제 (25)
      • 정보처리기사 (48)
      • CS 기술 면접 스터디 (3)
    • Programming Languages (26)
      • Python (16)
      • C와 C++ (10)
    • Backend (5)
      • Django (2)
    • 프로젝트 (2)
      • 테크포임팩트 (2)
    • iOS (11)
      • 레이블러리 (2)
    • Algorithm (PS) (275)
      • LeetCode (6)
    • 개발일기 (29)
      • 내돈내산 후기🎮 (3)
      • 개발자 취준생 (4)
      • Today I Learned (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • Hi there

인기 글

태그

  • docker
  • 코딩테스트
  • 운영체제
  • 파이썬
  • 알고리즘
  • 스파크
  • 백트래킹
  • 빅데이터
  • 데이터브릭스
  • BFS
  • 클라우드
  • dp
  • Databricks
  • linux
  • python
  • dfs
  • 쿠버네티스
  • 데이터엔지니어링
  • Kubernetes
  • ansible
  • AWS
  • Swift
  • SPARK
  • 카카오코딩테스트
  • Leetcode
  • 백준
  • 데이터엔지니어
  • 프로그래머스
  • EC2
  • 리눅스

최근 댓글

최근 글

hELLO· Designed By정상우.v4.5.2
minjiwoo
[Programmers] 표현 가능한 이진트리 - Python
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.