오늘 한 것
- 알고리즘 특강 세션에 참여하였다. 강의내용은 알고리즘의 기본개념과 연결리스트에 대한 내용이다.
- 파이썬으로 몇가지 코딩테스트문제를 풀어보았다. 이 과정에서 reduce,
:=연산자 등을 새로 알게되었다. - 파이썬으로 게임 만들기 미니 팀 프로젝트를 시작하였다. 전체적인 계획을 짜고, 각 객체의 외부에서 불러올 함수들의 이름과 인수들을 미리 정하고, 몇가지 기능들을 구현하였다.
알고리즘 특강 세션 내용
자료구조와 알고리즘
자료구조는 데이터를 효율적으로 관리하는 방법론을 의미한다.
(데이터: 변수, 상수, 파일 등 모든 자료를 의미)
알고리즘은 효율적으로 연산하는 방법이다.
왜 배울까?
문법에 맞는 코드보다 중요한 것은 성능/용량/비용 면에서 좋은 코드이다.
알고리즘과 자료구조에 대한 이해가 있어야 이것이 가능하다.
자료구조/알고리즘의 기본
- 시간복잡도 & 공간 복잡도
- 기본 코드 작성 능력 (구현능력) 현재 트랜드
- 배열&리스트
- 스택&큐
- 정렬 (버블/선택/삽입/퀵/병합)
현재 트렌드는 비전공자의 유입등으로 지엽적인 알고리즘 문제보다는 기본적인 알고리즘 유형에 대한 매우 어려운 문제를 내는 경향이 있으므로 기본 구현능력이 좋아야 한다.
코딩 테스트 공부 순서
- 언어 기초학습
- 자료구조/알고리즘 핵심개념
- 자료구조/알고리즘 기초 문제풀이
- 양치기
- 무엇보다도 "꾸준히 풀어보기"가 중요하다
알고리즘과 자료구조는 반드시 코드로 표현할줄 알아야한다. 개념을 배웠다면 실제로 구현해보거나 관련한 간단한 문제를 풀어보는 것이 좋다.
자료구조: 연결리스트
연결리스트는 자신의 값과 다음 노드의 포인터로 이루어진 노드들로 이루어진다.
이 자료구조는 배열(실제 메모리상에 연속된 공간에 요소들을 저장, 인덱스를 통한 랜덤 엑세스 가능)에 비해 조회 할때의 시간복잡도가 O(n)으로 느린편이나, 배열과 다르게 중간 요소의 삭제, 삽입시 속도가 빠르다(O(1)).
삽입시에는 그림과 같이 삽입할 위치를 찾고 포인터만 바꿔주면 된다.
삽입할 위치의 이전 노드에 저장된 포인터를 꺼내 새로운 노드의 포인터에 대입하고, 이전 노드의 포인터는 새로운 노드의 주소로 바꾼다.
삭제시에는 그림과 같이 삭제할 노드의 포인터를 이전 노드의 포인터에 대입하고, 삭제할 노드는 메모리에서 free(혹은 del)한다.
배열은 삭제/삽입 시 각 요소들을 밀고 당겨야하므로 훨씬 느리다.
reduce
reduce는 함수를 이용해 반복가능한 요소(list 등)의 요소들을 하나의 값으로 연산하게 하는 함수이다.
에를 들어 [1, 2, 3, 4, 5]와 같은 리스트가 있을 때 reduce를 이용해 합계를 구할 수 있다.
import functools
result=functools.reduce(lambda x,y:x+y,[1,2,3,4,5])
# 1+2=3
# 3+3=6
# 6+4=10
# 10+5=15반복문 없이 누적되는 연산을 할 수 있다.
:=, 대입표현식
파이썬 3.8 에서 추가된 연산자이다. 바다코끼리 연산자라고 불린다. 변수 대입(초기화)를 하는 동시에 조건문 등에서 사용가능하다.
list_=[1,2,3,4,5]
n=len(list_)
if n>2:
print(f'리스트 길이가 {n}. 2보다 큽니다.')len(list_)를 반복해서 사용하지 않기 위해 n에 대입하였다.
list_=[1,2,3,4,5]
if (n:=len(list_))>2:
print(f'리스트 길이가 {n}. 2보다 큽니다.')그 한줄을 바다코끼리 연산자를 쓰면 이렇게 줄여서 쓸 수 있다.
이외에도 리스트안에서도 쓸 수 있는 등 활용법이 다양하다고 한다.
x=5
y=x
a=[y,y**2,y**3]
x=5
b=[(y:=x),y**2,y**3]
#a와 b는 같다미니 팀 프로젝트
기능 브레인 스토밍
구현하고 싶은 기능을 정하고 각 기능을 어떻게 구현하고, 어떤 클래스들이 필요한지 회의를 하였다.
구현할 기능들은 다음과 같다:
- 다수의 플레이어블 캐릭터 생성
- 다수의 몬스터 캐릭터 생성
- 1,2 의 다대다 전투
- 전투가 끝나면 새로운 전투를 반복해 최종적으로 보스전(특수 전투)돌입
- 적 처치시 보상
- 레벨업을 통한 능력상승
추가로 구현할 수도 있는 기능들은 다음과 같다:
- 상점기능
- 랜덤 인카운터
- 조건(속도 수치 등)에 따른 전투 순서 변경
컨벤션 정하기
- 생성된 객체를 담는 변수에는 'entity'라는 단어를 쓴다.
- 어떤 클래스의 메소드는 다음 두가지 조건중 하나라도 해당하는 경우가 아니면 클래스 이름을 제일 앞에 붙인다.
1. 부모로부터 상속하는 메서드를 이용해 작성된다.
2. 오버라이딩 하려고 한다.예시) Character 클래스를 상속받는 Hero 클래스에는 부모와 전혀 상관없는 magic_attack 메서드를 넣어야한다.
이 때는 hero_magic_attack으로 이름을 지어 어디에 위치하는지 알기 쉽게 한다.
파일 분리
팀원들과 상의한 끝에 다음과 같이 파일을 분리하여 만들기로 하였다.
이는 협업시 중복 수정 및 충돌의 가능성을 낮추기 위해서 이다.
- game.py: 실제로 실행해야하는 파일로, 핵심적인 게임의 흐름을 통제한다.
- characters.py: 플레이어블 캐릭터나 적 캐릭터의 클래스를 만들어 두는 파일이다.
- battle_management.py: 한번의 전투 내에서의 흐름을 통제하는 코드들을 모아둔다.
- other_functions.py: 화면 표시, 플레이어 선택에 따른 객체 생성, 랜덤이름 생성등 기타 부가 기능들을 위한 코드들을 모아둔다.
dependancy관계는 다음과 같이한다.
역할 분배
역할 분배는 파일을 나눈 목적 대로 파일별로 진행하기로 하였다.
2명씩 묶어서 남은 한명은 플레이어블 캐릭터와 몬스터 캐릭터의 클래스를 만들고, 한 쌍은 game.py 와 battle_management.py를 담당하고(나+한명), 나머지 한 쌍이 oter_functions.py를 담당하기로 하였다.
협업 방식
협업은 처음에는 github을 이용하기로 하였으나, 마감 기한이 촉박한 점, 현재 팀원들 간 구현 역량의 편차가 큼을 고려하여, 하나의 live share서버에서 같은 역할을 맡은 인원끼리 협업하고 담당이 아닌 파일은 최대한 직접 수정하는 것을 피하며 계속 변경사항에 대해 소통하기로 하였다.
전체 구조 설계 - 주석과 스켈레톤 코드
실제 코드가 실행될 때 구체적으로 실행될 내용들을 생략 하고, 주석 위주로 동작의 절차를 기술하고, 서로 파일, 객체 외부에서 호출하게될 함수들의 이름과 매개변수들을 명확히 정하기 위해 함수 이름만 선언해 두는 스켈레톤 코드를 작성하였다.
기능 구현 - 랜덤 몬스터 생성
def battle_scence_make_monsters(self):
maden_monster_dict = {}
# 3개의 임의의 몬스터를 딕셔너리에 추가한다.
for i in range(1, 4):
monster = random.choice(monster_wikipedia).copy() # 딕셔너리 copy
# 숫자형으로 이루어진 value들을 10% 범위 안에서 임의로 조정
for key_ in monster.keys():
if key_ == 'name':
continue
original = monster[key_]
adjustment_level = int(original*0.1)
monster[key_] += random.randint(-1 *
adjustment_level, adjustment_level)
maden_monster_dict[str(i)] = Monster(**monster)
# {'1':Monster(name=goblin...),'2':Monster(name=asdf,...)}
return maden_monster_dict몬스터는 하나의 클래스를 체력등의 수치만 다르게 지정하여 만들기로 하였다.
monster_wikipedia에는 몬스터들의 스탯이 딕셔너리의 리스트로 저장되어있다. 이중에서 랜덤으로 뽑아, 스탯도 랜덤을 조정하여 만들어진 몬스터 객체들을 딕셔너리에 저장한다. 이후 이 딕셔너리를 BattleScene 객체 스스로에 저장해 몬스터를 조회하거나 삭제하면서 전투가 진행되게 된다.
기능 구현 - 전투 진행
def battle_scence_turn(self):
while (self.hero_list or self.monster_list):
for character in self.hero_list:
behavior_dict = {'A': character.attack,
'B': character.hero_magic_attack}
player_input = foo1(behavior_dict) # 일반/마법 공격타입 선택 문장 출력
select_enemy = foo2(self.monster_list) # 공격할 적 선택 문장 출력
behavior_dict[player_input](select_enemy)
# 마법 혹은 공격 후에
self.battle_scene_check_del_entity(select_enemy)
for monster in self.monster_list.keys():
target = random.choice(self.hero_list)
monster.attack()
self.battle_scene_check_del_entity(target)foo1, foo2는 미처 정하지 못한 외부 함수(other_functons)의 이름이다.
while문 한 사이클이 1턴이 된다. 한 턴 안에서 플레이어블 캐릭터 마다 순서대로 공격을 하고, 공격할때마다 적이 죽었는지 확인하는 함수를 불러온다.
이때 플레이어의 행동 선태과 대상 선택은 외부파일 함수의 기능으로 구현한다.
공격의 선택을 if문을 사용하지 않고 dict를 사용하여 더 간략하고 수정이 용이하게 구현하였다.
클래스축약어:클래스 딕셔너리 만들기
플레이어의 입력에 따른 직업을 선택하는 기능을, 플레이어의 입력을 키로 삼아 딕셔너리의 값(클래스)를 불러오는 식으로 만들려고 하였다.
시도 1. class.__subclasses__()
class_dict={}
for class_ in list(Hero.subclasses()):
key_=str(class_)[:]# 봐서 적당히 슬라이싱해 클래스명 추출
class_dict[key_]=class_부모가 되는 클래스의 __subclasses__() 메서드를 쓰면, 자식 클래스들을 가져온다. 이를 이용해 위와 같이 작성할 수 있다.
그러나 이는 형변환과 슬라이싱을 이용해야해서 변거롭다.
시도 2. self.class_name 지정
class Hero():
...
class Archer(Hero):
class_name='Archer'
...
class_dict={}
for class_ in list(Hero.subclasses()):
key_=class_.class_name[0]
class_dict[key_]=class_아예 클래스 안에 적당해 키가 될만한 이름(혹은 입력을 편하게 하기 위해 줄임말)을 지정해둔다. 그러나 사용자가 이미 만들어둔 클래스마다 데이터를 일일히 추가해줘야하는 번거로움이 있다.
해결: class.__name__
이 속성은 해당 클래스명을 string으로 저장하고 있다.
class_dict={}
for class_ in list(Hero.subclasses()):
key_=class_.__name__[0]
class_dict[key_]=class_따라서 위의 두 시도에서의 문제를 모두 해결할 수 있다.
오늘 배운점
- 알고리즘을 공부하는 것에서 가장 중요한 것은 기본개념을 숙지하고 나서부터 꾸준히 양치기하는 것이다.
- 연결리스트의 개념
reduce와:=의 활용- 협업은 생각보다 복잡하고 어려운 문제다. 처음부터 체계적으로 진행하려고 하니 너무 어렵다.
- class에는 다양한 메서드가 존재한다. 이것들을 사용하는 방법을 더 배워야 겠다.
