🤍[알고리즘] SW Expert 파이썬 SW문제해결 기본 - Stack1 강의

Stack 자료구조의 개념

Stack의 특성

Stack
프로그램에서 중요성과 활용도가 매우 높은 자료구조

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조
• 스택에 저장된 자료는 선형구조를 가짐
  • 선형구조: 자료간의 관계가 1대1의 관계를 가짐
  • 비선형구조: 자료간의 관계가 1대N의 관계를 가짐(ex: 트리)
• 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있음
• 마지막에 삽입한 자료를 가장 먼저 꺼냄
  = 후입선출(LIFO=Last-In-First-Out)
  ex) 스택에 1,2,3순으로 자료를 삽입한 후 꺼내면 3,2,1순으로(역순) 꺼낼 수 있음

Stack의 구현

스택을 프로그램으로 구현하기 위해 필요한 내용

1. 자료구조
-> 자료를 선형으로 저장할 저장소가 필요함

• C언어에서는 배열 사용가능
• 파이썬에서는 리스트 사용가능
  이때 리스트로 구현된 저장소 자체를 좁은의미로 스택이라 부르기도 한다.
• 스택에서 마지막 삽입된 원소의 위치를 top이라 부른다.

스택을 사용하기 위해서는 연산이 필요함

2. 연산

• 삽입
  : 저장소에 자료를 저장하고 보통 push라 부른다.

• 삭제
  : 저장소에서 자료를 꺼냄. 꺼낸 자료는 삽입한 자료의 역순으로 꺼내며 보통 pop이라 부른다.

• isEmpty
  : 스택이 공백인지 아닌지를 확인하는 연산

• peek
  : 스택의 top에 있는 item(원소)을 반환하는 연산

Stack의 연산

스택의 삽입/삭제 연산 과정

ex) 빈 스택에 원소 A,B,C를 차례로 삽입 후 한 번 삭제하는 연산과정
최초의 스택은 자료가 없는 공백상태.
이때 마지막 원소를 가리키는 top은 자료가 없기 때문에 -1의 값을 갖는다.

push 알고리즘

def push(item): #삽입할 자료 item을 입력값으로 받음
	s.append(item) #top을 하나 증가시키고 스택 s에 top위치의 자료 item을 저장

파이썬에서는 스택을 리스트로 구현.
파이썬의 리스트는 크기 제한 없이 데이터 삽입을 자유롭게 할 수 있음.
그래서 리스트로 구현시에는 오버플로우 문제를 고려할 필요가 없다.

또한 리스트에 데이터 삽입 시 삽입할 마지막 위치를 기억할 top 변수도 필요없다. append() 메소드를 통해서 리스트의 마지막에 data를 삽입할 수 있다.

pop 알고리즘

def pop():
	 if len(s)==0: #스택에 자료가 없는 상태
     	#underflow처리
        return
     else:
     	return s.pop(-1) #스택의 마지막 값 반환.

top이 -1인 경우, -1은 top의 초기값을 의미하며 이는 스택에 자료가 없는 상태를 의미.
이 경우 underflow처리를 한다.
그렇지 않으면 스택 s에서 top의 값을 반환하고 top은 하나 감소.

파이썬에서는 리스트의 크기를 len함수를 통해 알 수 있으므로 top변수 사용할 필요 없다.
리스트에서는 pop()메소드를 통해서 원하는 인덱스 위치의 값을 삭제하고 반환받을 수 있다. 인자값으로 -1을 입력하면 마지막 위치의 값을 삭제하고 반환받는것.
pop구현시에도 top변수가 필요없다.

stack 구현

1. 스택 구현
2. 구현한 스택을 이용하여 3개의 데이터를 스택에 저장하고 다시 3번 꺼내서 출력하기

def push(item):
	s.append(item)
def pop():
	if len(s)==0:
    	print("Stack is Empty!!") #underflow
        return
    else:
    	return s.pop(-1)
