확장형 자료구조

• 자료구조란 주기억장치에 데이터를 저장하는 방식을 구조적으로 정의하는 것을 말하고, 알고리즘은 문제를 해결하는 방식을 말한다.

• 이때 자료구조인 데이터를 저장하는 방식에 특별한 문제를 해결하기 위하여 문제 해결의 절차, 즉 알고리즘을 포함한 자료구조가 존재

• 기본 자료구조에 문제 해결을 위한 특정한 규칙을 포함시킨 자료구조로써 확장형 자료구조라 정의하였음

• 스택, 큐, 트리, 그래프를 포함시켜 설명함

• 스택과 큐는 선형 자료구조에 속해 데이터가 저장될 때 순서를 가지고 저장되는 구조를 가지므로, 순서에 맞추어 데이터에 접근하고 수정, 삭제할 수 있다

• 스택과 큐는 알고리즘을 포함한 자료구조라 정의할 수 있음

스택

• 스택은 기본 자료구조에 규칙을 포함한 확장형 자료구조, 규칙은 데이터를 저장하는 규칙을 말한다
• 새로운 데이터를 저장할 때 항상 가장 마지막에 저장하며, 이러한 저장 동작을 push라고 부름
• 스택은 저장된 데이터를 불러올 때 가장 마지막에 저장된 데이터를 읽어오며, 이러한 동작을 pop이라고 부름
• 스택은 이와 같은 규칙을 갖고 있어서 데이터가 들어가고 나오는 출구가 하나인 자료구조라고 하기도 하고, LIFO(Last In First Out)구조라 함
• 기본 자료구조의 경우 순서가 상관이 없고, 배열이나 연결 리스트의 경우 인덱스를 알아야 한다. 하지만 스택의 경우 무조건 가장 마지막에 젖아한 데이터를 불러온다.
• 스택의 경우, 기본 자료구조, 배열 자료구조, 연결 리스트 자료구조등 다양하게 구현이 가능하다.

스택을 이용한 문제 해결 예

괄호 확인 문제
프로그래밍할 때 열린 괄호의 수와 닫힌 괄호의 수가 다르면 프로그램 오류가 발생한다. 이때 오류 발생 프로그램은 괄호 확인 문제를 해결한 프로그램

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

• 예문을 본다면 열린 괄호의 수는 5개이고, 닫힌 괄호 수도 5개이다.
• 열린 괄호의 수와 닫힌 괄호의 수를 확인하는 프로그램은 스택 자료구조를 이용하면 쉽게 프로그래밍할 수 있다.

괄호개수 저장 문제

• 괄호의 개수를 저장하는 변수를 하나 정의한 후 왼쪽 괄호를 만나면 괄호 개수 저장변수를 하나 저장시키고, 오른쪽 괄호를 만나면 괄호 개수 저장변수를 하나 감소시킨다.
• 입력된 문자열을 모둔 확인하고 난 후 괄호 개수 저장변수의 값을 확인하면, 괄호 개수가 맞는지 틀리는지 확인할 수 있다

a = input()
cnt = 0
for i in a:
    if i == "(":
        cnt += 1
    elif i == ")":
        cnt -= 1
if cnt == 0:
    print("ok")
else:
    print("error")

• 일반 알고리즘을 이용하여 푸는 방법

cnt = []

def push(push_data):
    cnt.append(int(push_data))

def pop():
    cnt.remove(cnt[-1])

a = input()

for i in a:
    if i == "(":
        push(i)
    elif i == ")":
        pop(i)
if len(cnt) == 0:
    print("ok")
else:
    print("error")

• 스택 자료구조를 이용한 괄호 문제 해결

우선순위 연산 문제

