23.02.15 Day13

오윤범·2023년 2월 15일
CodingTestDataStrucurealgorithmpython
0

부경대학교 iot개발자 교육과정

목록 보기
13/74

알고리즘/자료구조

  • 스택 외부모듈 사용(pythonds)

!pip install pythonds

from pythonds.basic.stack import Stack

st = Stack()
print(dir(st))

st.push('사나')
st.push('쯔위')
st.push('지효')
st.items
print(st.peek())#latest 자료
print(st.size())
print(st.pop())
print(st.size())
print(st.isEmpty())
------------------출력------------------
------------------출력------------------
지효
3
지효
2
False

  • 큐 외부모듈 사용(pythonds)

!pip install pythonds

from pythonds.basic.queue import Queue

qu=Queue()
qu.enqueue('화사')
qu.enqueue('문별')
qu.enqueue('사나')
qu.enqueue('솔라')

print(qu.items)

print(qu.dequeue())
print(qu.items)
------------------출력------------------
------------------출력------------------
['솔라', '사나', '문별', '화사']

화사
['솔라', '사나', '문별']

  • Queue

queue = [None for _ in range(5)]
front,rear=-1,-1

rear+=1
queue[rear]='화사'
rear+=1
queue[rear]='솔라'
rear+=1
queue[rear]='문별'

print('----Queue----')
for i in range(len(queue)):
    print(queue[i],end=' ')

front+=1
data=queue[front]
queue[front]=None
print(f'deQueue -> {data}')

print('----Queue----')
for i in range(len(queue)):
    print(queue[i],end=' ')

front+=1
data=queue[front]
queue[front]=None
print(f'deQueue -> {data}')

front+=1
data=queue[front]
queue[front]=None
print(f'deQueue -> {data}')

print('----Queue----')
for i in range(len(queue)):
    print(queue[i],end=' ')
------------------출력------------------
------------------출력------------------
----Queue----
화사 솔라 문별 None None 
deQueue -> 화사
----Queue----
None 솔라 문별 None None 
deQueue -> 솔라
deQueue -> 문별
----Queue----
None None None None None

  • Queue 전체 구현

# Queue 구현
# 전역 변수
SIZE=0
queue=[]
front,rear=-1,-1
# Queue 꽉 찼는지 확인
def isQueueFull():
    if (rear==SIZE-1):
        return True
    else:
        return False
# Queue 비어있는지 확인
def isQueueEmpty():
    global SIZE,queue,front,rear
    if(front==rear):
        return True
    else:
        return False
#Queue 데이터 삽입
def enQueue(data):
    global SIZE,queue,front,rear
    if(isQueueFull()):
        print('Queue is Full')
    else:
        rear+=1
        queue[rear]=data
#Queue 데이터 추출
def deQueue():
    global SIZE,queue,front,rear
    if(isQueueEmpty()):
        print('Queue is Empty')
        return None
    else:
        front+=1
        data=queue[front]
        queue[front]=None
        #뽑을때마다 앞으로 당기면서 queue의 data값 위치 맞춰줘야함
        for i in range(front+1,SIZE):
            queue[i-1]=queue[i]
            queue[i]=None
        front -=1
        rear -=1
        ##
        return data
#Queue front+1 위치 데이터 확인
def peek():
    global SIZE,queue,front,rear
    if(isQueueEmpty()):
        print('Queue is Empty')
        return None
    return queue[front+1]

if __name__=='__main__':
    SIZE=int(input('Queue 크기 입력-->'))
    queue=[None for _ in range(SIZE)]
    front,rear=-1,-1
    while True:
        select = input('삽입(I)/추출(E)/확인(V)/종료(X) >> ')
        if select.lower() == 'x':       # 종료
            break

        elif select.lower()=='i':
            data=input('입력할 데이터>>')
            enQueue(data)
            print('큐 상태 : ',queue)
            print()

        elif select.lower()=='e':
            data=deQueue()
            print('추출된 데이터 >>',data)
            print('큐 상태 : ',queue)
            print()

        elif select.lower()=='v':
            data=peek()
            print('확인된 데이터 >>',data)
            print('큐 상태 : ',queue)
            print()

        else:
            continue            
    print('스택 프로그램 종료')
------------------출력------------------
------------------출력------------------
Queue 크기 입력-->3
삽입(I)/추출(E)/확인(V)/종료(X) >> i
입력할 데이터>>a
큐 상태 :  ['a', None, None]       

삽입(I)/추출(E)/확인(V)/종료(X) >> i
입력할 데이터>>b
큐 상태 :  ['a', 'b', None]        

삽입(I)/추출(E)/확인(V)/종료(X) >> i
입력할 데이터>>c
큐 상태 :  ['a', 'b', 'c']

삽입(I)/추출(E)/확인(V)/종료(X) >> e
추출된 데이터 >> a
큐 상태 :  ['b', 'c', None]        

