알고리즘 특강 1일차

알고리즘이란?

특정 문제를 해결하기 위해 기술한 일련의 명령문

• 프로그램
  알고리즘을 컴퓨터가 이해하고 실행할 수 있는 특정 프로그래밍 언어로 표현한 것
  Program = algorithm + data structures

• 알고리즘의 요건
  완전성과 명확성
  수행 단계와 순서사 완전하고 명확하게 명세되어야 함
  순수하게 알고리즘이 지시하는 대로 실행하기만 하면 의도한 결과가 얻어져야 함

  입력과 출력
  입력 : 알고리즘이 처리해아 할 대상으로 제공되는 데이터
  출력 : 입력 데이터를 처리하여 얻은 결과

  유한성
  유한한 단계 뒤에는 반드시 종료

• 알고리즘을 해야하는 이유
  코딩에서 알고리즘은 기초 체력과 비슷하다.
  단기간 안에 실력이 필요한 나에게 꼭 필요하다.

Q.
배열 A=[3,4,5,6,7,8,9]에서 숫자 8이 있는 지 찾아보시오
s1.
순차적으로 하나씩 검사 6번
s2.
배열 A가 순서대로 정렬되어있으니 중간값을 기준으로 대소 비교 2번
같은 동작을 하더라도 어떤 방식으로 하느냐에 따라 효율이 다르다.

• 배열
  동일한 데이터 유형을 가지는 데이터 요소들을 한 번에 모아서 다룰 수 있는 구조

• 배열의 특성
  순차적 메모리 할당 방식

  <인덱스, 원소>쌍의 집합 - 각 쌍은 인덱스와 그와 연관된 원소값의 대응 관계를 나타냄

  원소들이 모두 같은 타입, 같은 크기

  배열을 이용하면 많은 수의 변수를 하나의 문장으로 선언 가능

  배열을 구성하는 변수에 순차적으로 접근 가능

  배열 인스턴스의 멤버변수 length에는 배열의 길이 정보가 저장되어 있다.

• 인덱스
  순서를 나타내는 원소의 유한 집합

  배열 네에서 원소의 상대적인 위치를 나타냄

  인덱스만으로 원하는 원소에 직접 접근이 가능

• 배열의 종류
  1차원 배열 : int[] arr; arr =[1,2,3];
  2차원 배열 : int[,] arr; arr{[1,2,3],[4,5,6]}
  가변 배열 : int[][] arr; arr[0] =[1,2,3], arr[1] = [4,5,6]

2차원 배열은 배열의 길이가 모든 배열들을 한줄로 세운 길이가 나옴 ex)3,3 length는 9
가변배열은 가로길이 하나하나가 다 1차원배열로 인식함 (배열의 배열)

• 리스트
  동적으로 크기를 조절할 수 있는 배열

  할당한 크기가 넘어가는 경우 2배의 크기로 재할당

• 할당이 가능한 이유
  크기를 미리 잡아놓으면 그 두배만큼 미리 자리를 잡아놓아서 가능함
  할당한 크기가 넘어가는 경우 2배의 크기로 재할당함.
  리스트가 무조건 배열보다 좋은 건 아님.

  리스트라고 해도 초기에 크기는 잡고 가는게 좋음.
  최대 몇개정도라고 생각하고 그정도 크기 잡고가면 나중에 재할당은 발생하지 않음

알고리즘 뜯어보기

• 연결리스트
  각 노드가 데이터와 포인터를 가지고 있으면서 노드들이 한 줄로 쭉 연결되어 있는 방식
  데이터 필드 - 리스트의 원소, 즉 데이터 값을 저장하는 장소
  링크 필드
  예외 처리는 무조건 해줘야됨

이중연결리스트

• 하나의 노드가 데이터, 왼쪽링크, 오른쪽 링크 필드를 가짐
• 양방향으로 탐색이 가능해서 선행 노드를 검색하기가 쉬움.

따라 적느라 필기를 잘 못했다. 제네릭에 링크드리스트는 이미 있지만, 알고리즘은 그냥 아는 것 보다 어떤 식으로 되어있는지 이해하는 게 중요함.

내일은 스택큐,정렬, 탐색,순환 이런거 예시들면서 알려준다고함. 오늘은 여기까지