s=[]
push(1)
push(2)
push(3)

print('pop item =>', pop())
print('pop item =>', pop())
print('pop item =>', pop())

스택 구현 고려사항

• 리스트를 사용하여 스택을 구현하는 경우
  • 장점 : 구현이 용이
  • 단점 : 리스트의 크기를 변경하는 작업은 내부적으로 큰 overhead 발생 작업으로 많은 시간이 소요

-> 해결방법
1. 리스트의 크기가 변동되지 않도록 배열처럼 크기를 미리 정해놓고 사용하는 방법
2. 동적 연결리스트를 이용하여 저장소를 동적으로 할당하여 스택을 구현하는 방법

• 장점 : 구현이 용이. 스택에 데이터를 추가, 삭제하는 작업이 많이 일어날 경우 시간을 절약할 수 있다.
• 단점 : 리스트로 구현하는것보다 구현이 복잡함

Stack의 응용

괄호검사

괄호의 종류

• 대괄호 []
• 중괄호 {}
• 소괄호 ()

문장에서 괄호를 올바로 사용했는지를 조사하는 조건

1. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야함
2. 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야함
3. 괄호 사이에는 포함관계만 존재함

ex) 잘못된 괄호 사용
(a(b), a(b)c), a{b(c[d]e}f)

스택을 이용한 괄호 검사