삽입(I)/추출(E)/확인(V)/종료(X) >> e
추출된 데이터 >> b
큐 상태 :  ['c', None, None]       

삽입(I)/추출(E)/확인(V)/종료(X) >> e
추출된 데이터 >> c
큐 상태 :  [None, None, None]      

삽입(I)/추출(E)/확인(V)/종료(X) >> v
Queue is Empty
확인된 데이터 >> None
큐 상태 :  [None, None, None]      

삽입(I)/추출(E)/확인(V)/종료(X) >> x
스택 프로그램 종료

--> Queue는 FIFO(First In First Out)의 구조이기에 먼저 삽입한놈이 먼저 빠져나감
이를 유의하며 구현
--> deQueue 함수에서 추출할 때 마다 queue 자릿값 맞추기

  • 트리구조(이진트리)

class TreeNode: 
    def __init__ (self):
        self.left=None
        self.data=None
        self.right=None

node1=TreeNode()
node1.data='화사'

node2=TreeNode()
node2.data='솔라'
node1.left=node2

node3=TreeNode()
node3.data='솔라'
node1.right=node3

node4=TreeNode()
node4.data='휘인'
node2.left=node4

node5=TreeNode()
node5.data='쯔위'
node2.right=node5

node6=TreeNode()
node6.data='선미'
node3.left=node6

print(node1.data,end=' ')
print()
print(node1.left.data,node1.right.data,end=' ')
print()
print(node1.left.left.data,node1.left.right.data,node1.right.left.data,end=' ')
------------------출력------------------
------------------출력------------------
화사 
솔라 솔라 
휘인 쯔위 선미

  • 이진탐색트리 전체구현

# 이진 탐색트리 구현
# 전역변수 선언
memory=[]
root=None
nameAry=['블랙핑크','레드벨벳','마마무','에이핑크','걸스데이','트와이스']

class TreeNode:
    def __init__(self):
        self.left=None
        self.data=None
        self.right=None

if __name__=='__main__':
    node=TreeNode() #TreeNode 다 가지는 node 생성함
    node.data=nameAry[0] #node.data에 블랙핑크 들어감
    root=node #root는 블랙핑크 들어간 noode 가지고있음
    memory.append(node) #memory에다가 추가함

for name in nameAry[1:]: #0에는 블랙핑크 들어가있고 그 뒤로 쭉 돌아가면서
    node=TreeNode()
    node.data=name#node.data에 레드벨벳~트와이스 추가로 들어감
    current=root
    while True:
        if name<current.data: #부모노드 왼쪽 / 걸그룹이름 ㄱㄴㄷㄹ 비교해서 작으면 왼쪽으로
            if current.left==None:
                current.left=node
                break
            current=current.left
        else: #부모노드 오른쪽 / 이름 ㄱㄴㄷㄹ 비교해서 크면 오른쪽으로
            if current.right==None:
                current.right=node
                break
            current=current.right
    memory.append(node)
print('이진 탐색 트리 구성 완료')

search=input('찾을 걸그룹 입력 > ')
current=root
while True:
    if search==current.data:
        print(search,'찾음')
        break
    elif search < current.data:
        if current.left==None:
            print(search,'못찾음')
            break
        else:
            current=current.left
    else:
        if current.right==None:
            print(search,'못찾음')
            break
        else:
            current=current.right
------------------출력------------------
------------------출력------------------
이진 탐색 트리 구성 완료
찾을 걸그룹 입력 > 마마무
마마무 찾음

  • 백준 1110번 더하기 사이클


inum=int(input()) #숫자입력
num=inum #num에 내가 입력한 숫자 넣음
cnt=0 #사이클
while True:
    sum_num=(num//10)+(num%10)#sum_num:내가 입력한 숫자의 일의자리+십의자리
    new_num=((num%10)*10)+(sum_num%10)#new_num:왼쪽 항 숫자 일의자리 + 새로운 수 일의자리
    cnt+=1#사이클 카운팅
    if new_num==inum:#새로만든 수와 내가 처음에 입력한 수가 같으면
        break#탈출
    num=new_num#새로 만들어지는 수로 계속 초기화 해줌
print(cnt)

1) 내가 입력받은 두자리 숫자를 새로운 변수에 넣고
2) 무한루프를 돌면서
3) 십의자리,일의자리를 더해서 sum_num 만들고
4) 기존 두자리 숫자의 일의자리 + sum_num의 일의자리 --> 코드로 구현하게 되면 기존 두자리 숫자의 일의자리가 새로운 숫자의 십의자리가 되어야하기에 new_num(새로운 수)=((num%10)*10)+(sum_num%10)와 같이 구현
5) 사이클 카운팅 해주면서
6) 가장 최근에 들어온 숫자를 new_num으로 초기화 시켜주며
7) 조건문을 통해 새롭게 만들어진 숫자가 처음 입력한 숫자와 같아지면 루프 탈출

profile
오윤범
이전 포스트

23.02.14 Day12

다음 포스트

23.02.16 Day14

0개의 댓글