팀 프로젝트 - Text RPG 만들기

지난 과제의 연장선으로 생각하면 되지만, 팀프로젝트인만큼 처음 보는 것들이 잔뜩 나왔다.

게임 루프에 대해서

(출처 : 호진님이 만들어준 가이드)
게임 루프란 게임 프로그램의 전체적인 흐름을 말합니다.

기본적으로 대부분의 게임들은 다음과 같은 흐름을 따릅니다.

• StartUp : 초기화 과정입니다. 플레이어 정보 불러오기, 맵 불러오기 등 현재 사용할 데이터들을 불러오는 과정입니다.

• Update : update는 크게 두 과정으로 나뉩니다. 플레이어의 입력을 받는 부분과 그 입력에 따라 처리하는 부분으로 나뉩니다.

• Render : render는 플레이어의 입력에 따라 바뀐 화면을 그리는 과정입니다.

• Shutdown : 게임의 종료입니다.

Unity에서도 동일합니다.

Unity로 만든 게임을 실행시키면, 시작씬을 로드하고, 그 Scene에 하이어라키에 있는 게임 오브젝트들을 생성하고 초기화합니다(Awake 및 Start).

그 다음 이제 Update를 수행하기 시작합니다.

유니티에서는 Update가 알아서 돌아가고 있어서 직접 이렇게 할 필요는 없지만, 알고리즘도 그렇듯 어떻게 돌아가는 지 알아두자.

예시

internal class Program
{
    static void Main(string[] args)
    {
        Game game = new Game();
        game.Start();
    }
}

public class Game
{
    public static Game game;
    Scene curScene;

    public Player player { get; private set; }

    public Game()
    {
        game = this;
    }

    public void Start()
    {
        Init();
        Loop();
    }

    void Init()
    {
        player = new Player();
        curScene = new Idle();
    }

    void Loop()
    {
        while (true)
        {
            bool exit = false;
            curScene.Render();

            Console.WriteLine();
            Console.WriteLine("원하시는 행동을 선택해주세요.");
            Console.Write(">> ");

            int input = -1;

						// 입력 부분은 살짝 수정 필요
						// 입력 이후 바로 행동하지 않음
            while (int.TryParse(Console.ReadLine(), out input))
            {
                if (input == 'q') {
                    exit = true;
                    break;
                }
                Console.Clear();
                curScene.Update(input);
            }

            if (exit) break;
        }
    }

    public void ChangeScene(Scene scene)
    {
        this.curScene = scene;
    }
}

public abstract class Scene
{
    public abstract void Render();
    public abstract void Update(int act);
}

Program, Game, Scene 이 세 개의 클래스에 주목해주시길 바랍니다.

Program은 프로그램의 시작점입니다.

Game은 게임 루프의 시작점이자, Unity에서 GameManager이자 SceneManager 역할을 할 클래스입니다.

Scene은 게임 흐름의 단위로, Unity의 Scene과 유사합니다.

Program이 Game을 초기화하고, Game은 루프를 돌기 시작합니다. 초기화 할 때에 지정된 첫번째 Scene에 들어가, 그 Scene에 대해서 Render(여기에서는 ShowInfo)와 Input, Update (동일하게 Update)를 반복합니다.

Render() → Input → Update(input) → Render() → Input → Update(input) → ∞
변경이 있을때마다 Render가 동작하여 새로운 화면을 그려줌

Scene에서 다른 Scene으로 바꾸고 싶은 경우 Game 클래스의 ChangeScene을 이용합니다.

Scene 분리의 장점

독립적입니다. 현재 씬에 사용할 데이터만 들고 있기 때문에 코드를 여러 파일로 분할하기 좋습니다.
다른 씬과 변수 이름의 중복이 있어도 안전하며, 외부의 데이터를 침범할 여지를 줄여줍니다.
중복이 줄어들고, 프로그램의 흐름을 관리하기 편합니다.

Scene 분리의 단점

다른 객체의 데이터를 참조 할 때에 해당 데이터를 참조하기 위한 인터페이스를 추가로 구현해야 합니다. 예를 들어, Battle 씬에서 플레이어의 레벨이 올랐을 경우 player.level++ 이 아닌 player.LevelUp()을 수행해야 합니다.
(물론 player를 public set으로 설정한 경우 player.level++도 가능합니다.)