• 컴퓨터에서는 산술 연산자마다 우선순위가 있다.
• 우선순위에 따른 연산을 하는 문제
• 컴퓨터에 연산자와 피연산자를 표현하는 방법에는 후위 표기법, 전위 표기법, 중위 표기법의 세가지가 존재
  • 중위 표기법은 기본 표기법으로 피연산자를 연산자들 중간에 표현하는 표기법
  • 전위 표기법과 후위 표기법은 연산자와 피연산자를 분리하여 표기하는 방법
    • 전위 표기법은 연산자를 피연산자 앞에 두는것, 후위 표기법은 피연산자를 연ㅅ나자들 뒤에 표기하는 법

우선순위 연산(후위 표기법 사용)
A*B-C/D 연산 -> ((AB)*(CD)/) -> AB*CD/-

• 스택자료구조로 해결 하는 방법 : 피연산자는 스택에 push하고 연산자이면 스택에 저장된 데이터를 pop하여 연산후 다시 결과 데이터를 push한다.
• 연산식을 마치면 마지막 스택에 저장된 데이터를 pop하여 결과로 출력한다.

stack = []

def push(push_data):
    stack.append(int(push_data))

def pop():
    a = 0
    a = stack[-1]
    stack.remove(stack[-1])
    return a

a = list(input().split(","))

for i in a:
    if i == "+" or i == "-" or i == "*" or i == "/":
        pop_data = pop()
        pop_data2 = pop()

        if i == "+":
            push(pop_data2 + pop_data) # 스택이기에 순서 필수

        elif i == "-":
            push(pop_data2 - pop_data)
        
        elif i == "*":
            push(pop_data2 * pop_data)
        
        elif i == "/":
            push(pop_data2 / pop_data)
    
    else:
        push(i)
print(pop())

• 스택을 정의하고 스택의 동작인 push와 pop을 정의한다.

큐

• 큐(Queue)는 기본 자료구조에 규칙을 포함한 확장형 자료구조

• 규칙은 데이터를 저장하는 규칙을 말한다

• 큐의 규칙은 매우 간단

  • 새로운 데이터를 저장할 때 항상 가장 마지막에 저장하며, 이러한 저장 동작의 경우 일반적으로 Enqueue 동작이라고 함
  • 큐는 저장된 데이터를 불러올 때 가장 처음에 저장된 데이터를 읽어오며, 이러한 불러오기 동작을 Dequeue 동작이라고 함

• 큐를 데이터가 들어가고 나오는 출구가 다른 자료구조라고 하기도하고, 가장 빨리 저장된 데이터를 가장 빨리 불러올 수 있는 의미로 FIFO(Fisrt In First Out) 구조라고 함

• 큐는 기본 자료구조에 규칙을 포함시킨 자료구조, 실질적으로 주기억장치에 데이터가 저장되는 구조는 기본 자료구조인 배열이나 연결 리스트로 저장됨

• 큐도 배열 자료규조를 이용하여 구현할 수 있고, 연결 리스트 자료구조를 이용하여 구현할 수 있다.

큐를 이용하여 해결하는 문제

대기자 명단

• 대기자 명단등을 큐라고 한다.
• 큐는 일반적인 순서를 정하는 프로그램에 많이 사용
• 은행 업무 프로그램에서 대기표 관리 프로그램은 큐로 해결한 대표적인 문제

w_no = 100
queue = []

def enqueue(data):
    queue.append(data)

def dequeue(data):
    deq_ob = None
    if len(queue) ==0:
        print("queue is empty")
    else:
        deq_ob = queue[0]
        queue.remove(queue[0])

    return deq_ob

while True:

    a = int(input("1 : 뽑기, 2: 업무처리, 3:종료"))

    if a == 1:
        enqueue(w_no):
        w_no += 1
        print(w_no)
    elif a == 2:
        b == dequeue()
        print(b)
    else:
        break

• 큐는 시스템 프로그램에서 우선쉰위가 같은 작업을 예약하는 데 사용되며, 특히 운영체제에서 프로세스 관리 시스템을 개발할 때 사용되는 자료구조