[멋쟁이사자처럼 부트캠프 TIL 회고] Unity 게임 개발 3기 16일차

 

목차

---

알고리즘

알고리즘이란?

: 프로그래밍에서 문제를 해결하기 위한 단계적인 절차나 방법

>> 효율적인 알고리즘은 프로그램의 성능을 크게 향상시키고, 복잡한 문제를 해결하는데 필수적이다.

 

특징

• 입력 : 하나 이상의 입력을 받는다.
• 출력 : 하나 이상의 결과를 생성한다.
• 명확성 : 각 단계는 모호하지 않고 명확해야 한다.
• 유한성 : 유한한 수의 단계 후에 반드시 종료되어야 한다.
• 효율성 : 가능한 한 효율적으로 설계되어야 한다.

종류

• 정렬 알고리즘 : 버블 정렬, 퀵 정렬, 병합 정렬 등 --> 사실상 퀵 정렬만 알고 있어도 된다. 나머지는 대기업 면접 대비
• 검색 알고리즘 : 선형 검색, 이진 검색 등
• 그래프 알고리즘 : 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 다익스트라 알고리즘 등
• 동적 프로그래밍 : 최적화 문제를 해결하는 데 사용되는 기법
• 분할 정복 알고리즘 : 문제를 작은 부분으로 나누어 해결하는 방식
• 그리디 알고리즘 : 각 단계에서 최적의 선택을 하는 방식

버블 정렬 (Bubble Sort)

: 인접한 두 원소를 비교하여 정렬하는 간단한 알고리즘

public void BubbleSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
            }
        }
    }
}

※ 이해를 위한 영상

https://www.youtube.com/watch?v=Iv3vgjM8Pv4

퀵 정렬 (Quick Sort)

: 분할 정복 방법을 통해 정렬하는 알고리즘

 

>> 퀵 정렬의 핵심은 어떻게 pivot을 선정하는가? --> 최악의 경우 O(N²) 시간복잡도

• 첫번째 값이나 마지막 값을 pivot으로 선정한다.
• 첫번째 값, 가운데 값, 마지막 값 중에 중간 값을 pivot으로 선정한다. (Median of Three)
• 무작위 값을 pivot으로 선정한다.

※ Median of Three를 사용하면 배열의 분할이 거의 이등분으로 유지가 될 가능성이 높기 때문에 이 방법이 가장 좋은 pivot 선정법으로 알려져있다.

 

>> 마지막 값을 pivot으로 선정한 방식 (수업) --> 내 기준, 이해가 어려움

public void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        int pi = Partition(arr, low, high);
        QuickSort(arr, low, pi - 1);
        QuickSort(arr, pi + 1, high);
    }
}

private int Partition(int[] arr, int low, int high)
{
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j < high; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            (arr[i], arr[j]) = (arr[j], arr[i]);
        }
    }

    (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
    return i + 1;
}

void Start()
{
    int[] arr = { 3, 5, 6, 9, 1, 2, 4, 11, 7 };
    QuickSort(arr, 0, arr.Length - 1);
    
    for (var i = 0; i < arr.Length; i++)
    {
        Debug.Log(arr[i]);
    }
}

 

>> 첫번째 값을 pivot으로 선정한 방식 --> 퀵 정렬의 원리와 과정을 이해하기 가장 용이한 방법

private int MyPartition(int[] arr, int l, int h)
{
    int pivot = arr[l]; // pivot 값 설정
    int low = (l + 1); // low는 pivot의 바로 다음 위치
    int high = h;

    while (low <= high)
    {
        while (arr[low] < pivot) low++; // pivot보다 큰 값이 나올 때까지 이동
        while (arr[high] > pivot) high--; // pivot보다 작은 값이 나올 때까지 이동
        
        if (low <= high) // low와 h가 멈춘 지점이 서로 역전되지 않았다면
            (arr[low], arr[high]) = (arr[high], arr[low]); // low와 high의 값 변경
            // 이후 다시 low와 high 이동
    }

    (arr[l], arr[high]) = (arr[high], arr[l]); // pivot과 high 위치 교환

    return high; // pivot 위치 반환
}

public void MyQuickSort(int[] arr, int l, int h)
{
    if (l < h)
    {
        int pi = MyPartition(arr, l, h);
        MyQuickSort(arr, l, pi - 1);
        MyQuickSort(arr, pi + 1, h);
    }
}

void Start()
{
    int[] arr = { 3, 5, 6, 9, 1, 2, 4, 11, 7 };
    MyQuickSort(arr, 0, arr.Length - 1);
    
    for (var i = 0; i < arr.Length; i++)
    {
        Debug.Log(arr[i]);
    }
}

※ 이해를 위한 영상

https://youtu.be/3San3uKKHgg?si=iMaIy8lTBtizYI80

└ Quick Sort를 Unity로 Visualize (Quest)

: 중급자 이상이 되면 누구나 할 수 있다. --> 나중에 구현해보자

 

>> 정답 코드

// Bar.cs
using System.Collections;
using System.Collections.Generic;
using TMPro;
using UnityEngine;

public class Bar : MonoBehaviour
{
    public int _data;
    public bool bResizeFinish;
    
    public TextMeshPro _text;
    public GameObject _stick;

    void Start()
    {
        _text.text = _data.ToString();
    }
    
    public void SetData(int index)
    {
        StartCoroutine(Lerp(index));
    }

