[자료구조와 알고리즘 with Python] Chapter 1 : Stack

김민정·2024년 7월 1일
pythonstack개발기술블로그스택알고리즘자료구조코딩
0

자료구조와 알고리즘 with Python

목록 보기
1/8
post-thumbnail

Intro

6개월간의 부트캠프가 드디어 끝났다...!

작년 겨울 C언어 독학을 시작으로 코딩에 입문하게 되면서
혼자 공부하기엔 커리큘럼이라던지 어디서 부터 시작해야할지 감도 안 잡히고
무엇보다도 의지가 약해질까봐 부트캠프에 지원하게 되었다.
확실히 열심히 하는 동기들과 의지를 다잡아주는 매니저님, 조교님, 멘토님들 덕분에
끝까지 완주할 수 있었던거 같다.
(개근상까지 받은 건 안 비밀 (❁´◡`❁))

사실 이론 교육 4개월 + 프로젝트 기간 2개월로 이론을 다 배우기엔 부족한 시간이었다.
이론 교육 기간엔 하루에 정해진 공부를 다 하고 여유가 있을 땐
개인적으로 C언어, 알고리즘 문제 풀기, C언어로 자료구조를 공부했었다.
하지만, 프로젝트 기간에 들어서자마자 그런 시간을 전혀 못 가지게 되었다...
(사실 Flask 배울 때 강사님이 설명을 예시 위주로만 해주셔서 이해도 잘 못하고 하차할 뻔 했다....ㅎ)
프로젝트 기간 끝난 이후 수료식까지 마지고 일주일 간의 셀프 재정비 기간을 갖은 이후 다시 돌아 왔다.

다시 돌아온 나, 왜 자료구조와 알고리즘을 그것도 파이썬으로 공부하기 시작했나?!

사실 프로젝트 기간이 2개월이었던건 합동 프로젝트 1개월 + 메인 프로젝트 1개월로 해서 2개의 결과물을 만들 수 있는 시간이었다.

"
합동 프로젝트
: 부트 캠프 내 FE, BE, BD(기획) 수강생들로 팀을 이뤄 웹 개발

메인 프로젝트
: 부트 캠프 내 FE, BE 수강생들로 팀을 이뤄 웹 개발.
"

하지만 우리 팀은 기업 연계로 2개월동안 하나의 앱을 만들게 되었고
메인 프로젝트 기간에 멘토님이 조언해주는 것 보단 자료구조를 알려주는게 더 도움이 될거 같다 하여
파이썬으로 자료구조를 배우게 되었다. (다른 수강생들이 엄청 부러워 했다.😉)

그래서 다같이 책도 맞춰서 사서 파이썬으로 자료구조 수업이 진행되었는데...!
시간이 넉넉하지 않고 우리에게 다양한 자료구조, 알고리즘 개념을 알려주고 싶으셨던 멘토님의 욕심(?)으로 책 내용을 너무 후루룩 나가게 되었다...
(하지만, 난 정독하는 걸 선호하는 스타일😥)

산 책이 아깝기도 하고 이어서 공부하기 좋다 생각해서
당분간 자료구조와 알고리즘, 알고리즘 문제 풀이, 파이썬에 관한 글을 올릴 예정이다.😉

그럼 다시 한번 달려보자구우~!

Part 1 : 자료구조

자료구조 : 데이터를 어떻게 저장, 관리, 조직 하는지
- 선형 자료구조(linear) : 자료들을 일렬로 나열하여 저장. 자료 사이 순서 존재.
- 비선형 자료구조(non-linear) : 한 줄로 세우기 어려운 복잡한 관계의 자료들 표현.

data structure
│
├── Linear
│  ├── Stack
│  ├── Queue, Deque
│  └── List
└── Non-Linear
   ├── Tree
   └── Graph

Chapter 1 : Stack (스택)

01 "스택이란?"

동전 케이스, 탄창, 쇼핑카트 정 등 가장 마지막에 넣어둔 것을 가장 먼저 꺼내 쓴다. 한군데에서만 in & out 이 발생한다. (입구가 하나)
→ 후입선출(LIFO: Last-In First-Out)

입구를 보통 스택 상단(stack top)이라 부른다.
스택에 저장되는 것을 항목 또는 요소(element)라 부른다.

이러한 스택들을 쌓아 배열이라고 한다.

01. 추상 자료형

새로운 자료형을 정의하려면 그 자료형의 자세하고 복잡한 내용 대신에 필수적이고 중요한 특징만 골라서 단순화 시키는 작업이 필요하다. 이를 "추상화"라 한다.

추상화를 통해 정의한 자료형을 추상 자료형(ADT: Abstract Data Type)이라한다.

스택의 추상 자료형은 스택이 어떤 자료를 다루고, 어떤 연산이 필요한지 정의해 보는 것이다.

스택에는 숫자와 문자열을 포함한 어떤 자료든지 저장할 수 있다.

02. 스택의 연산

1) 삽입 - push(e)

새로운 요소 e를 스택의 맨 위에 추가.

  • Overflow(오버플로) : 포화 상태인 스택에 새로운 요소를 삽입하는 경우 발생하는 오류.

2) 삭제 - pop()

스택의 맨 위에 있는 요소를 꺼내서 반환.

+) peek() : 스택의 맨 위에 있는 항목을 삭제하지 않고 반환

  • Underflow(언더플로) : 공백 상태인 스택에서 pop()이나 peek() 호출하는 경우 발생하는 오류.

3) isEmpty(), isFull()

isEmpty() : 스택이 비어 있으면 True, 비어 있지 않으면 False 반환
isFull() : 스택이 가득 차 있으면 True, 차 있지 않으면 False 반환.

4) size()

스택에 들어 있는 전체 요소의 수를 반환.

02 "배열 구조로 스택 구현하기"

01. 자료구조의 구현 방법들

  1. 배열 구조
    : 자료들을 배열에 모아 저장하는 방법.
    모든 요소는 인접한 메모리 공간에 저장.
    지정된 메모리 공간이 가득 차면 더는 저장할 수 없음.

  2. 연결된 구조
    : 인접한 메모리 공간이 아닌 흩어져 있는 요소들을 연결하여 하나로 관리하는 방법.
    배열 구조에 비해 유연하게 요소 쉽게 추가 및 삭제 가능. 단, 관리 복잡.

파이썬에서는 리스트를 사용하여 배열을 구현할 예정이다.

02. 배열 구조의 스택을 위한 데이터

  • array[ ] : 스택 요소들을 저장할 배열 (공간)
  • capacity : 스택의 최대 용량. 저장할 수 있는 요소의 최대 개수 (상수)
  • top : 상단 요소의 위치 (변수, 인덱스)
#코드 1.1a: 스택을 위한 데이터
capacity = 10
array = [None]*capacity
top = -1	# 맨 처음 스택이 비어 있으므로 -1로 초기화.

03. 스택의 연산

#코드 1.1b: 스택의 공백 상태와 포화 상태 검사
def isEmpty():
    if top == -1 : return True
    else : return False

def isFull() : return top == capacity-1

#코드 1.1.c: 스택의 삽입 연산
def push(e) :
    # global top
    if not isFull():
        top += 1
        array[top] = e
    else :
        print("stack overflow")
        exit()

#코드 1.1d: 스택의 삭제 연산
def pop() :
    # global top
    if not isEmpty() :
        top -= 1
        return array[top+1]		# 이전 (top+1) 위치의 요소 반환
    else :
        print("stack underflow")
        exit()

#코드 1.1e: 스택의 peek() 연산
def peek():
    if not isEmpty():
        return array[top]
    else : pass

#코드 1.1f: 스택의 size() 연산
def size() : return top+1

04. 스택을 클래스로 구현

객체 지향 프로그래밍 기법을 이용해 구현한다.

#코드 1.2a: 스택 클래스의 정의와 생성자 함수
class ArrayStack :
    def __init__(self, capacity):
        self.capacity = capacity
        self.array = [None]*self.capacity
        self.top = -1

#코드 1.2b: 스택 클래스의 연산
    def isEmpty(self) :
        return self.top == -1

    def isFull(self):
        return self.top == self.capacity-1

    def push(self, item):
        if not self.isFull():
            self.top += 1
            self.array[self.top] = item
        else:
            pass

    def pop(self):
        if not self.isEmpty():
            self.top -= 1
            return self.array[self.top+1]

    def peek(self):
        if not self.isEmpty():
            return self.array[self.top]
        else:
            pass

    def size():
        return top+1

05. 스택 클래스의 사용

스택을 이용해 말을 거꾸로 뒤집는 프로그램을 만들어볼 수 있다.
문자열을 입력 받고, 입력된 문자들을 순서대로 스택에 모두 넣은 다음, 하나씩 꺼내서 출력하기만 하면 된다.

#코드 1.3: 문자열 역순 출력 프로그램
s = ArrayStack(10)

msg = input("문자열 입력: ")
for c in msg:
    s.push(c)

print("문자열 출력: ", end='')
while not s.isEmpty():
    print(s.pop(), end='')
print()

03 "스택의 응용: 괄호 검사"

괄호 검사 문제 조건
조건 1. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.
조건 2. 같은 종류의 경우 왼쪽 괄호가 오른쪽 괄호보다 먼저 나와야한다.
조건 3. 다른 종류의 괄호 쌍이 서로 교차하면 안된다.

#코드 1.4: 괄호 검사 프로그램
def checkBrackets(statement):
    stack = ArrayStack(100)
    for ch in statement:
        if ch in ('{','[','('):		# 왼쪽 괄호(열리는 괄호)의 경우 스택에 삽입.
            stack.push(ch)
        elif ch in ('}', ']', ')'):		
        	# 오른쪽 괄호(닫히는 괄호)의 경우 스택이 공백이면 오른쪽 괄호가 먼저 나온 경우로 조건 2 위반.
            if stack.isEmpty():
                return False
            else:
                left = stack.pop()		# 문자를 pop해서 비교.
                if(ch == "}" and left != "{") or \
                   (ch == "]" and left != "[") or \
                   (ch == ")" and left != "(") :	# 쌍이 맞지 않은 경우 조건 3 위반.
                   return False
    return stack.isEmpty()		# 스택이 공백이면 True 반환. 아닐 경우 조건 1 위반으로 Flase 반환.

checkBrackets('{ A[(i+1)]=0;}')		# True
checkBrackets('if ((x<0) && (y<3)')		# False
checkBrackets('while (n<8)) {n++;')		# False
checkBrackets('arr[(i+1])=0;]')		# False

04 "파이썬 리스트를 스택으로 사용하기"

연산ArrayStackPython List
삽입push()L.append()
삭제pop()L.pop()
상단 들여다보기peek()L[len(L)-1],
L[-1]
공백 상태 검사isEmpty()len(L) == 0
포화 상태 검사isFull()False
(list는 용량이 무한대이므로)
요소의 수size()len()
#코드 1.5: 문자열 역순 출력(파이썬 리스트 이용)
s = list()

msg = input("문자열 입력: ")
for c in msg:
    s.append(c)

print("문자열 출력: ", end='')
while len(s) > 0:
    print(s.pop(), end='')
print()

01. queue 모듈의 LifoQueue 사용하기

파이썬 queue 모듈에서 큐(Queue)나 스택(LifoQueue), 우선순위 큐(PriorityQueue) 등을 클래스로 제공해준다.

연산ArrayStackPython List
삽입push()put()
삭제pop()get()
상단 들여다보기peek()-
공백 상태 검사isEmpty()empty()
포화 상태 검사isFull()full()
#코드 1.6: 문자열 역순 출력(LifoQueue 이용)
import queue

s = queue.LifoQueue(maxsize=100)

msg = input("문자열 입력: ")
for c in msg:
    s.put(c)

print("문자열 출력: ", end='')
while not s.empty():
    print(s.get(), end='')
print()

05 "시스템 스택과 순환 호출"

순환이란 함수가 자기 자신을 다시 호출하여 문제를 해결하는 프로그래밍 기법이다.
순환 호출은 반드시 멈추는 부분이 있어야한다.

01. 팩토리얼의 두 가지 구현

#코드 1.7: 반복 구조의 팩토리얼 함수
def factorial_iter(n):
    result=1
    for k in range(2,n+1):
        result = result*k
    return result
    
factorial_iter(5)	# 120

#코드 1.8: 순환 구조의 팩터리얼 함수
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)
        
factorial(3)	# 6

02. 하노이의 탑

하노이의 탑

  • 규칙
    1. 시작 막대(A)에서 목표 막대(C)로 n개의 원판을 모두 옮겨야한다.
    2. 한번에 하나의 원판만 옮길 수 있다.
    3. 맨 위에 있는 원판만 옮길 수 있다.
    4. 크기가 작은 원판 위에 보다 큰 원판을 쌓을 수 없다.
    5. 중간 막대(B)를 임시 막대로 사용할 수 있다. 
#코드 1.9: 하노이의 탑
def hanoi_tower(n, fr, tmp, to):
    if(n==1):
        print("원판 1: %s --> %s" % (fr, to))
    else:
        hanoi_tower(n-1, fr, to, tmp)
        print("원판 %d: %s --> %s" % (n, fr, to))
        hanoi_tower(n-1, tmp, fr, to)

hanoi_tower(4, 'A', 'B', 'C')

> 출력 결과
원판 1: A --> B
원판 2: A --> C
원판 1: B --> C
원판 3: A --> B
원판 1: C --> A
원판 2: C --> B
원판 1: A --> B
원판 4: A --> C
원판 1: B --> C
원판 2: B --> A
원판 1: C --> A
원판 3: B --> C
원판 1: A --> B
원판 2: A --> C
원판 1: B --> C

<후기>

자료구조 중에 비교적 이해가 쉬운 편이라는 스택이었다.
파이썬으로 자료구조 배우는게 흔하진 않는 것이라고 생각이 드는데 그래도 열심히 책을 완독해봐야겠다.
여기서 지치지 않고 더 열심히 해보자구~!!

profile
김민정
백엔드 코린이😁
다음 포스트

[자료구조와 알고리즘 with Python] Chapter 2 : Queue & Deque

0개의 댓글

관련 채용 정보