알고리즘 스터디 1주차

학습목표: 자료구조와 알고리즘 with 파이썬 1장, 2장

---

Part 1. 자료구조  _ 1장. 스택

 

01-1 스택이란?

 

자료의 입출력: Last In First Out(후입선출)

 

추상 자료형(ADT): 어떤 자료를 다루고, 어떤 연산이 필요한지를 정의

- 스택 등 자료구조들이 다룰 수 있는 자료형: ALL

- 스택의 주요 연산

• 삽입 push(e)
• 삭제 pop()
• 스택의 상단 요소 확인 peek()
• 스택이 가득 차 있는지 isFull() - overflow 방지
• 스택이 비어있는지isEmpty() - underflow 방지
• 스택의 크기 size()

 

01-2 배열 구조로 스택 구현하기

 

배열 구조: 모든 요소를 인접한 메모리 공간에 저장하여 관리

연결된 구조: 메모리 상에서 흩어져 있는 요소들을 연결하여 관리

 

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

- array[]: 스택 요소를 저장할 배열

- capacity: 스택의 최대 용량(상수)

- top: 가장 최근에 삽입한 요소의 위치 //초기화 -1

 

스택의 연산

- isEmpty()

- isFull()

- push(e)

- pop()

- peek()

- size()

StackFunc.py

 

전역변수와 함수 구현 방법의 문제

1) top을 전역 변수로 인식하지 못함 → global 선언

2) 여러 개의 스택이 동시에 필요한 경우, 사용하지 못함 → 스택을 클래스로 구현

 

*자료구조의 추상 자료형과 클래스의 개념은 대응관계이다

클래스 ↔ 자료형

객체 ↔ 자료형의 변수

멤버변수 ↔ 자료(데이터)

멤버함수 ↔ 연산

 

스택 클래스의 선언과 멤버번수 초기화 

스택 클래스의 연산

스택 클래스의 사용

StackClass.py

 

01-3 스택의 응용: 괄호 검사

 

괄호 검사 문제: 소스코드나 주어진 문자열에서 괄호들이 올바르게 사용되었는지 검사

 

괄호 검사 알고리즘 조건

1. 여는 괄호의 개수와 닫는 괄호의 개수가 같을 것
2. 같은 종류일 경우 여는 괄호가 닫는 괄호보다 먼저 나올 것
3. 다른 종류의 괄호 쌍이 서로 교차하지 않을 것

괄호 검사 프로그램

CheckBrackets.py

 

01-4 파이썬에서 스택 사용하기

 

1) 파이썬 리스트를 스택처럼 사용하기: 리스트의 뒷쪽을 스택의 최상단으로 사용

push(e)  &  List.append(e)

pop()   &   List.pop()

peek()    &    List[-1] or List[len(List)-1]

size()    &    len(List)

isEmpty    &    'len(List)==0'

isFull: 리스트는 용량이 무한대이기 때문에 의미없음. 항상 False.

 

2) queue 모듈의 LifoQueue(=스택) 사용하기

StacksInPython.py

01-5 시스템 스택과 순환 호출

 

운영체제가 관리하는 메모리에는 스택 영역이 존재. 함수의 호출과 반환을 위해 사용함.

프로그래밍 기법 중 순환에서 이러한 시스탬 스택을 적극적으로 활용.

 

순환: 어떤 함수가 자기자신을 다시 호출하여 문제를 해결하는 프로그래밍 기법.

 

1-1) 팩토리얼 반복 구현

1-2) 팩토리얼 순환 구현

Factorial.py

2) 하노이 탑 문제

hanoiTower.py

 

---

Part 1. 자료구조  _ 2장. 큐

 

02-1 큐란?

 

자료의 입출력: First In First Out(선입선출)

- 전단(front): 맨 처음에 들어온 요소. 삭제가 일어남.

- 후단(rear): 맨 나중에 들어온 요소. 삽입이 일어남.

- 임시 저장소(buffer)로 사용됨.

 

큐의 연산

• [rear] 새로운 요소를  추가- enqueue(e)
• [front] 맨 앞에 있는 요소를 삭제 - dequeue()
• [front] 맨 앞에 있는 요소를 삭제하지 않고 반환 - peek()
• - isEmpty(), isFull(), size

 

02-2 배열로 구현하는 큐

 

배열 구조의 큐를 위한 데이터

- array[]: 큐 요소를 저장할 배열

- capacity: 큐의 최대 용량(상수)

- rear: 맨 마지막(후단) 요소의 위치(인덱스) //초기화 -1

- front: 첫번째(전단) 요소 바로 이전의 위치(인덱스) //초기화 -1

 

*front를 첫번째 요소로 정의할 수도 있다

 

선형 큐의 문제점과 원형 큐의 원리

선형 큐는 요소를 삽입하기 위해 요소들을 앞으로 옮겨 공간을 확보해야 함

→ 원형 큐는 rear를 회전시켜 그 위치에 요소를 삽입

전단 회전(시계): front ← (front+1)%capacity

후단 회전(시계): rear ← (rear+1)%capacity

 

원형 큐의 클래스 구현

ArrayQueue.py

원형 큐의 활용

ArrayQueueTest.py

 

원형 큐를 링 버퍼로 사용하기

링 버퍼: 가장 최근에 들어온 n개만 저장하고 오래된 데이터를 버린다

RingBuffer.py

 

02-3 덱이란?

 

double-ended queue = deque(덱)

: 전단과 후단에서 삽입과 삭제가 모두 가능한 큐

 

덱의 연산

addFront(e): 전단 회전 (반시계): front ← (front-1)%capacity

addRear(e)

deleteFront()

deleteRear(): 후단 회전(반시계): rear ← (rear-1)%capacity

getFront()

getRear()

isFull()

isEmpty()

size()

 

02-4 상속을 이용한 덱의 구현

 

원형 큐를 상속하여 구현하는 원형 덱 클래스

CircularDeque.py

 

02-5 파이썬에서 큐와 덱 사용하기

 

queue 모듈의 Queue 사용하기

collections 모듈의 deque 클래스 사용하기

QueueInPython.py