    IEnumerator Lerp(int index)
    {
        bResizeFinish = false;
        
        float t = 0.0f;
        float duration = 0.3f;
        while (true)
        {
            t += Time.deltaTime;
            if (t >= duration)
            {
                break;
            }
            
            _stick.transform.position = Vector3.Lerp(_stick.transform.position, new Vector3(index, _data / 2.0f, 0), t / duration);
            _stick.transform.localScale = Vector3.Lerp(_stick.transform.localScale, new Vector3(1,_data, 1), t / duration);

            _text.transform.position = _stick.transform.position + new Vector3(0,0,-3.0f);;
            yield return null;
        }
        
        _stick.transform.position = new Vector3(index, _data / 2.0f, 0);
        _stick.transform.localScale = new Vector3(1,_data, 1);
        _text.transform.position = _stick.transform.position + new Vector3(0,0,-3.0f);
        
        bResizeFinish = true;
    }
}

※ t / duration --> 0.3초 동안만 보간을 한다는 의미

※ Lerp

https://iygames.tistory.com/6

[Unity] 유니티 3D Vector의 선형보간 Lerp 정확한 사용법

// QuickSort.cs
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

public class QuickSort : MonoBehaviour
{
    public Material swapMaterial;
    public Material pivotMaterial;
    public Material normalMaterial;
    
    public Bar barPrefab;
    
    private int pi = 0;
    
    private IEnumerator Partition(Bar[] arr, int low, int high)
    {
        int pivot = arr[high]._data; 
        int i = (low - 1);

        for (int j = low; j < high; j++)
        {
            if (arr[j]._data < pivot)
            {
                i++;
           
                (arr[i], arr[j]) = (arr[j], arr[i]);
                arr[j].SetData(j);
                arr[i].SetData(i);
                arr[j]._stick.GetComponent<MeshRenderer>().material = swapMaterial;
                arr[i]._stick.GetComponent<MeshRenderer>().material = swapMaterial;

                var i1 = i;
                var j1 = j;
                yield return new WaitUntil(() => arr[i1].bResizeFinish && arr[j1].bResizeFinish);
                
                arr[j]._stick.GetComponent<MeshRenderer>().material = normalMaterial;
                arr[i]._stick.GetComponent<MeshRenderer>().material = normalMaterial;
            }
        }
        
        (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
        arr[i + 1].SetData(i + 1);
        arr[high].SetData(high);
        arr[i + 1]._stick.GetComponent<MeshRenderer>().material = swapMaterial;
        arr[high]._stick.GetComponent<MeshRenderer>().material = swapMaterial;

        yield return new WaitUntil(() => arr[i + 1].bResizeFinish && arr[high].bResizeFinish);

        arr[i + 1]._stick.GetComponent<MeshRenderer>().material = normalMaterial;
        arr[high]._stick.GetComponent<MeshRenderer>().material = normalMaterial;
        
        arr[pi]._stick.GetComponent<MeshRenderer>().material = normalMaterial;
        pi = i + 1;
        arr[pi]._stick.GetComponent<MeshRenderer>().material = pivotMaterial;
    }
    
    public IEnumerator QuickSort(Bar[] arr, int low, int high)
    {
        if (low < high)
        {
            yield return StartCoroutine(Partition(arr, low, high));
            yield return StartCoroutine(QuickSort(arr, low, pi - 1));
            yield return StartCoroutine(QuickSort(arr, pi + 1, high));
        }
    }

    void Start()
    {
        int[] arr = { 3, 5, 6, 9, 1, 2, 4, 11, 7 };
        
        Bar[] instanceArr = new Bar[arr.Length];
        for (var i = 0; i < arr.Length; i++)
        {
            instanceArr[i] = Instantiate(barPrefab, transform);
            instanceArr[i].SetData(i);
            instanceArr[i]._data = arr[i];
        }
        
        StartCoroutine(QuickSort(instanceArr, 0, arr.Length - 1));
        foreach (var i in instanceArr)
        {
            Debug.Log(i._data);    
        }
    }
}

Text(TMP)

A* (A Star Algorithm) (Quest)

: 최단 경로를 찾는 데 사용되는 그래프 탐색 알고리즘

>> 찾은 경로는 추측값이 섞여있기 때문에 항상 최선은 아니다.

※ 참고 사이트

https://www.redblobgames.com/pathfinding/a-star/introduction.html

 

※ 중, 고급자용 과제 : AStar로 pathfindingdmf 구현하고 실시간으로 장애물을 뒀을 때, 그곳을 피해서 이동하라 --> 나중에 구현 해보자

---

Unity로 별 찍기

: 초급자용 과제

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class StarExample : MonoBehaviour
{
    public GameObject cube;

    void Start()
    {
        // *****
        //  ***
        //   *
        
        //for (int i = 0; i < 3; i++)
        //{
        //    string star = "";
        //    for (int j = 0; j < 5 - i; j++)
        //    {
        //        if (j >= i)
        //        {
        //            Instantiate(cube, new Vector3(j, -i, 0), Quaternion.identity);
        //        }
        //    }
        //    Debug.Log(star);
        //}
        
        // *****
        // ***
        // *
        // ***
        // *****

        int addtive = 0;
        
        for (int y = 0; y < 5; y++)
        {
            for (int x = 0; x < 5 + addtive; x++)
            {
                Instantiate(cube, new Vector3(x, -y, 0), Quaternion.identity);
            }

            if (y < 2)
                addtive -= 2;
            else
                addtive += 2;
        }
    }
}

Array를 이용하여 3Match 게임 만들기 (Quest)

: 초, 중급자용 --> 나중에 구현 해보자