01/10 본캠프 #12

guno park·2024년 1월 10일

알고리즘 강의 유니티 부트캠프 중요 팀 프로젝트

본캠프

목록 보기

13/77

알고리즘 강의 - 2일차

스택

원소의 삽입과 삭제가 한쪽 끝, top에서만 이루어지도록 제한되어 있는 유한 순서 리스트
후입선출(LIFO : Last in First Out)
삽입 : Push
삭제 : Pop

반복문을 잘못만들어서 무한반복이되거나 하면 범위를 벗어나면 흘러넘치는데 그걸 스택 오버플로우라고 부름

만드는 법 (예시)

배열 만들고(string[])
마지막을 뜻하는 top을 만들어줌(int)
생성자로 얼마 크기로 만들건지 받아줌 (stack(int i))
top은 -1로 시작

왜냐 arr[-1] = 없는게 아니라 배열 마지막을 가져옴. 스택은 들어온 순서대로 빠진다.

Push로
if (top >= arr.Length-1)이면 스택 가득참
아니면 arr[top++] = data;
Pop 스택에서는 arr.Length가 아니라 top으로 크기를 판단함
스택 출력한다고 하면
for(int i =0;i<=pop;i++) //top이 인덱스 크기기 때문에 작거나 같아야됨.
이런식으로
Pop //삭제시킬 원소를 반환해줘야됨
public string Pop(){
if(top<0) // 스택이 비었다
아닐때는 arr[top--] return //top을 줄여줌.
Peek 마지막 원소를 훔쳐봄
Pop이랑 똑같이 예외처리하고
return arr[top]
Delete
if (top < 0) 이면 예외처리
아니면 top--

top--를 해주면 다음에 스택에 Pop을 해도 지우려던 값은 안나오고, Push를 하면 어차피 덮힌다.
스택을 이용해서 리스트의 순서를 역순으로 만드는데 유용
리스트에서 스택으로 Push하고 다시 pop하면 뒤집어짐

Queue

스택이 한쪽끝만 뚫려있으면 큐는 양쪽 다
한쪽 끝에서는 삽입만, 또 다른 끝에서는 삭제만 하도록 제한되어 있는 유한 순서 리스트
선입선출 (FIFO : First in First Out)
삽입 : Enqueue
삭제 : Dequeue

큐 만들어보기 (예시)

스택에서는 top, 큐에서는 front, rear (int) 인덱스를 뜻함
string[]
생성자로 배열 크기만큼 만들어주기
front = 0; rear = -1;

중요

생성자에 매개변수로 넣은 게 클래스 멤버랑 이름이 같을 때가 있는데,
public class Queue
{
	int maxSize;
	public Queue(int maxSize)
    {
	this.maxSize = maxSize 이렇게 하면 컴퓨터가 구분할 수 있다 
	}
}

isfull, isempty //큐가 가득 찼거나, 비어있는지 체크

if (rear >= maxsize - 1) - isfull 예외처리
rear >= maxsize - 1 //이렇게 하면 bool값을 반환할 수 있음.
if (rear < front) - isempty - 예외처리
return rear < front //여기도

Enqueue(string Data)
if (IsFull) - 예외처리
arr[++rear]=data;
return data
Dequeue
if (IsEmpty) 예외처리
return arr[front++]

7.peek
return arr[front]

선형 큐의 문제점
rear = Length-1인 경우 큐의 상태가 full이라고 판단하지만 반드시 Length개의 원소가 큐에있지 않다.
해당 큐에서 삭제가 일어났다면 그만큼 빈 공간이 생긴다.
빈 공간을 없애기 위해 모든 원소들을 앞쪽으로 이동시키고 front와 rear를 재설정한다.
배열의 원소가 많은 경우에 연산의 지연 문제가 심각해진다.
선형큐를 고친게 원형큐 (기본으로 있는 Queue는 원형큐 / 예시로 만든게 선형큐)

프로그램 평가

프로그램의 평가 기준

원하는 결과의 생성 여부
시스템 명세에 따른 올바른 실행 여부
프로그램의 성능
사용법과 작동법에 대한 설명 여부
유지 보수의 용이성
프로그램의 판독 용이

프로그램의 성능 평가

성능 분석
프로그램을 실행하는데 필요한 시간과 공간의 추정
성능 측정
컴퓨터가 실제로 프로그램을 실행하는게 걸리는 시간 측정

시간복잡도 LogN 나오는 경우

for (int i =0;i<n; i=i*10)

버블정렬

서로 인접한 두 원소를 검사하여 (오름차순 or 내림차순)으로 나열
구현하기 쉽고 정밀한 비교가 가능
모든 인덱스를 비교하므로 연산시간과 성능이 불규칙적이고 배열이 클수록 비효율적

선택정렬

원소를 삽입할 위치를 정해두고 어떤 원소를 삽입할 지 선택
배열의 최솟값을 찾고 맨앞의 인덱스와 교체하여 오름차순으로 나열
구현하기 쉽고 버블정렬보다 값으 복사와 이동이 적어 비교적 빠름
데이턱 커질수록 효율이 떨어지고 정렬속도가 고정적으로 n의 제곱만큼 걸림

퀵정렬

가장 보편적으로 쓰이는 정렬
피벗을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬
현재 모든 정렬 알고리즘보다 빠른 속도를 자랑한다
정렬된 리스트에 대해서는 수행시간이 더 오래 걸린다.

정리

알고리즘은 그 자체를 아는 것 보다 해결방법을 아는 게 더 중요하다

내일부터 알고리즘 코드카타 들어가는 데, 몸으로 하다보면 늘겠지. 열심히 합시다.

팀 프로젝트 - Text RPG 만들기

오늘 만든 것의 구조

메서드 재활용 하기

만들던 것 중에 전투 시작 전에도 상태 보기를 할 수 있는 선택지가 있었다.
어제는 그 선택지를 내가 만드는 Battle : Scene에도 똑같이 만드는 것이였지만,
오늘은 내가 어디에서 '상태 보기'를 선택했는지 기억하고, 되돌아 갈 수 있는 기능을 만들었다.

enum 사용하기

내가 어떤 상태였는지 기억하는데는 enum이 쓰기 좋다는 생각이 들었다.
1. 그래서 NameSpace 바로 밑에 enum을 선언해주었다.

public enum Doing { beforebattle, battle_ing, beforeDungeon }

'상태 보기' 선택지가 있는 곳에서 선택할 경우, 여기가 어디 였는지 기억해준다.

 case 1:
     doing = Doing.beforebattle;
     Game.game.ChangeScene(new PlayerInfo());
     break;

'상태 보기'에서 돌아가기 (0번)을 입력할 때, enum의 상태에 따라 돌아갈 위치를 다르게 한다.

case 0:
    if (Dungeon.doing == Doing.beforebattle)
        Game.game.ChangeScene(new Dungeon.Battle());
    else if (Dungeon.doing == Doing.beforeDungeon)
        Game.game.ChangeScene(new Dungeon());
    else
        Game.game.ChangeScene(Game.game.idle);
    break;

트러블슈팅

문제 : enum doing의 선언 위치를 잘못 지정해서 다른 class에서 호출하지 못하는 문제가 발생했다.

해결 : 처음에는 Battle : Scene 내에 있었지만, 범위를 넓혀 적용하기 위해 내 cs코드의 최상단으로 꺼내주었다. 그리고 public static으로 선언해주어 다른 스크립트에서도 참조할 수 있도록 접근자를 변경해주었다.

결과

중복되는 동작의 Scene을 줄이는 것으로 코드가...보기 이뻐졌다.

던전 구성하기

회의에서 제시한 '던전을 맵 형태로 구성해보기'를 주제로 진행했다.

던전 구성

던전을 구성하는 요소로
1. 맵 / 2. 방 이벤트 / 3. 보스
라고 생각했다. 맵은 틀을 잡아놨고 맵 이동과 방 이벤트를 엮기 위해 여러 방법을 써봤다.

bool[]

처음에는 Bool[] 배열로 작성해서 방 이벤트를 클리어 할때마다 그 위치의 값을 true로 바꿔주는 코드로 작성을 했다.

문제 : bool로 작성 할 시 두 가지로 밖에 표현 못 하고, 방마다 이벤트를 설정하기 어려움

int[] & Dictionary

해결
그래서 int배열과 Dictionary로 바꾸는 방법을 생각해보았다.

public static void dungeonsetting() //던전 최초 입장 시 한번만 돌아감
{
    isdungeonclear = false;
    isclear = new Dictionary<int, string>(){
    { 0,"X"}, { 1,"X"}, { 2,"X"},
    { 3,"O"}, { 4,"H"}, { 5,"B"} };
    dungeon = new int[3, 3] { 
    //보스방이랑 시작위치만 고정하고 나머지 방은 Random으로 섞어버리자.
    // 전투 4개, 함정 2개, 보상 1개 해서 배열 만든다음에 오더바이해서 섞어버리고 포문으로 넣어버리는 게 더 깔끔할 듯.
    // 0 : 미클리어 - 전투, 1 : 미클리어 - 함정, 2 : 미클리어 - 보상, 3 : 클리어, 4 : 현재위치, 5 : 보스방
    { 5, 2, 0 },
    { 2, 1, 0 },
    { 0, 0, 3 } }; //임의로 지정한 방 이벤트
    Forsave.dungeonposx = Forsave.dungeon.GetLength(0) - 1; //최초 시작위치 설정
    Forsave.dungeonposy = Forsave.dungeon.GetLength(1) - 1;
}

이렇게 작성 할 경우, 방마다 이벤트를 지정할 수도 있으며, 현재 위치를 매 이동마다 표시해 줄 수도 있다.

현재 위치 표시하는 방법

머리로는 이해하고 있는데 말로 풀기가 애매해서 그림을 그렸다

1. 방에서 이동할 때 = 나갈 때 그 방 값을 3으로 바꿔줌 -> 맵에는 "O"로 표시됨
2. 이동한 방(씬)을 클리어하고 다시 이동하는 씬을 로드하는 구문에서 이동할 방 값을 4로 바꿔줌
-> 맵에는 "H"로 표시됨.

던전 진행현황 저장하기

씬을 전환할 때, 그 씬에 저장된 값들이 초기화 된다.
만약 초기화 시키고 싶지 않은 변수들이 있다면 네임스페이스 바로 밑에 저장용 클래스를 만들어 저장하는 것도 방법이다.

 public class Forsave()
 {
     public static bool Dungeonfirst; //첫 입장인지
     public static bool isdungeonclear; //던전이 클리어 됬는 지 -> 좋은방법 찾아서 삭제 예정
     
     public static int dungeonposx; //던전 내 현재 위치 저장용
     public static int dungeonposy;
     
     public static int dungeonClearCnt; //던전 클리어 횟수 - 둘다 퀘스트나 전직에 사용
     public static int KillCnt; //몹 잡은 횟수
     
     public static Dictionary<int, string> isclear;
     public static int[,] dungeon = new int[3, 3]; 
  }

위 값들은 위의 Datasetting()이나 다른 특정한 상황에서만 값이 변하기 때문에, 일반적으로는 계속 값이 저장된다고 보면 된다.

계속 쓰는데 static이 정확하게 어떤 역할을 하는지 알아보자.

맵 구성하기

그리기에는 3주차 과제 틱택토를 재활용했다.

 Console.WriteLine("     |     |     ");
 Console.WriteLine("  {0}  |  {1}  |  {2}  ", roomname[0], roomname[1], roomname[2]);
 Console.WriteLine("_____|_____|_____");
 Console.WriteLine("     |     |     ");
 Console.WriteLine("  {0}  |  {1}  |  {2}  ", roomname[3], roomname[4], roomname[5]);
 Console.WriteLine("_____|_____|_____");
 Console.WriteLine("     |     |     ");
 Console.WriteLine("  {0}  |  {1}  |  {2}  ", roomname[6], roomname[7], roomname[8]);
 Console.WriteLine("     |     |     ");

기본적인 맵 형태는 3X3으로 잡아놓고, 나중에 필요에 따라 늘려보려 한다.
roomname을 통해 방마다 표시해줄 방의 정보를 입력해준다.

 string[] roomname = new string[9];
 int j = 0;
 foreach (int i in Forsave.dungeon)
 {
     switch (i)
     {
         case 0:
             roomname[j] = Forsave.isclear[0];
             break;
         case 1:
             roomname[j] = Forsave.isclear[1];
             break;
         case 2:
             roomname[j] = Forsave.isclear[2];
             break;
         case 3:
             roomname[j] = Forsave.isclear[3];
             break;
         case 4:
             roomname[j] = Forsave.isclear[4];
             break;
         case 5:
             roomname[j] = Forsave.isclear[5];
             break;
     }
     j++;
 }
 j = 0;

방의 배치 순서대로 이벤트가 배정되어 있기에 foreach와 switch를 사용해 배열을 생성했다.

문제

여기서 자그만 문제가 발생했었는데, roomname 배열에 특정 값들이 null로 초기화 되어있었다.
다행히 금방 해결했는데
해결

roomname[]에 j가 아니라 i를 넣어서 0~5의 값들만 초기화 시켜줘서 그렇다.
다시 j로 바꿔주면 0~8까지 정상적으로 출력된다.

던전 내 이동하기 구현

던전 이동은 우리 프로젝트에 입력값 검증이 int로 잡혀있어서 넘버패드로 사용했다.
각 방향으로 이동할 수 있는 최대,최솟값만 설정해주고 해당 축의 값만 증감시켜줬다.

문제
원래는 각 방향 이동마다 이벤트 발생 메서드를 따로 작성했는데, 다른 부분들 작성하면서 슬쩍 보니 요약이 가능할 것 같앗다.

해결
입력 받은 후의 위치 좌표를 다시 스위치에 넣어서, 그 위치값에 따라 불러올 이벤트를 선택해줬다.
※주의점 : 4는 현재 위치로 case 4: 는 다루지 않는다.
하지만 case 3:은 클리어한 방끼리 이동할 때도 위치가 바뀐다는 것을 표현해주기 위해 작성해야한다.

보스 전투 구현하기

보스 몬스터를 따로 만들었다.
보스 전투를 구현하기 위해 필요한 과정이 몇 가지 있었는데 차례로 소개해보자면
1. 보스방인지 어떻게 알고 구현할 것인가 -> 던전 내 이동에서 보스방을 따로 지정함 (O)
2. 보스방일 때 몬스터 스폰을 어떻게 할것인가. (O)

if (Forsave.dungeon[Forsave.dungeonposx, Forsave.dungeonposy] != 5)
{
   for (int i = 0; i < rand.Next(1, 5); i++)
   {
       switch (rand.Next(5))
       {
          //잡몹 생성하기
       }
   }
}
else if (Forsave.dungeon[Forsave.dungeonposx, Forsave.dungeonposy] == 5)
   spawnlist.Add(new UncontrollableBug()); //보스만 생성하기

보스 전투에서 승리 시 던전이 끝나야 하는데 어떻게 구현할 것인가.
던전이 끝나는 씬으로 분리하고 싶지 않아서 기존 사용하던 Battle_result를 사용하고 싶었다.

문제 : 보스몬스터와의 전투인지 어떻게 알 것인가.
졌을 때의 조건은 player.IsDead = true라 차치하고, 이겼을 때 잡은 몬스터가 보스몬스터라면 던전 클리어!, 일반 몬스터라면 전투 승리!를 해줘야된다.
그래서 시도한 방법이

Indexof & Find

이전 개인 과제를 할 때, 인벤토리에 아이템이 있는 지 탐색할 때 사용한 방법이다.
값이 있으면 그 인덱스를 반환하고, 없으면 -1을 반환한다.

spawnlist.IndexOf(UncontrollableBug);

근데 이렇게 작성하니까 유효하지 않은 컨텍스트라 안된다하고, 앞에 new를 붙이니까 다른 친구를 찾는거라 보스를 잡아도 안 잡은 취급을 해서 폐기했다.
Find도 써봤는데 비슷한 오류가 생겨서 이 역시 폐기했다.

OfType

(출처 : Devstory)
특정 값을 출력하는 방법이라고 해서 바로 써봤었는데, 예시처럼 하려고 해서 문제였던 것 같다.

List<Monster> moblist = new List<Monster>();
moblist.Add(spawnlist.OfType<보스몬스터>;

문제 해결

그냥 보스몬스터의 클래스에 있는 TakeDamage()에 던전클리어 시 사용할 bool을 하나 추가해주고, 보스.isDead = true 일 때, true로 바꿔주는 방식으로 해서 구분했다.

보스몬스터의 TakeDamage()를 바꿔주기 위해서, 부모 클래스의 메서드를 가상메서드로 바꿔주고
override 했다.

팀원분이 좋은 방법을 알려주셨다. (출처 : 마소 공식)

(spawnlist[0] is 보스몬스터) //bool을 반환함

보스몬스터는 1마리만 나오니까 인덱스는 항상 0이며, is로 형식을 비교했을 때
'보스 몬스터의 클래스와 같으면' true를 반환한다.
이 방식으로 작성할 경우, 부모 클래스의 가상 메서드를 원래대로 돌려도 무관하다.

해결 사진

정리

시도도 많고 탈도 많았지만 만들어보고 싶은 것들 만들어봐서 재밌었다.
다양한 방식으로 시도하다보니 뭐가 되는지 안되는지도 알 수 있고, 어떤게 더 효율적일까? 하는 생각도 든다.

내일 할 일

알고리즘 코드카타
팀 프로젝트

병합하기
던전 밸런스 잡기
아이템 작업하기
레벨업 작업하기
보상 추가하기

튜터님 피드백 공부해보기 (천천히 하는건 괜찮음. 안하지 말 것)

속보- 작성하다 퇴실 놓침

guno park

이전 포스트

01/09 본캠프#11

다음 포스트