오늘 한 것
- 알고리즘 특강 세션에 참여하였다(2). 강의내용은 stack, queue, sorting algorithm들에 대한 내용이다.
- 파이썬으로 게임 만들기 미니 팀 프로젝트(팀과제)를 진행하였다. 전체적인 계획 내에서, 각 객체의 메서드 들을 통해 실제로 기능을 구현하고 디버깅 하는 것을 주로 하였다.
알고리즘 특강 세션 내용
Stack
Stack은 삽입과 삭제를 한쪽 끝(top)에서만 할 수 있도록 제한된 선형 자료구조이다. 자료를 넣으면(push), 꺼낼 때(pop)는 반대의 순서로 나오게 된다. (후입선출, LIFO)
stack의 활용
stack은 다음과 같을 때 주로 사용된다.
1. '최근에 임시저장한' 데이터를 가장 먼저 활용:
함수의 안에서 선언되는 매개변수,지역변수들은 스택에 저장된다.
함수가 끝나면 메모리에서 변수가 사라져야한다. 스택에 저장했으므로 바로 최근에 저장된 것들을 팝 하면 된다.
2. 쌍을 맞추기:
문자열에 주어진 괄호가 쌍이 맞는지 검사
'(':push
')':pop
문자열이 끝나고 stack에 남은 것이 있거나 빈 stack에서 pop하는 경우에는 쌍이 맞지 않는다는 것이다.
3. 뒤로 가기 기능:
웹페이지, 컨트롤제트, 그래프탐색에서 뒤로가기 등에 활용
stack 구현
# in python, stack and queue are made with list
class Stack:
def __init__(self):
self.items = list()
# check list is empty
def is_empty(self):
return self.items == []
# 넣기
def push(self, item):
self.items.append(item)
# 가장 최근에 삽입된 자료 꺼내기
def pop(self):
if self.is_empty():
return None
return self.items.pop(-1)
# 가장 최근에 삽입된 자료 확인
def top(self):
if self.is_empty():
return None
return self.items[-1]
# 현재 입력된 자료 갯수 출력
def size(self):
return len(self.items)
# 전체 비우기
def empty(self):
while self.pop():
TrueQueue
삽입과 삭제를 정해진 반대쪽 양끝에서만 할 수 있도록 제한된 선형 자료구조이다. 자료를 넣으면(enqueue), 꺼낼 때(dequeue)는 넣은 순서로 나오게 된다. (선입선출, FIFO)
Queue 활용
큐는 대기열, 버퍼등을 구현하는데 사용된다. 또한 스케쥴링 알고리즘을 만들 때 쓰인다.
Queue 구현
# in python, stack and queue are made with list
class Stack:
def __init__(self):
self.items = list()
# check list is empty
def is_empty(self):
return self.items == []
# 넣기
def push(self, item):
self.items.append(item)
# 가장 먼저 삽입된 자료 꺼내기
def pop(self):
if self.is_empty():
return None
return self.items.pop(0)
# 가장 먼저 삽입된 자료 확인
def front(self):
if self.is_empty():
return None
return self.items[0]
# 가장 최근 삽입된 자료 확인
def rear(self):
if self.is_empty():
return None
return self.items[-1]
# 현재 입력된 자료 갯수 출력
def size(self):
return len(self.items)
# 전체 비우기
def empty(self):
while self.dequeue():
True정렬 알고리즘
정렬 알고리즘은 요소들을 기준 값에 따라 오름차순, 혹은 내림차순으로 순서대로 줄을 세우는 것이다.
기본 메서드를 제공하지만, 정렬 알고리즘의 원리를 묻는 문제가 나오기 때문에 그 원리를 알아야 한다.
삽입정렬 (O(N^2))
- 0부터 N까지 요소를 순차적으로 선택한다.(i)
- i보다 앞에 있는 요소들을 역순으로 i와 비교해서 i보다 크면, 한칸 뒤로 보낸다.
i 보다 작거나 같은 값을 만나면, 뒤로 보내지 않고 그 값 뒤에 i를 넣는다.
결론:
첫번째 for는 정방향, 두번째 for는 역방향, 앞쪽부터 정렬이 완성된다.
버블정렬 (O(N^2))
가장 큰(뒤로가야할)요소가 거품처럼 쭈루룩 올라가는 모습이 이름의 유래다.
1. 앞에서 부터 순회(i)
2. 인접한것끼리 잘 정렬되어있는지 확인하고 바꿔치기(i,i+1)를 반복한다.
3. 정렬될 때까지 1, 2 를 반복한다. 가장 뒤는 제 위치이므로 반복이 돌 때마다 뒤에서 하나씩 빼고 비교 가능하다. (뒷쪽부터 정렬완료)
선택 정렬 (O(N^2))
- 정렬 안된 부분(최초: 전체 배열)에서 최솟값을 찾고 제일 앞과 치환한다.
- 정렬 안된 부분이 한 사이클당 한칸씩 줄어든다. 1을 다 정렬될때까지 반복한다.
퀵 정렬 (O(nlogn))
분할 정복의 개념을 이용한다. 분할정복은 큰 문제를 작은 문제로 분리해 해답을 찾아 종합하여 큰 문제의 답을 구하는 방법론이다.
- 피벗: 임의로 고른 기준점을 정한한다.
- 피벗보다 큰 것은 피벗 뒤로, 작은 것은 앞으로 넘긴다.
- 앞과 뒤의 sub-array에 대해 1,2를 재귀적으로 실행한다.
- sub-array길이가 1, 0 일때는 그냥 반환한다.
미니 팀 프로젝트
기능 구현 - 전투 진행: 사망한 객체 제거
def battle_scene_check_del_entity(self, target, entity_list: dict):
if entity_list[target].hp == 0:
# 빼기
print(f"{entity_list[target].name}가 쓰러졌다.")
corps = entity_list.pop(target, None) # 키로 찾아서 제거. 없으면 None반환
return corps
return None전투가 진행되는 도중 공격 이후 공격받은 객체가 살아있는지 죽었는지 확인하여 죽었다면 객체를 객체가 저장되어있던 BattleScene객체의 딕셔너리 데이터에서 제거하고, 시체로서 반환하는 함수를 만들었다.
몬스터의 경우 시체(객체)에 reward 데이터(사망시 제공하는 보상. 여기서는 돈)이 있으므로 이후 반환 값을 받은 battle_scene_turn()함수가 리워드를 처리해야 하기 때문에 반환한다.
object.__class__.__name__
화면에 무언가를 출력하는 함수를 만들었다. 해당 함수는 인자로 객체의 딕셔너리를 받는다. 객체 안에는 객체의 클래스명을 따로 명시해두지 않은 상태에서 객체의 클래스명을 문자열로 출력하고 싶었다.
해결: Magic Method
클래스 뿐이 아니라 클래스를 통해 만든 객체에도 기본적으로 제공되는 다양한 특수한 메서드들과 데이터들이 존재하였다. 이러한 것중 메서드들을 magic method 라고 부른다. __이름__과 같은 형태의 메서드들은 파이선에서 기본적으로 제공하는 magic method인 것이다. 예를들어 __init__(객체가 생성될 때 함께 실행됨),__add__(정수, 실수 객체의 덧셈 연산. +연산자를 쓸 때 실제 호출되는 메서드) 등이 있다.
여기서는 1. 객체의 클래스를 가져온뒤, 그 클래스의 이름을 가져오는 식으로 해결하였다.
오늘 배운점
- 큐와 스택 복습
- 정렬 알고리즘 복습
- 협업을 할때 실력의 차이가 존재한다면 너무 이끌려고 하지말고 조금씩 방향만 맞게 던져주며 스스로 나머지를 채울 수 있게 하자
- 시간 남을 때 직접 정렬 알고리즘 구현해보자