씬을 매번 생성하기 때문에 씬의 변경 사항을 기억해야 하는 경우 그 데이터를 파일에 저장하고 불러와야 합니다.
Game 클래스에 모든 씬을 생성해두고, ChangeScene에 해당 씬을 넘겨주면 되긴 합니다만, 게임이 종료되었을 때 까지 보존되지는 않습니다.
일반적으로 씬의 데이터도 파일에 저장하고 불러올 것을 권장합니다.

씬으로 분리가 어려운 경우

씬으로 분리가 어려운 경우, 즉, 다른 화면을 표시해주고, 다른 입력을 받아야 하는 경우에 이러한 상황이 발생합니다.

이 경우에는 씬 내에 또 다른 게임 루프를 만든다고 생각하면 됩니다.

정리

1. 유니티 동작 구조와 비슷하며, 여느 게임 구조와도 비슷하기에 동작하는 방식을 이해해보자.
2. 씬으로 사용 할 시 가독성을 높일 수 있으며, 데이터 관리가 수월하다.
3. 단점이라고 적힌 것 중에 딱히 단점을 못 느꼈다. 아직 데이터 저장까지 안 해서 그런가보다.

총평 : 정말 좋은 글인 것 같아서 통째로 긁었다. 새 프로젝트 시작 전에 한번씩 보고 시작하자

오늘 작업한 것

1. 전투 씬 구성
2. 치명타 기능
3. 회피 기능

전투 씬 구성

1. 몬스터 클래스를 상속하는 3가지 몬스터를 만듬 (대포미니언, 미니언, 공허충)
2. Battle : Scene 이라는 큰 틀을 만들고, 그 안에서 여러 함수와 클래스로 동작하게 만듬.
   ※루프 도는 것까지 신경써서 다듬어 볼 것
3. 만들어져 있는 메인 cs와 연결하여 잘 구동하는 지 확인함.

• 대락적인 구성도
  

치명타 기능

치명타 기능은 Random 클래스를 활용해서 Random.Next(100) >85 이상일 때 발생하도록 if와 else로 구획을 나뉘어 작성하였다.
작성하는데 특이사항으로는 공격력 자체가 10%의 오차를 가져야하며, 오차가 소수점이라면 올림 처리를 해야한다는 것, 그리고 치명타 배율이 160%인 것이다.

데미지 = 공격력1.1 or 공격력0.9
치명타 데미지 = 데미지*1.6

이렇게 되어있어서 Mathf.Ceiling 기능을 사용해서 작성하였다.

회피 기능

원래는 엄청 복잡하게 공격 실패, 회피 기능을 구현하고 싶었는데 (D&D처럼) 그렇게 하려면 플레이어 클래스에 멤버변수를 4개 정도 집어 넣어야되는데, 이걸 다른 요구사항에서 쓰느냐하면 그것도 아니라서 명중률, 회피율만 넣었다.

20D 기준으로 생각해서

명중률+D20(Random.Next(20)) > 적회피율+D20 ? Hit : Miss;

이런 느낌으로 작성했다.

다른 솔루션에 임의로 명중 확률 계산기를 만들어서 돌려봤는데

플레이어 명중치 10, 미니언 회피치 5로 설정하고 1000번 돌려보니까 7:3 정도 나온다.

정리

오늘 작업한 것 중에는 문법적으로 어려운 내용은 없었다. 했었던 것들 다시 하는 느낌이라.
기초적인 걸 몰라서 좀 헷갈렸다.
1. 클래스안에서 함수 호출은 그냥은 안된다.
2. 맨 처음에 만들 때는 클래스랑 메서드를 다 분리해서 만들었다.
이렇게 하니까 계속 Random도 선언해줘야되고, 몬스터 리스트도 계속 만들어야되서 팀원들에게 질문드리니까 바깥 큰 틀을 만들고 그 바로 밑에 계속 들고갈 데이터들을 선언해주면 된다고했다.
그렇게 하고나니까 지난 포스팅에도 비슷하게 한 게 있다는 기억이 났다.

오늘도 많이 배웠는데 다 못 담은 것 같다.