수식을 표현한 문자열의 예
if((i==0)&&(j==0)

문자열에서 한 문자씩 읽어, 만약 여는괄호이면 스택에 저장하고, 닫은괄호일경우 스택에서 pop하여 비교.
스택을 이용하여 저장하고 꺼내어 비교하는동안 조건에 위배되면 올바르게 사용되지 못한 괄호라고 판단

괄호를 조사하는 알고리즘 개요

Function call

함수 호출 관리
: 프로그램에서의 함수 호출과 복귀에 따른 수행 순서를 관리

1. 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로, 후입선출 구조의 스택을 이용하여 수행순서 관리
2. 함수 호출이 발생하면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입
3. 함수의 실행이 끝나면 시스템 스택의 top 원소(스택 프레임)를 삭제(pop)하면서 프레임에 저장되어있던 복귀주소를 확인하고 복귀
4. 함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 됨

함수 호출 수행 순서

1. 프로그램이 실행되면 프로그램의 main함수에 대한 스택 프레임이 스택에 위치한다. 이때 top은 현재 실행 중인 함수, 즉 main함수에 대한 스택 프레임의 위치를 가리킨다.
2. 메인함수에서 F_1함수를 호출
3. F_1함수에 대한 스택 프레임이 스택에 삽입되고 top이 이를 가리킴
4. F_1함수의 실행이 시작됨
5. F_1에서 F_2함수를 호출
6. F_2함수에 대한 스택 프레임이 스택에 삽입되고 top이 이를 가리킴
7. F_2함수의 실행이 시작됨
8. F_2함수가 실행되고 종료됨.
9. F_2함수가 종료되면 스택프레임에 저장된 F_1함수의 복귀주소를 조회하고, F_1함수로 복귀. 이때 스택에서 top의 위치 변경됨. 더이상 F_2에 대한 스택 프레임의 정보가 유효하지 않다는것을 이해해야 한다.
10. F_2함수로부터 복귀후, F_1함수의 남은부분을 수행하고 F_1함수가 종료됨
11. F_1함수가 종료되면 스택에서 top을 변경하여 F_1의 스택프레임 정보를 무효화 하고 main함수로 복귀한다.
12. main함수로 복귀후, main함수의 남은 부분을 수행하고 main함수의 수행을 종료한다.
    

재귀 호출

함수 호출의 특수한 경우

• 자기 자신을 호출하여 순환 수행되는 것
• 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 재귀 호출 방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성할 수 있다.
• 디버깅이 어렵고 잘못 작성하게 되면 수행시간이 많이 소요됨
  

재귀호출은 함수호출과 유사하지만 스택프레임으로 스택에 저장되는 값이 입력값이 틀린 같은 함수의 스텍 프레임을 저장한다는 차이점이 존재

Memoization

피보나치 수열

재귀 호출을 작성할 수 있는 함수 - 피보나치 수열을 구하는 함수

• 0과 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열
  0,1,1,2,3,5,8,13,...
• 피보나치 수열의 i번째 값을 계산하는 함수 F를 정의하면 다음과 같음
  
• 위의 정의로부터 피보나치 수열의 i번째 항을 반환하는 함수를 재귀 함수로 구현할 수 있음

피보나치 수를 구하는 재귀 함수

피보나치 수열을 구하는 함수의 알고리즘

def fibo(n):
	if n<2:
    	return n
    else:
    	return fibo(n-1)+fibo(n-2)

-> 엄청난 중복 호출이 존재한다는 문제점!

-> 같은 입력값에 대한 함수 호출이 많이 중복됨을 확인할 수 있다.

이러한 단점을 보완할 수 있는 프로그램 기법이 Memoization

Memoization

Memoization의 의미

• 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술
• DP(동적계획법)의 핵심이 되는 기술

Memoization 단어의 의미

• 글자 그대로 해석하면 '메모리에 넣기(to put in memory)'라는 의미
• '기억되어야 할 것'이라는 뜻의 라틴어 Memorandum에서 파생
• 흔히 '기억하기', '암기하기'라는 뜻의 Memorization과 혼동하지만, 정확한 단어는 Memoization으로 동사형은 memoize이다.

Memoization 방법을 적용한 알고리즘

피보나치 수를 구하는 알고리즘에서 fibo(n)의 값을 계산하자마자 저장하면 실행시간을 줄일 수 있다.

# memo를 위한 리스트를 생성하고,
# memo[0]을 0으로 memo[1]는 1로 초기화한다.

def fibo1(n):
	global memo
    if n>=2 and len(memo)<=n:
    	memo.append(fibo1(n-1)+fibo1(n-2))
   	return memo[n]
memo=[0,1]

• 조건문에서 memo라는 리스트에 값이 저장되어 있는지 없는지를 조사.
• 만약 기존에 계산하여 저장된 값이 있을 경우에는 다시 계산하지 않겠다는 알고리즘

DP(동적 계획법)

DP(동적 계획법) 알고리즘

• Dynamic Programming의 약자
• 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘
• 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에, 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결
• 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘 설계 기법

DP(동적 계획법)를 적용한 피보나치 수

피보나치 수를 구하는 함수에 DP 적용하기
-> 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있는 최적부분구조로 이루어져있어 DP를 적용할 수 있다.

1. 문제를 부분 문제로 분할
   
   최종적으로 단위요소인 부분집합으로 나눌 수 있다.

2. 부분 문제로 나누는 일을 끝냈으면 가장 작은 부분 문제부터 해를 구함

3. 그 결과는 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구함
   

피보나치 수를 DP에 적용한 알고리즘

def fibo2(n):
	f=[0,1]
  	
    for i in range(2, n+1):
    	f.append(f[i-1]+f[i-2])
    
    return f[n]

반복문을 이용하여 작은값부터 상위로 구해나감

DP 구현 방식

크게 2가지로 나눌 수 있다.

1. recursive 방식 : fibo1()
함수의 호출을 이용한 재귀적 방법
재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생할 수 있다.

2. iterative 방식 : fibo2()
반복문을 이용한 반복적 방법

Memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현한 것이 성능면에서 보다 효율적이다!

DFS(깊이 우선 탐색)

DFS(깊이 우선 탐색)이란?

비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는것이 중요하다.

이러한 알고리즘으로는 2가지 존재
1. 깊이 우선 탐색(Depth First Search, DFS) -> 스택 이용
2. 너비 우선 탐색(Breadth First Search, BFS)

DFS 방법

1. 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색
2. 더 이상 갈곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아옴
3. 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하여 순회

가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용

DFS 알고리즘

스택이 공백이 될때까지 위의 과정을 반복

DFS의 예

검색하고자 하는 그래프

A부터 G까지 정점 가지며 간선으로 연결되어 있음

1. 경로를 역추적할 때 필요한 스택 자료구조와 정점에 방문했는지에 대한 상태 정보를 저장하는 visited 리스트 자료구조를 선언

2. DFS 함수가 호출되는 시점에 방문시작 정점이 주어짐. 이를 visited 리스트에 방문했다고 표시함 (여기서는 정점 A가 시작 정점)

3. 정점 A의 인접 정점을 조사함. B,C의 2개 정점이 방문되지 않은것을 visited 리스트를 조사하여 확인할 수 있다. 이중 하나를 선택 (여기서는 알파벳 순으로 B를 선택)

4. B 정점 정보를 w변수에 저장. v변수에 저장된 방문한 정점의 정보를 스택에 저장. 이는 이후 되돌아올 정점의 정보를 저장하는것이다.
   

5. w에 저장된 정점 정보가 있다면 w를 방문, 즉 화면에 정점 정보를 출력하고 방문했다는 정보를 저장함. 그리고 w정점을 스택에 push

6. v변수에 w의 정보를 저장.

7. v정점, 즉 방금 방문한 B 정점의 이웃한 정점, A D E 중 A는 방문했다고 표시되어 있고 D와 E중 D를 선택하여 w에 저장.

8. 5~6번 반복

9. D의 이웃한 정점 중, F를 선택하여 w에 저장

10. 5~6번 반복

11. F에 이웃한 정점 중, E를 선택하여 w에 저장

12. 5~6번 반복

13. E에 이웃한 정점 중, C를 선택하여 w에 저장

14. 5~6번 반복

15. C에 이웃한 정점 중, 방문하지 않은 정점이 없음. w는 빈값을 가지게 된다.

16. w가 빈값이므로 스택에서 하나의 정점 정보를 pop하고 이를 v에 저장함.

17. v에 저장된 정점, C의 이웃 정점 중 방문하지 않은 정점이 없기 때문에 w는 빈값을 가짐

18. 16번 반복

19. v에 저장된 정점, E의 이웃 정점 중 방문하지 않은 정점이 없기 때문에 w는 빈값을 가짐

20. 16번 반복

21. v에 저장된 정점, F의 이웃 정점 중 방문하지 않은 정점, G를 찾아 w에 저장.

22. v에 저장된 정점 정보 F를 스택에 저장.

23. 5~6번 반복

24. G에 이웃한 정점 중, 방문하지 않은 정점이 없으므로 w는 빈값을 가짐

25. 16번 반복

26. 24번 반복

27. 16번 반복

28. 21번 반복

29. 16번 반복

30. v에 저장된 정점, D의 이웃 정점 중 방문하지 않은 정점이 없기 때문에 w는 빈값을 가짐

31. 16번 반복

32. v에 저장된 정점, B의 이웃 정점 중 방문하지 않은 정점이 없기 때문에 w는 빈값을 가짐

33. 16번 반복

34. v에 저장된 정점, A의 이웃 정점 중 방문하지 않은 정점이 없기 때문에 w는 빈값을 가짐

35. w가 빈 값이므로 스택에서 pop하려 하지만 스택이 비어있음. 따라서 v는 빈값을 가지며 v가 빈값이므로 함수를 종료한다.

정리

• 깊이 우선 탐색의 순서를 따라가보면 A,B,D,F,E,C,G 순으로 탐색함.
  -> 한 쪽 방향으로 계속 탐색하다가 더 이상 진행할 수 없으면 다시 되돌아오는 방법으로 탐색했다는 것을 확인할 수 있음
• 다시 되돌아 오기 위해 사용한 자료구조로 스택을 사용했다는것을 기억해야 한다.