인공지능 교육 2일차

1일차는 쓰는걸 깜빡했다..;;

뭔가 쉬운 테스트들도 배운 queue나 linked list, 이진트리 등등으로 풀어보려고 노력하다 보니

오늘도 늦게 끝났다.. 결국 2문제는 배운걸로 완전 해결을 못해서 시간 있을때 다시 도전해보는 걸로

-12.02: 큰수 만들기 오류 수정 [0, 0, 0] != '000', [0, 0, 0] = '0'

 

linked list 맨앞 노드 지울때 tail도 신경쓰기
사칙연산할 때 숫자가 2자리가 넘어가는 경우도 신경쓰기

이진트리 탐색 중위(좌 중 우) 전위(중 좌 우) 후위(좌 우 중)

힙 - 불규칙적 원소들의 Max, Min 할때 좋음 ex)우선순위 큐, 힙 정렬

 

class Node:
 
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None
 
    def insert(self, item):
        if self.data > item:
            if self.left:
                self.left.insert(item)
            else:
                self.left = Node(item)
        else:
            if self.right:
                self.right.insert(item)
            else:
                self.right = Node(item)
 
    def min_pop(self, parent):
        if self.left:
            return self.left.min_pop(self)
        else:
            if self.right:
                parent.left = self.right
            else:
                parent.left = None
            return self.data
 
 
class binary_tree:
 
    def __init__(self):
        self.root = None
 
    def insert(self, item):
        if self.root:
            self.root.insert(item)
        else:
            self.root = Node(item)
 
    def min_pop(self):
        if self.root.left:
            return self.root.left.min_pop(self.root)
        elif self.root.right:
            data = self.root.data
            self.root = self.root.right
            return data
        else:
            data = self.root.data
            self.root = None
            return data
 
    def is_Empty(self):
        return self.root is None
 
 
def solution(d, budget):
    answer = 0
 
    bin = binary_tree()
 
    for i in d:
        bin.insert(i)
 
    sum = 0
    while sum < budget and not bin.is_Empty():
        sum += bin.min_pop()
        answer += 1
 
    return answer - 1 if sum > budget else answer

리스트를 작은 숫자 부터 뽑아오는 이진 트리

 

class Node:
    def __init__(self, data, speed):
        self.data = data
        self.speed = speed
 
class queue:
    def __init__(self):
        self.head = -1
        self.tail = -1
        self.data = []
        self.nodeCount = 0
 
    def enqueue(self, data, speed):
        self.data.append(Node(data, speed))
        self.tail += 1
        self.nodeCount += 1
 
    def dequeue(self):
        self.head += 1
        self.nodeCount -= 1
        return self.data[self.head]
 
    def day(self): #하루 경과 후 진행률 상승
        for i in range(1, self.nodeCount + 1):
            self.data[self.head + i].data += self.data[self.head + i].speed
 
    def peek_done(self): #head의 진행도가 100이 넘었는지
        return self.data[self.head + 1].data < 100
 
    def is_Empty(self):
        return self.nodeCount == 0
 
def solution(progresses, speeds):
    answer = []
    jobs = queue()
 
    for i in range(0, len(progresses)):
        jobs.enqueue(progresses[i], speeds[i])
 
    while not jobs.is_Empty():
        cnt = 0
        while jobs.peek_done():
            jobs.day()
 
        while not jobs.peek_done():
            jobs.dequeue()
            cnt +=1
            if jobs.is_Empty():
                break
 
        answer.append(cnt)
 
    return answer

queue를 이용한 진행도 관리

 

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
    #'num1num2'와 'num2num1'을 비교하여 작은 경우 왼쪽 크면 오른쪽으로 저장
    def insert(self, data):
        if str(self.data) + str(data) >  str(data) + str(self.data):
            if self.left:
                self.left.insert(data)
            else:
                self.left = Node(data)
        else:
            if self.right:
                self.right.insert(data)
            else:
                self.right = Node(data)
 
    #가장 오른쪽 노드 부터 뽑아냄
    def pop_max(self, parent):
        if self.right:
            return self.right.pop_max(self)
        else:
            data = self.data
 
            if self.left:
                parent.right = self.left
            else:
                parent.right = None
 
            return data
 
class Binary_tree:
    def __init__(self):
        self.root = None
 
    def insert(self, data):
        if self.root:
            self.root.insert(data)
        else:
            self.root = Node(data)
 
    def pop_max(self):
        if self.root.right:
            return self.root.pop_max(self.root)
        else:
            data = self.root.data
 
            if self.root.left:
                self.root = self.root.left
            else:
                self.root = None
 
            return data
 
    def is_Empty(self):
        return self.root == None
 
def solution(numbers):
    answer = ''
    bin = Binary_tree()
    
    #이진 트리에 데이터 입력
    for i in numbers:
        bin.insert(i)
 
    #이진 트리에 가장 오른쪽부터 전부 뽑아 answer에 더하기
    while not bin.is_Empty():
        answer += str(bin.pop_max())
        if answer == '00':
            answer = '0'
 
    return answer

주어진 리스트에서 나올 수 있는 가장 큰 숫자 조합