ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Stack, Queue
    파이썬 정리/자료구조와 알고리즘 2024. 5. 1. 14:19

    문제 해결의 알고리즘

    데이터 저장의 자료구조

     

     

    병렬 - or

    직렬 - and

    not회로 : True/ false 반대로 (0,1)

     

     

    전류의 흐름, 오른쪽 전달상태 저장

    => 되먹임 회로: not, not연속 회로 사용을 통해 흐름 내에서 데이터 저장 가능

     

    이에 따른 래치 회로 / 플리플롭 회로 존재 (이해를 위해 탐구 필요)

    =>메모리 내 byte방식으로 저장되는 방법

     

    C 언어 기반 언어들 -> 최종적으로는 배열, 연결리스트 형식으로 메모리에 저장됨


    기본 : array, linked list

    +선형 : stack, queue +비선형 : tree, graph = 기본 자료구조에 특정 규칙 포함한 자료구조

     

    추상적 구조 : 기본 자료에 추상적으로 특정한 규칙 포함

    선형구조 : 순서가 정해져있는 자료구조

    저장된 여러 개의 데이터 중에서 특정 데이터에 순차적으로 접근 할 수 있고, 접근하는 방법

    비선형구조 : 순서가 정해지지 않은 자료구조

    기본 자료구조를 하나가 아닌 다양하게 적용하여 표현

    여러개의 데이터 중에 특정 데이터에 접근하려면 저장된 규칙을 잘 이해하고 알아야 접근 가능

     


    배열 : Array

    번호와 번호에 대응하는 데이터들로 이뤄진 자료구조

    데이터를 순차적으로 저장하여, 개념이 쉽고, 사용하기 편하지만 메모리 사용 효율성이 낮다.

     

    변수이름 - 첫번째 데이터 저장 주소

    ...

    데이터 1 - 2 - 3 ...

    => 정확한 위치를 아는 변수이름으로 호출 필요

    => 주소로 이동 시 1번 데이터는 변화 없음(0), 두번째 데이터는 주소에서 1 변화된 값(연결됨)(1) ...\

    : 주기억장치에 데이터가 일정 공간 확보된 상태에서 주소값 '일정'하게 변화되는 형태로 연달아 저장되는 구조

     

    => 색인은 유용하나 데이터의 삽입 및 삭제 시 효율적이지 않다

    : 공간을 미리 확보하지 않으면 새로운 데이터 삽입을 위해 공간을 다시 확보해야 하며

      삭제되었을때 사용하지 않는 공간이 지속적으로 할당될 수 있어 저장 효율이 떨어질 수 있고

      연속되는 값 사이에 삽입하기 위해서는 이후의 모든 데이터들의 위치를 변화시켜야 한다.

     

     

    연결리스트 :  Linked List

    리스트가 한줄로 연결된 방식의 자료구조

    리스트 = 데이터 저장 공간 + 주소 저장 공간 

     

    노드 = 연결 리스트에서 데이터를 저장하는 단위 = 리스트?

    포인터 = 주소 저장 공간

     

    메모리 사용 효율성이 높아 저장할 때 유리

    삽입 및 삭제 연산이 효율적

    데이터 접근이 느림

    => 단일 연결 리스트 , 이중 연결 리스트, 원형 연결 리스트 등 다양하게 구현 될 수 있음

     

    변수이름 - 첫번째 데이터 저장 주소

    ...

    데이터 - pointer

    ...

    ...

    데이터 - pointer

     

    각각의 데이터가 변수처럼 다른 데이터가 저장 된 주소를 저장할 공간을 함꼐 할당받아 저장됨

    => 데이터 간 독립성, 연결은 주소값으로 정의

    /# C 언어로 구현한 연결 리스트 노드(Node) 정의 - C# 작성 
    typedef struct Node {
    	
        int data;
        struct Node* next;
            
    } Node;

    정수형 데이터 저장 공간  + 별next 주소 저장 공간 = 무조건적 순차접근

    주소 공간의 변경 = 삽입, 삭제 용의 / 따로저장 => 작은공간 활용 가능

    # dict 자료형을 이용하여 정수 데이터 3개를 연결 리스트 자료구조(처럼) 저장
    a = { 'h':[8, 't'], 't':[4, 'u'], 'u':[9, null] }
    
    
    #a[h][0] = 8
    #a[h][1] = 't' -> 다음 데이터 키
    #a[t][0] = 4
    #a[t][1] = 'u' -> 다음 데이터 키
    #a[u][0] = 9
    #a[u][1] = null -> 다음 데이터 키
    
    # h 에 해당하는 head 값은 따로 존재함을 가정한다
    # null 이 tail 값

     


    확장형 자료구조 : 본 교재의 특징

     

    자료구조 : 주기억장치(RAM)에 데이터를 저장하는 방식을 구조적으로 정의하는 것

    알고리즘 : 문제 해결 방안

     

    데이터 저장 방식에 특별한 문제를 해결하기 위해 문제 해결의 절차, 알고리즘을 포함한 자료구조 = 확장형 자료구조

     => 스택, 큐, 트리, 그래프

     


     

    Stack

    새로운 데이터를 저장할 떄 가장 마지막에 저장하며, 이러한 저장 동작을 Push 동작이라고 한다.

    저장된 데이터를 불러 올 때 가장 마지막에 저장된 데이터를 읽어오며, 이러한 불러오기 동작을 pop동작이라고 한다.

     

    이 구조는 데이터가 들어가고 나가는 출구가 하나인 자료구조이며 LIFO(Last In First Out) 선입후출 구조라고도 한다.

     

      기본자료구조 스택
    규칙 반드시 지켜야하는 순서나 규칙이 없다 규칙을 가지는 데이터 저장 방식
    데이터 읽기 배열 : 인덱스 필요
    연결리스트 : 순차적 확인 필요`
    LIFO

    배열로 스택 구현 : 스택의 크기를 미리 정해놓고, 미리 정해놓은 크기를 주기억장치에 확보해야 한다.

    연결리스트로 ''    : 스택 크기의 한정 X, 삽입 삭제 및 데이터 저장이 효율적이다.

     

    구현 구조

    D TOP  
    C     Data.C Pnt.b
    B   ...
    A   Data.B Pnt.a
    Array.Stack   Data.A Null
      Linked List.Stack

     

    스택 활용 문제해결 예

     

    괄호 확인 문제

    print("계산 결과는 {0}입니다..".format((int(a)+int(b)))

    열린 괄호문 수 = 닫힌 괄호문 수 = 5개

    => 괄호의 개수를 저장하고 변수 정의 > 왼쪽괄호 +=1, 오른쪽괄호 -=1 > 저장변수값 == 0 :

     

    #일반 알고리즘
    a = input()
    def close_check (a) :
        
        cnt = 0
        for i in a :
            if i == '(' :
                cnt +=1
            if i == ')' :
                cnt -=1
        if cnt == 0 :
            return print('clear')
        else :
            return print('fail')
    close_check (a)

     

    왼쪽 괄호에 대해서 push(+1) 오른쪽 괄호에 대해서 pop(-1)동작을 한다

    = 한개의 입력값을 받고 ->  저장할 것인지 판단 후 -> 출력

    a_count = []
    def push(push_data) :
    	a_count.append(int(push_data))
        
    def pop() :
    	a_count.remove(a_count[-1])
        
    a = input()
    
    for i in a :
    	if i == '(' :
        	push(i)
        if i == ')' :
        	pop()
    if len(a_count) == 0 :
    	print('OK')
    else : 
    	print('Error')

     

     

     

    우선순위 연산 문제

    연산자와 피연산자를 표현하는 방법에는 3가지로

     

    중위 : 기본 표기법으로 피연산자를 연산자들 중간에 표현하는 표기법

    전위, 후위 : 연산자와 피연산자를 분리하여 표기하는 방법 // 연산자 기준 피연산자의 위치 에 따른 분류이다.

    중위 : A*B - C/D
    	((AB)*(CD)/)-
    후위 : AB*CD/-

     

    이러한 우선순위에 맞춰 후기 표기된 연산식을 계산하는 프로그램은

    피연산자는 PUSH(), 연산자를 만나면 피연산자를 POP()하여 연산 후 다시 PUSH(), 마지막 POP()으로 연산 결과 출력

    의 순서로 이뤄지게 된다.

    a_stack=[]
    
    def push(push_data) :
    	a_stack.append(int(push_data))
    # 숫자 list로 저장
    
    def pop () :
    	a = 0
        a = a_stack[-1]
        a_stack.remove(a_stack[-1])
        return a
    # 숫자 출력 후 잔여값 제거    
    
    print(" 계산식을 후위표기법으로 입력하시오. \n연산자와 피연산자는 \",\"로 분리해서 입력하세요.")
    a = list(input().split(','))
    
    for i in a : 
    	if i = '+' or i = '-' or i = '*' or i = '/' :
        	pop_data1 = pop()
            pop_data2 = pop()
            if i = '+'  :
            	push(pop_data2+pop_data1)
            if i = '-' :
            	push(pop_data2-pop_data1)
            if i = '*' :
            	push(pop_data2*pop_data1)
            if i = '/' :
    			push(pop_data2/pop_data1)
        else : 
        	push(i)
    # 연산 구현        
    
    print(pop())
    # 최종값 출력

     


     

     

    큐(Queue)

    데이터를 저장하는 규칙 :

    새로운 데이터를 저장할 때 항상 가장 마지막에 저장하며(Enqueue), 저장된 데이터를 불러 올 때 가장 처음에 저장된 데이터를 읽어온다(Dequeue)

    = 입출구가 다른 구조 , FIFO(First In First Out) 선입 선출

     

      배열 자료구조상 일정 크기를 미리 지정하고 사용한다. Head는 비워지고 Tail을 추가하려고 하나 고정된 위치로 인해 추가 하지못하는 경우를 해결하기 위해 '순환 큐' 라는 특징을 가지게 한다.

      즉, 데이터를 이동하는 것이 아니라, 큐의 가장 앞을 가지는 변수 Front와 큐의 가장 마지막 데이터의 위치를 가리키는 변수 Rear를 두어 순환 큐를 구현한다.

      A B C    
    Index 0 1 2 3 4
      front   rear    

     

      연결 리스트 자료구조를 이용한 큐는 LL의 가장 처음 노드를 읽어오고, 새로운 데이터는 연결 리스트의 마지막에 저장하도록 구현할 수 있다.

      C    
      B   D
    A       E
      (front)   F  
      G(rear)  

     

     

      일반적으로 대기자 명단 등을 '큐'라고 한다. '롤큐 돌려라' 등의 말도 많이 사용하는 것처럼 우선순위 없이 동등한 조건에서 순서를 정하는것을 큐라고 하며, 큐는 일반적인 순서를 정하는 프로그램에서 많이 사용된다. 

     

    w_no = 100
    queue = []
    
    def enqueue(data) :
    	queue.append(data)
        
    def dequeue(data) :
    	dequeue_object=None
        if len(queue) 0 :
        	print("Queue is Empty")
    	else :
        	dequeue_object=queue[0]
            queue.remove(queue[0])
            
            return dequeue_object
            
    while True :
    	a = int(input("대기표 뽑기:1, 업무처리:2, 종료:3\n")
        
        if a==1 :
        	enqueue(w_no)
            w_no+=1
            print("현재 대기표번호:",w_no)
        elif a==2 :
        	b==dequeue()
            print("현재 업무처리번호:",b)
        else : 
        	break

    1: 100번부터 시작하는 번호표 뽑기, 2: 한명씩 선입선출 되는 업무처리, 3: break조건

     

     

     

     

    P.103까지

    '파이썬 정리 > 자료구조와 알고리즘' 카테고리의 다른 글

    결정문제와 비결정문제  (0) 2024.05.16
    알고리즘 성능  (0) 2024.05.07
    Tree, Graph  (0) 2024.05.02
Designed by Tistory.