로그인 인증 기능 구현

SDK 설치 유니티에 인증 기능 설치 *Imports, Plugins, json 파일 Ignore 설정

Firebase에 인증 기능 추가 - 시작하기

이메일/비밀번호 로그인 추가

[FirebaseManager] Firebase초기화 코드 사용 https://firebase.google.com/docs/unity/setup?authuser=0&hl=ko&_gl=1*qocjdp*_up*MQ..*_ga*NjE5NTUwODA4LjE3MTQ0NzIzMjk.*_ga_CW55HF8NVT*MTcxNDYxMDQ4OS40LjEuMTcxNDYxMDQ5NS41NC4wLjA.

using Firebase;
using Firebase.Auth;
using Firebase.Extensions;
using UnityEngine;

public class FirebaseManager : MonoBehaviour
{
    private static FirebaseManager instance;
    public static FirebaseManager Instance { get { return instance; } }

    private static FirebaseApp app;
    public static FirebaseApp App { get { return app; } }

    private static FirebaseAuth auth;
    public static FirebaseAuth Auth { get { return auth; } }

    private void Awake()
    {
        CreateInstance();
        CheckFirebaseAvailable();
    }

    private void CheckFirebaseAvailable() //Firebase 초기화 코드 (서비스 사용 가능한지 확인)
    {
        Firebase.FirebaseApp.CheckAndFixDependenciesAsync().ContinueWithOnMainThread(task => {
            var dependencyStatus = task.Result;
            if (dependencyStatus == Firebase.DependencyStatus.Available)
            {
                // Create and hold a reference to your FirebaseApp,
                // where app is a Firebase.FirebaseApp property of your application class.
                app = FirebaseApp.DefaultInstance;
                auth = FirebaseAuth.DefaultInstance;
                Debug.Log("Success");
                // Set a flag here to indicate whether Firebase is ready to use by your app.
            }
            else
            {
                UnityEngine.Debug.LogError(System.String.Format(
                  "Could not resolve all Firebase dependencies: {0}", dependencyStatus));
                // Firebase Unity SDK is not safe to use here.
                app = null;
                auth = null;
            }
        });
    }



    private void CreateInstance() //싱글톤
    {
        if(instance == null)
        {
            instance = this;
            DontDestroyOnLoad(gameObject);
        }
        else
        {
            Destroy(gameObject);
        }
    }
}

디버그로 동작 확인 [로그인 / 회원가입] 로그인/회원가입 코드 사용 https://firebase.google.com/docs/auth/unity/start?hl=ko&authuser=0&_gl=1*kys2yi*_up*MQ..*_ga*NjE5NTUwODA4LjE3MTQ0NzIzMjk.*_ga_CW55HF8NVT*MTcxNDYxMDQ4OS40LjEuMTcxNDYxMDQ5NS41NC4wLjA.

using System.Collections;
using System.Collections.Generic;
using TMPro;
using UnityEngine;
using UnityEngine.UI;

public class LoginPanel : MonoBehaviour
{
    [SerializeField] TMP_InputField idInputField;
    [SerializeField] TMP_InputField passInputField;

    [SerializeField] Button loginButton;
    [SerializeField] Button signUpButton;

    private void Awake()
    {
        loginButton.onClick.AddListener(Login);
        signUpButton.onClick.AddListener(SignUp);
    }

    public void Login() //Firebase 로그인 코드
    {
        string email = idInputField.text;
        string password = passInputField.text;

        FirebaseManager.Auth.SignInWithEmailAndPasswordAsync(email, password).ContinueWith(task => 
        {
            if (task.IsCanceled)
            {
                Debug.LogError("SignInWithEmailAndPasswordAsync was canceled.");
                return;
            }
            if (task.IsFaulted)
            {
                Debug.LogError(task.Exception.Message);
                return;
            }

            Firebase.Auth.AuthResult result = task.Result;
            Debug.LogFormat("User signed in successfully: {0} ({1})",
                result.User.DisplayName, result.User.UserId);
        });
    }

    public void SignUp() //Firebase 회원가입 코드
    {
        string email = idInputField.text;
        string password = passInputField.text;

        FirebaseManager.Auth.CreateUserWithEmailAndPasswordAsync(email, password).ContinueWith(task => {
            if (task.IsCanceled)
            {
                Debug.LogError("CreateUserWithEmailAndPasswordAsync was canceled.");
                return;
            }
            if (task.IsFaulted)
            {
                Debug.LogError(task.Exception.Message);
                return;
            }

            // Firebase user has been created.
            Firebase.Auth.AuthResult result = task.Result;
            Debug.LogFormat("Firebase user created successfully: {0} ({1})",
                result.User.DisplayName, result.User.UserId);
        });
    }
}

회원가입 시 Firebase에 해당 아이디 추가 (Unity)

로그인 동작 확인

셰이더 그래프(Shader graph)

Lit Shader graph 생성

좌측에 변수를 생성해 Fragment와 연결하면 인스펙터 창에 출력되어 입력이 가능하게 된다. (인스펙터창에 기능이 추가된 모습) 레퍼런스 이름으로 컬러 찾기

 [SerializeField] Renderer renderer;

 public Color color;

 void Start()
 {
     //color = renderer.material.GetColor("_BaseColor");
     //renderer.material.SetColor("_BaseColor",color);
 }

Play 했을 때

color = renderer.material.GetColor("_BaseColor");

*결과

셰이더 컬러를 가져온다. renderer.material.SetColor("_BaseColor",color);

*결과

스크립트 컬러를 셰이더에 적용한다. 이 때, RGBA값을 RGB만 지닌 BaseColor에 입력하기 때문에 A값이 생략된다. 변수 BaseColor를 Split으로 RGBA로 나눈 뒤 RGB는 Combine으로 다시 결합하여, 각각 Fragment의 Alpha와 BaseColor로 연결한다. 이로써 인스펙터에서 A값도 조절이 가능해진다.

오브젝트기준의 Position과 변수 Position을 Add로 결합하며 Vertex Position에 연결하면, 변수의 값에 따라 셰이더 위치가 변경된다.

x값에 +1했을 때 셰이더만 위치를 이동한 모습

이번엔 노멀벡터 방향을 value 값을 곱하고 오브젝트기준 위치에 더해준 경우다. value 값을 증가시키면,

노멀벡터 방향으로 value값만큼 셰이더가 이동한다.

윤곽선

이전에 만든 그래프를 그대로 활용해서 윤곽선 표현하기(굴곡이 없는 직각오브젝트는 부적합) value를 윤곽선의 두께로 사용 그래프를 적용한 셰이더를 대상 오브젝트에 추가 렌더러를 후면만 그려지게 했을 때, 다음처럼 value 값에 비례하는 두께를 가진 윤곽선이 표현된다. *다른 모델 적용

등장효과

새롭게 Shader graph 생성하고 Texture2D변수를 Sample Textyre 2D를 거치며 컬러로 변환하여 Fragment에 연결한다. Metallic과 Emission도 같은 방식으로 적용할 수 있다. Alpha Clipping을 체크해주면 Fragment에 Alpha와 Alpha Clip Threshold가 추가되는데, Alpha값이 Alpha Clip Threshold 설정 값보다 크면 그려주고, 낮으면 그리지 않는 방식이다.

Position에서 Split으로 Y값만 가져오고 Step에 연결한다. Step은 Value를 기준으로 보다 높으면 0, 낮으면 1로 양분해 주는 노드이다. 이 Step을 Alpha에 연결해준다.

이제 Value값을 높이거나 줄이면 다음 같은 표현이 가능하다.

포스트 프로세싱

Global Volume: 씬 전체 적용 그 외: 해당 범위 안에서만 적용 Weight: 씬에 미치는 영향의 정도 Priority: 여러 볼륨이 씬에 영향을 미칠 때 이 값을 사용하여 어느 볼륨을 사용할지 우선순위 결정

1. 새 볼륨 프로파일을 생성하고 Volume 컴포넌트에 Add Override 버튼을 추가
2. Add Override를 클릭, Volume Overrides 다이얼로그에서 포스트 프로세싱 효과를 선택

ex)자주 활용하는 효과 Bloom: 섬광 같은 밝은 광원에서 나오는 빛이 주변 오브젝트로 새어 들어가는 것처럼 보이는 광학 효과 Vignette: 이미지 모서리를 어둡게 Motion Blur: 카메라에 의해 촬영되는 오브젝트가 빠르게 움직일 때 블러링 효과 Depth Of Field: 피사계심도 https://docs.unity3d.com/Packages/com.unity.render-pipelines.universal@12.0/manual/post-processing-depth-of-field.html

카메라에 포스트세싱을 체크해야 적용

카메라

카메라 범위 조절 (카메라 2개로 화면을 나눠서 적용) *결과

*렌더 텍스처 *

캐릭터의 얼굴을 비추는 카메라를 추가하고 렌더텍스처를 만들어 Output에 참조 카메라 장면을 담을 RawImage를 추가하고 같은 렌더텍스처를 참조 *결과 이미지에 카메라 촬영장면을 띄운다

카메라 스태킹 베이스 카메라와 하나 이상의 오버레이 카메라로 구성된다. 카메라 스택은 베이스 카메라의 출력을 카메라 스택에 있는 모든 카메라의 결합된 출력으로 오버라이드한다.

1인칭 게임에서 메인카메라를 캐릭터의 눈 위치에 두었을 때, 1인칭 화면에 보여질 캐릭터의 손과 3인칭으로 플레이어를 볼 때의 손 위치에 괴리가 생긴다. 이 때, 손은 차렷 자세로 자연스럽게 둔 뒤 오버레이 카메라를 만들고 앞으로 뻗은 손만 촬영하여 병합출력한다.

*결과

렌더 피처스(Renderer Features)

사용할 URP에셋과 데이터를 새롭게 생성하고, 프로젝트셋팅에도 추가해 준다.

Depth URP Universal Renderer 생성 후 에셋에 추가하면 카메라에서 선택하여 사용

레이어마스크로 Player 제외가능

HidePlayer(플레이어 가려졌을 때) Depth Test: Greater Equal (깊이버퍼가 크거나 같을 때 그려준다.) ShowPlayer(가려지지 않은 플레이어)

*결과

Decal (조명, 그림자 등 사용) URP Universal Renderer 생성 후 렌더피처스 Decal 추가 에셋에 추가 머티리얼 생성 - 셰이더 Decal로 변경 - 그려질 이미지 선택 빈 오브젝트 생성후 URP Decal Projector컴포넌트 추가, 생성한 머티리얼 참조 *결과

Sten

URP Universal Renderer 생성 후 에셋에 추가 플레이어를 가리는 구체 생성 머티리얼 생성 - Transparent변경, 알파값 0

구체는 Stencil레이어, 플레이어를 가리는 큐브는 Block레이어 적용 Stencil레이어, Block레이어 제외

각 레이어별 렌더피처스 추가

-Stencil 알파값이 있으므로 Transparent Stencil레이어 오브젝트에 0을 1로 변경해서 유지한다.

-Block Block레이어 오브젝트가 0에 겹칠때 그려준다.

*결과

그래픽 최적화 체크

Batches(드로우콜) 값 최소화시키기 프레임디버거를 사용하면 실행 중인 게임을 특정 프레임에서 중지하고 해당 프레임을 렌더링하는 데 사용되는 개별 드로우 콜 을 볼 수 있다. 디버거는 드로우 콜의 리스트를 제공하고, 하나씩 단계별로 볼 수 있도록 하여 씬이 그래픽 요소에서 어떻게 구성되는지 자세하게 볼 수 있다. Window - analysis - profiler play했을 때 리소스가 사용되는 세부내용 을 확인할 수 있다.

정적 배칭

고정된 위치에 존재할 오브젝트는 부모의 자식으로 묶어두었을 때 정점셰이더의 계산을 줄일 수 있다. 이때, 움직이지 않을 오브젝트들은 Static을 체크하여 Play시에도 고정되도록 한다.

머티리얼

Public Render render;

void Start()
{
    render.material.color = Color.red; 
    //머티리얼의 복사본을 만들어 단일 적용, Play 종료 시 원본으로 복구
    render.sharedMaterial.color = Color.red; 
    //머티리얼의 원본을 변경하여 전체 오브젝트에 적용, Play 종료시 변경사항 유지
}

render.material.color = Color.red; 를 사용할수록 머티리얼이 생성되어 배치콜이 증가한다.

Public Render render;
Public Material nomalMat;
Public Material highLighyMat;

void Start()
{
    render.material = nomalMat; 
    render.material = highLighyMat; 
}

이런식으로 변경할 색상의 머티리얼을 미리 생성하여 사용하는게 최적화에 도움이 된다.

라이트매핑

라이트매핑은 씬의 표면 밝기를 미리 계산하고 계산 결과를 나중에 사용하기 위해 차트 또는 “라이트맵”에 저장하는 프로세스이다.

Mixed: Static인 오브젝트에 광원을 그려넣고 Static이 아닌 오브젝트에는 Realtime을 계속 적용한다. Baked: Static인 오브젝트에 광원을 그려넣는 기능만 사용하므로 Bake 이후 Light 오브젝트를 비활성화해도 무관하다.

Window - Rendering - Lighting

*결과

라이트 프로브(Light Probes)

Static인 큐브를 Bake했을 때 그려진 그림자에 다른 오브젝트가 진입해도 음영이 발생하지 않는다. Ctrl+D 로 원점 복사 빛의 변화가 큰 곳을 지정하여 Bake *결과

반사 프로브 (Reflection Probe)

범위를 지정하여 Bake 반사가 잘되도록 머티리얼을 조정하여 적용 *결과

오큘루전 컬링(Occlusion Culling)

카메라에 담기지 않는 Static오브젝트의 머티리얼을 비활성화 한다.

Window - Occlusion *결과

Level of Detail

카메라와의 거리에 따라 디테일 조절 LOD 컴포넌트를 추가하고 거리에 따라 변경할 모델을 각각 참조(프레임드랍 없다면 None → Cross Fade) *결과

카메라 Clipping Planes

카메라 시야범위 제한 +Fog를 사용하여 시야범위 제한을 자연스럽게 연출

유니버셜 렌더링 파이프라인(URP)

유니버설 렌더 파이프라인(URP)은 Unity에서 제작한 사전 빌드된 스크립터블 렌더 파이프라인이다. URP는 아티스트 친화적 워크플로를 통해 모바일, 고사양 콘솔, PC 등 다양한 플랫폼에서 최적화된 그래픽스를 쉽고 빠르게 구현할 수 있는 도구이다. 이전 URP 버전은 경량 렌더 파이프라인(LWRP)이라고 불렸고, URP는 LWRP를 대체한다.

빌트인 → URP 변경

UniversalRP - Install *URP 패키지 다운로드

Window - Rendering - Render Pipeline Converter

*빌트인 에셋 URP로 변경, URP 에셋 추가

인덱스 숫자(level)로 옵션 변경하기

public class Graphics : MonoBehaviour
{
    public void QualitySetting(int level)
    {
        QualitySettings.SetQualityLevel(level); //퀄리티 세팅 변경
        Debug.Log(QualitySettings.GetQualityLevel()); //퀄리티 세팅 읽기
    }

}

XR Origin 생성 → 양쪽 Controller에 Toolkit에서 제공하는 프리셋 적용 →양쪽 Controller에 모델 추가

Locomotion

XR → Locomotion System 추가 이동, 회전, 순간이동 기능에 사용 Locomotion이 입력을 받아 플레이어(Camera)에게 적용

Move 구현

Locomotion System 밑에 Move 오브젝트를 생성하고 Continuous Move Provider 스크립트를 추가, 프리셋 적용 후 Locomotion System 참조 Move Speed - 이동속도 조절 Enable Strafe - 좌우 이동 여부 Enable Fly - 공중 이동 여부 Use Gravity - 중력 적용 여부 Foward Soource - ex) Left Controller 참조 시 Controller 기준으로 이동 방향이 결정 된다.(None 일 때 카메라 방향) Hand Move Action - 어느 손, 어느 키에 적용할지 여부

Turn 구현

Turn 오브젝트를 생성하고 Continuous Turn Provider(점진적인 회전), Snap Turn Provider(순간적인 회전) 스크립트 추가(일반적으로 둘 중 하나만 사용), 프리셋 적용 후 Locomotion System 참조 Turn Speed - 회전 속도 Hand Turn Action - 어느 손, 어느 키에 적용할지 여부

Turn Amount - 회전 시 각도 Debounce Time - 회전 사이의 쿨타임 Enable Turn Left Right - 회전 가능 여부 Enable Turn Around - 180도 회전 (뒤돌기) 가능 여부 Delay Time - 회전 키 입력 시 Delay 후 동작

Interactor

Direct Interactor 구현(기능 구현을 위해 Controller의 겹치는 기존 스크립트 제거)

XR Direct Interator 스크립트 추가(Collider 컴포넌트 필요)

Interaction Layer Mask - 상호작용할 Layer 선정(VR 전용 Layer 존재) Select Action Trigger - State Change(누르는 동안 잡기), Toggle(누르면 잡기, 다시 누르면 놓기) Keep Selected Target Valid - 잡고 있을 때 텔레포트 쓸지? Hide Controller On Select - 잡고 있을 때 컨트롤러 숨기기 Allow Hovered Active - 잡고 있지 않은 오브젝트 트리거 Target Priority Mode - 잡는 우선순위(기본은 가까운 순서) Starting Selected Interactable - 시작할 때 잡고 있을 오브젝트 Events - 각 이벤트에 기능 추가

Ray Interactor 구현

XR - Ray Interactor 생성 Force Grab - 오브젝트 컨트롤러로 이동 Hit Direction Type - Ray 적용할 범위

Interactable

Interactor에 상호작용할 Interactable은 Rigidbody와 Collider가 필요하다.

Colliders - 충돌체 지정(없으면 자식 오브젝트 콜라이더 적용) Select Mode - 한손, 양손 잡기 Movement Type - 잡았을 때 움직임 유형 Throw On Detach - 던지기 가능 여부 Force Gravity On Detach - 상호작용 시 중력 적용 Attach Transform - 잡을 위치 Use Dynamic Attach - 아무 위치나 잡기

VR(VR디바이스 연결) - Install

VR Install할 때 InputSystem이 자동설치된다. (OpenXR Plugin 에 필요하기 때문) Xr Interaction Toolkit(VR/AR 기본적인 기능) - Install MainCamera 삭제 Hierachy 우클릭 - XR - XR Origin (XR Rig) 생성 *Enter Play Mode(선택 사항) 사용할 기기 체크(PC,안드로이드) PC 안드로이드 안드로이드로 플랫폼 변경 Starter Assets (기본기능 에셋), XR Device Simulator(PC에서 VR 기기 조작 테스트) Import XR Device Simulator 프리팹을 씬에 포함시키면 PC에서 VR기기 조작 가능(단, 실제 vr기기 사용 시엔 제외해야 한다.) XR Origin (XR Rig)을 삭제하고 Starter Assets에서 XR Interaction Setup프리팹을 추가해주면 기본 기능이 추가된 카메라를 사용할 수 있다.

[실제 XR기기 연결하기]

1.오큘러스 프로그램 설치 2.기기 연결 3.알 수 없는 출처 활성화 1.메뉴 - Oculus Link 2.기기 선택 후 연결 3.연결 완료

물리적 충돌을 위해 게임오브젝트의 모양을 정의하며 게임오브젝트의 표현인 메시와 똑같을 필요는 없다. 충돌체가 충돌상황에 있을 경우 유니티 충돌 메시지를 받아 상황을 확인한다.

public class UnityCollision : MonoBehaviour
{
    // <유니티 충돌 메시지>
    private void OnCollisionEnter(Collision collision)//충돌에 진입했을 때
    {
        Debug.Log("OnCollisionEnter");
    }

    private void OnCollisionStay(Collision collision)//충돌 중일 때
    {
        Debug.Log("OnCollisionStay");
    }

    private void OnCollisionExit(Collision collision)//충돌에서 벗어났을 때
    {
        Debug.Log("OnCollisionExit");
    }


    /************************************************************************
     * 트리거 충돌체
     * 
     * 하나의 충돌체가 충돌을 일으키지 않고 다른 충돌체의 공간에 들어가는 것을 감지
     * 트리거가 겹침상황에 있을 경우 유니티 트리거 메시지를 받아 상황을 확인
     ************************************************************************/

    // <유니티 트리거 메시지>
    private void OnTriggerEnter(Collider other)//충돌에 진입했을 때
    {
        Debug.Log("OnTriggerEnter");
    }

    private void OnTriggerStay(Collider other)//충돌 중일 때
    {
        Debug.Log("OnTriggerStay");
    }

    private void OnTriggerExit(Collider other)//충돌에서 벗어났을 때
    {
        Debug.Log("OnTriggerExit");
    }

    // <레이어기반 충돌 감지>
    // 게임오브젝트의 레이어를 활용하여 충돌체간의 충돌가능 여부를 설정 가능
    // edit -> ProjectSettings -> Physics 에서 설정 가능

    // <충돌체 종류>
    // (1) 정적 충돌체 (Static Collider)
    // Rigidbody가 없는 충돌체, 외부에 힘에 움직이지 않음
    // 절대로 움직이지 않는 지형, 구성요소에 주로 사용

    // (2) 리지드바디 충돌체 (Rigidbody Collider)
    // Rigidbody가 있는 충돌체, 외부에 힘을 받아 움직임
    // 충돌할 수 있으며 물리를 사용하는 게임 내 가장 흔히 사용되는 충돌체에 사용

    // (3) 키네마틱 충돌체 (Kinematic Collider)
    // Kinematic Rigidbody가 있는 충돌체, 외부의 힘에 반응하지 않음
    // 움직이지만 외부 충격에는 밀리지 않는 물체(밀어내는 장애물, 미닫이문 등)등 에 사용
    // kinematic 상태를 활성화/비활성화 하여 움직임 여부를 설정할 경우 사용


    // <충돌체 상호작용 매트릭스>
    // 편의상 정적충돌체(SC), 리지드바디충돌체(RC), 키네마틱충돌체(KC)로 표현
    // 편의상 정적트리거(ST), 리지드바디트리거(RT), 키네마틱트리거(KT)로 표현

    // 충돌시 충돌 메시지가 전송
    //        SC    RC    KC
    // SC         O    
    // RC     O     O     O
    // KC         O    

    // 충돌시 트리거 메시지가 전송
    //        SC    RC    KC    ST    RT    KT
    // SC                     O     O
    // RC                 O     O     O
    // KC                 O     O     O
    // ST         O     O         O     O
    // RT     O     O     O     O     O     O
    // KT     O     O     O     O     O     O
}

카메라(Camera)

게임월드를 플레이어에게 보여주는 장치로 하나의 씬에 카메라를 원하는 만큼 추가할 수 있다. 카메라가 렌더링하는 순서와 화면의 위치를 설정하며, 일부만 렌더링하도록 설정도 가능하다.

** <주요 속성>** Clear Flags : 화면의 그리지지 않은 부분을 비울 방법을 선택 Background : 스카이박스가 없을 경우 여백 화면에 적용할 색상 Culling Mask : 카메라가 렌더링할 오브젝트의 레이어 선택 Projection : 카메라의 원근감 설정 Perspective : 카메라의 원근감을 적용 Orthographic : 카메라의 원근감 없이 적용 Clipping Planes : 렌더링을 시작 및 중지하기 위한 카메라부터의 거리 Viewport Rect : 카메라 뷰가 드로우될 화면의 위치를 나타내는 사각형

<시네머신 패키지> 카메라의 촬영위치를 선정하기 위한 기능이 구현된 패키지 시네머신 브레인 : 카메라에 부착되어 있으며 가장 우선순위가 높은 시네머신(촬영장소)으로 당겨짐 시네머신 : 촬영장소이자 이동방법, 촬영대상, 기타 효과에 대해 정의

오디오 (Audio)

게임월드에서 플레이어에게 들려주는 청각적인 요소이다. 소리를 듣는 AudioListener 컴포넌트와 소리를 발생시키는 AudioSource 컴포넌트를 사용하고 소리들의 결과를 믹스, 효과적용 및 마스터링 작업하는 Audio Mixer가 있다.

<Audio Listener & Source> Audio Listener : 씬에서 주어진 오디오 소스로부터의 입력을 수신하여 사운드를 재생 주로 씬에서 카메라에 부착되어 있으며, 하나만 유지시킴 Audio Source : 씬에서 오디오 클립을 재생 오디오 클립을 재생하기 위한 다양한 오디오효과를 적용할 수 있음

<*Audio Mixer> 다양한 오디오 소스 믹스, 효과 적용 및 마스터링 작업진행 오디오의 그룹을 나누어 여러 효과를 적용하고 최종적으로 합치는 작업을 진행

public class UnityFunction : MonoBehaviour
{
    [Header ("This")]
    public GameObject thisGameObject;
    public string thisName;
    public bool thisActive;
    public string thisTag;
    public int thisLayer;

    [Header("GameObject")]
    public GameObject newGameObject;
    public GameObject destroyGameObject;
    public GameObject findWithName;
    public GameObject findWithTag;

    [Header("Component")]
    public Component newComponent;
    public Component addComponent;
    public Component destroyComponent;
    public Component getComponent;
    public Component findComponent;

    private void Start()
    {
        ThisFunction();
        GameObjectFunction();
        ComponentFunction();
    }

    private void ThisFunction()
    {
        //<현재 게임오브젝트 참조>
        //컴포넌트가 붙어있는 게임오브젝트는 Component에 구현한 gameObject 속성을 이용하여 접근가능
        thisGameObject = gameObject; //컴포넌트가 붙어있는 게임오브젝트
        thisName = gameObject.name; //게임오브젝트의 이름
        thisActive = gameObject.activeSelf; //게임오브젝트의 활성화 여부(activeInHierarchy : 게임씬에서 활성화여부)
        thisTag = gameObject.tag; //게임오브젝트의 태그 string
        thisLayer = gameObject.layer; //게임오브젝트의 레이어 int
    }

    private void GameObjectFunction()
    {
        //<게임오브젝트 생성>
        newGameObject = new GameObject("NewGameObject");

        //<게임오브젝트 삭제>
        if(destroyGameObject != null)
        {
            Destroy(destroyGameObject, 3f);//(삭제할 오브젝트, 지연삭제 시간)
        }

        //<게임오브젝트 탐색>update에선 사용x
        findWithName = GameObject.Find("MainCamera"); //이름으로 찾기
        findWithTag = GameObject.FindWithTag("MainCamera"); //태그로 찾기, 이름으로 찾기보다 효율적
    }

    private void ComponentFunction()
    {
        //<컴포넌트 추가>
        // newComponent = new Rigidbody();//의미없음, 컴포넌트는 게임오브젝트에 부착되어 동작할 때 의미있음
        addComponent = gameObject.AddComponent<Rigidbody>();

        //<컴포넌트 삭제>
        if(destroyComponent != null) 
        {
            Destroy(destroyComponent);
        }

        //<컴포넌트 탐색 - 같은 게임오브젝트에서 찾기>
        getComponent = gameObject.GetComponent<Collider>();

        //<컴포넌트 탐색 - 씬에서 찾기>
        findComponent = Component.FindObjectOfType<Camera>();
    }
}

프리팹(Prefab)

미리 만들어 놓은 게임오브젝트, 템플릿으로 프리팹 시스템을 이용하여 게임오브젝트를 생성, 설정 및 저장할 수 있다. 처음부터 씬에 존재하지 않던 게임오브젝트를 런타임 시점에 생성하려는 경우 사용한다.

<프리팹 생성> 유니티 하이어라키 창의 게임오브젝트를 프로젝트 창을 드래그 & 드롭하여 프리팹에셋을 생성

<프리팹 특징> -게임오브젝트를 프리팹화 시킨 프리팹에셋은 게임오브젝트의 모든 컴포넌트, 속성값, 자식 게임오브젝트를 가지고 있다. -프리팹에셋을 게임씬에 추가할 경우 프리팹인스턴스로 생성한다. -프리팹에셋의 변경사항은 프리팹인스턴스에게 자동으로 반영한다. -프리팹인스턴스에 변경사항이 있을 경우 해당 변경사항은 프리팹인스턴스에 영향을 받지 않는다 -프리팹에셋을 클래스, 프리팹인스턴스를 클래스의 인스턴스로 볼 수 있다.

유니티에서 사용자의 명령을 감지할 수 있는 수단으로 사용자는 외부 장치를 이용하여 게임을 제어할 수 있다. 유니티는 다양한 타입의 입력기기(키보드 및 마우스, 조이스틱, 터치스크린 등)를 지원한다.

      // <Device>
    // 특정한 장치를 기준으로 입력 감지
    // 특정한 장치의 입력을 감지하기 때문에 여러 플랫폼에 대응이 어려움
    private void InputByDevice()
    {
        // 키보드의 입력감지
        if (Input.GetKey(KeyCode.Space))//누르는 동안
            Debug.Log("Space key is pressing");
        if (Input.GetKeyDown(KeyCode.Space))//눌렀을 때
            Debug.Log("Space key is down");
        if (Input.GetKeyUp(KeyCode.Space))//눌렀다 땔 때
            Debug.Log("Space key is up");

        // 마우스의 입력감지
        if (Input.GetMouseButton(0))//누르는 동안
            Debug.Log("Mouse left button is pressing");
        if (Input.GetMouseButtonDown(0))//눌렀을 때
            Debug.Log("Mouse left button is down");
        if (Input.GetMouseButtonUp(0))//눌렀다 땔 때
            Debug.Log("Mouse left button is up");
    }


    // <InputManager>
    // 여러 장치의 입력을 입력매니저에 이름과 입력을 정의
    // 입력매니저의 이름으로 정의한 입력의 변경사항을 확인
    // 유니티 에디터의 Edit -> Project Settings -> Input Manager 에서 관리

    // 단, 유니티 초창기의 방식이기 때문에 키보드, 마우스, 조이스틱에 대한 장치만을 고려함
    // 추가) VR Oculus Integraion Kit 같은 경우 입력매니저와 유사한 방식을 사용
    private void InputByInputManager()
    {
        // 축 입력
        // Horizontal(수평) : 키보드(a,d / ←, →), 조이스틱(왼쪽 아날로그스틱 좌우)
        float x = Input.GetAxis("Horizontal");
        // Vertical(수직) : 키보드(w,s / ↑, ↓), 조이스틱(왼쪽 아날로그스틱 상하)
        float y = Input.GetAxis("Vertical");

        transform.position += new Vector3(x *3* Time.deltaTime, y * Time.deltaTime, 0);

        // 버튼 입력
        // Fire1 : 키보드(Left Ctrl), 마우스(Left Button), 조이스틱(button0)으로 정의됨
        if (Input.GetButton("Fire1"))
            Debug.Log("Fire1 is pressing");
        if (Input.GetButtonDown("Fire1"))
            Debug.Log("Fire1 is down");
        if (Input.GetButtonUp("Fire1"))
            Debug.Log("Fire1 is up");
    }


    // <InputSystem>
    // Unity 2019.1 부터 지원하게 된 입력방식
    // 컴포넌트를 통해 입력의 변경사항을 확인
    // GamePad, JoyStick, Mouse, Keyboard, Pointer, Pen, TouchScreen, XR 기기 등을 지원

    private void InputByInputSystem()
    {
        // InputSystem은 이벤트 방식으로 구현됨
        // Update마다 입력변경사항을 확인하는 방식 대신 변경이 있을 경우 이벤트로 확인
        // 메시지를 통해 받는 방식과 이벤트 함수를 직접 연결하는 방식 등으로 구성
    }

    // Move 입력에 반응하는 OnMove 메시지 함수

    private void Onmove(InputValue value)
    {
        Vector2 inputDir = value.Get<Vector2>();
        Debug.Log(inputDir);
    }

    private void OnJointBreak(InputValue value)
    {
        bool inputButton = value.isPressed;
        Debug.Log(inputButton);
    }


    //활용 예시

    Vector3 moveDir;
    private void OnMove(InputValue value)
    {
        Vector2 inputDir = value.Get<Vector2>();
        moveDir.x = inputDir.x;
        moveDir.z = inputDir.y;
    }

    private void Move()
    {
        transform.position += moveDir * 3f * Time.deltaTime;
    }

    public Rigidbody rigid;
    private void OnJump(InputValue value)
    {
        Jump();
    }

    private void Jump()
    {
        rigid.AddForce(Vector3.up * 5f, ForceMode.Impulse);
    }

    private void Update()
    {
        Move();
    }
}

트랜스폼(Transform)

게임오브젝트의 위치, 회전, 크기를 저장하는 컴포넌트이며, 게임오브젝트의 부모-자식 상태를 저장하는 컴포넌트이다. 게임오브젝트는 반드시 하나의 트랜스폼 컴포넌트를 가지고 있으며 추가 & 제거할 수 없다.

 //<트랜스폼 접근>
 private void TransformReference()
 {
     thisTransform = transform; //자신의 트랜스폼 직접 가리키기
 }


 // <트랜스폼 이동>
 // Translate : 트랜스폼의 이동 함수
 private void TranslateMove()
 {
     // 월드를 기준으로 이동
     transform.Translate(1, 0, 0, Space.World);
     // 자신을 기준으로 이동, Space 생략 시 자신 기준
     transform.Translate(1, 0, 0, Space.Self);
     // position을 이용한 이동, 월드기준
     transform.position += new Vector3(1, 0, 0);

 }


 // <트랜스폼 회전>
 // Rotate : 트랜스폼의 회전 함수
 private void Rotate()
 {
     // 월드를 기준으로 회전
     transform.Rotate(1, 0, 0, Space.World);
     transform.Rotate(Vector3.up, 30 * Time.deltaTime, Space.World);

     // 자신을 기준으로 회전
     transform.Rotate(1, 0, 0, Space.Self);
     transform.Rotate(Vector3.up, 30 * Time.deltaTime, Space.Self);

     // 특정 위치를 기준으로 회전
     transform.RotateAround(new Vector3(0, 0, 0), Vector3.up, 30*Time.deltaTime);
     transform.RotateAround(Camera.main.transform.position, Vector3.up, 1);

     // 위치를 바라보는 회전
     transform.LookAt(new Vector3(0, 0, 0));
 }


 //<트랜스폼 축>
 private void Axis()
 {
     // 트랜스폼의 x축
     Vector3 right = transform.right;

     // 트랜스폼의 y축
     Vector3 up = transform.up;

     // 트랜스폼의 z축
     Vector3 forward = transform.forward;
 }

 //비교 예시
 public Transform sphere;
 public Transform cube;
 public void Update()
 {
     sphere.position = transform.position + 3 * Vector3.forward;
     cube.position = transform.position + 3 * transform.forward;
 }

     // <트랜스폼 부모-자식 상태>
    // 트랜스폼은 부모 트랜스폼을 가질 수 있음
    // 부모 트랜스폼이 있는 경우 부모 트랜스폼의 위치, 회전, 크기 변경이 같이 적용됨
    // 이를 이용하여 계층적 구조를 정의하는데 유용함 (ex. 팔이 움직이면, 손가락도 같이 움직임)
    // 하이어라키 창 상에서 드래그 & 드롭을 통해 부모-자식 상태를 변경할 수 있음
    private void TransformParent()
    {
        GameObject newGameObject = new GameObject() { name = "NewGameObject" };

        // 부모 지정
        transform.parent = newGameObject.transform;

        // 부모를 기준으로한 트랜스폼
        // transform.localPosition    : 부모트랜스폼이 있는 경우 부모를 기준으로 한 위치
        // transform.localRotation    : 부모트랜스폼이 있는 경우 부모를 기준으로 한 회전
        // transform.localScale        : 부모트랜스폼이 있는 경우 부모를 기준으로 한 크기

        // 부모 해제
        transform.parent = null;

        // 월드를 기준으로한 트랜스폼
        // transform.localPosition == transform.position    : 부모트랜스폼이 없는 경우 월드를 기준으로 한 위치
        // transform.localRotation == transform.rotation    : 부모트랜스폼이 없는 경우 월드를 기준으로 한 회전
        // transform.localScale                                : 부모트랜스폼이 없는 경우 월드를 기준으로 한 크기
    }


    // <Quarternion & Euler>
    // Quarternion    : 유니티의 게임오브젝트의 3차원 방향을 저장하고 이를 방향에서 다른 방향으로의 상대 회전으로 정의
    //                  기하학적 회전으로 짐벌락 현상이 발생하지 않음
    // EulerAngle    : 3축을 기준으로 각도법으로 회전시키는 방법
    //                  직관적이지만 짐벌락 현상이 발생하여 회전이 겹치는 축이 생길 수 있음
    // 짐벌락        : 같은 방향으로 오브젝트의 두 회전 축이 겹치는 현상

    // Quarternion을 통해 회전각도를 계산하는 것은 직관적이지 않고 이해하기 어려움
    // 보통의 경우 쿼터니언 -> 오일러각도 -> 연산진행 -> 결과오일러각도 -> 결과쿼터니언 과 같이 연산의 결과 쿼터니언을 사용함
    private void Rotation()
    {
        Quaternion rotation = transform.rotation;

        Vector3 position = transform.position;
        Vector3 scale = transform.localScale;

        // 트랜스폼의 회전값은 Euler각도 표현이 아닌 Quaternion을 사용함
        transform.rotation = Quaternion.identity;

        // Euler각도를 Quaternion으로 변환
        transform.rotation = Quaternion.Euler(0, 90, 0);
        //  Vector3 rotation = transform.rotation.eulerAngles;
    }
}

프레임(Frame) : 정지된 게임상황, 장면 FPS(Frame per Second) : 1초 동안 표현한 프레임수 단위시간(DeltaTime) : 1프레임 동안 소모한 시간 DeltaTime == 1 / FPS

<프레임> 만화영화의 움직이는 그림들은 연속된 정지 그림들을 빠르게 전환하며 보여주어 움직이는 듯한 착각을 일으키는 방법이다. 게임도 마찬가지로 정지된 게임상황을 연속적으로 빠르게 교체하여 움직이는 게임상황처럼 표현한다. 이 각각의 정지 게임상황을 '프레임(Frame)'이라 하며 Unity의 경우 1프레임 당 1Update 가 진행된다.

<*FPS> 1초 동안 표현한 프레임수이다. 보통의 경우 30FPS 이상일 경우 움직이는 듯한 시각효과를 보여주며, 30FPS 이하일 경우 눈으로도 게임의 정지상황을 포착할 수 있게 된다.

<단위시간> 1프레임 동안 소모한 시간 Unity의 경우 Update마다 소요된 시간

<시간동기화> 게임의 FPS은 가변적이며 확정되어 있지 않다. 컴퓨터의 사양에 따라 처리시간이 다르거나, 외부의 요인으로 지연시간이 발생할 수 있기 때문이다. 게임이 다양한 상황에 따라 처리시간이 다를 수 있지만, 어떠한 기기에서든 동일한 게임진행이 되어야한다. 단위시간을 기반으로 게임을 구성할 경우 처리시간과 무관하게 모든 기기에서 동일한 게임진행이 가능하다.

(ex) 게임이 10FPS 일 경우 : 1 / 10초마다 10번씩 움직임 -> 결과는 1초동안 1 움직임 게임이 100FPS 일 경우 : 1 / 100초마다 100번씩 움직임 -> 결과는 1초동안 1 움직임 게임이 x FPS 일 경우 : 1 / x 초마다 x번씩 움직임 -> 결과는 1초동안 1 움직임

코루틴 (Coroutine)

작업을 다수의 프레임에 분산할 수 있는 비동기식 작업이다. 반복가능한 작업을 분산하여 진행하며, 실행을 일시정지하고 중단한 부분부터 다시시작할 수 있다. 단, 코루틴은 스레드가 아니며 코루틴의 작업은 여전히 메인 스레드에서 실행한다.

// <코루틴 진행>
// 반복가능한 작업을 StartCorouine을 통해 실행

IEnumerator SubRoutine()
{
    for (int i = 0; i < 10; i++)
    {
        yield return new WaitForSeconds(1);
        Debug.Log("코루틴 1초");
    }
}

private Coroutine routine; //코루틴 변수 생성
private void CoroutineStart()
{
    routine = StartCoroutine(SubRoutine());
}

// <코루틴 종료>
// StopCoroutine을 통해 진행 중인 코루틴 종료
// StopAllCoroutine을 통해 진행 중인 모든 코루틴 종료
// 반복가능한 작업이 모두 완료되었을 경우 자동 종료
// 코루틴을 진행시킨 스크립트가 비활성화된 경우 자동 종료

private void CoroutineStop()
{
    StopCoroutine(routine);     // 지정한 코루틴 종료
    //StopCoroutine(SubRoutine()); 잘못된 사용법, 함수를 멈추는게 아닌 routine을 멈추는 기능이다.
    StopAllCoroutines();        // 모든 코루틴 종료
}

// <코루틴 시간 지연>
// 코루틴은 시간 지연을 정의하여 반복가능한 작업의 진행 타이밍을 지정할 수 있음
IEnumerator CoRoutineWait()
{
    yield return new WaitForSeconds(n);     // n초간 시간지연
    yield return null;                      // 시간지연 없음
}

씬을 구성하는 모든 오브젝트의 기본 클래스로, 게임오브젝트만으로는 독자적인 기능은 없다. 실질적인 기능은 컴포넌트들이 수행하며, 게임오브젝트는 컴포넌트들을 가지기 위한 컨테이너이다.

<게임오브젝트 구성요소>

name : 게임오브젝트의 이름 active : 게임오브젝트의 활성화 여부, 비활성화인 경우 씬에 없는 게임오브젝트로 취급됨 static : 게임오브젝트의 정적상태 여부, 런타임 당시 변경되지 않는 데이터를 지정하여 최적화 tag : 게임오브젝트의 태그, 게임오브젝트를 특정하기 위한 수단으로 사용 layer : 게임오브젝트의 레이어, 씬에서 게임오브젝트를 분리하는 기준 (카메라의 선별적 표현, 충돌 그룹, 레이어 마스크 등에 사용)

component : 게임오브젝트에 포함된 기능모듈, 실질적인 기능을 수행 게임오브젝트는 컴포넌트를 담기위한 컨테이너 역할

컴포넌트 (Component)

특정한 기능을 수행할 수 있도록 구성한 작은 기능적 단위이다. 게임오브젝트의 작동을 담당하며 추가, 삭제하는 방식의 조립형 부품이다.

MonoBehaviour

컴포넌트를 기본클래스로 하는 클래스로 유니티 스크립트가 파생되는 기본 클래스이다. 게임 오브젝트에 스크립트를 컴포넌트로서 연결할 수 있는 구성을 제공하고 스크립트 직렬화 기능, 유니티메시지 이벤트를 받는 기능, 코루틴 기능을 포함한다.

<스크립트 직렬화 기능>

인스펙터 창에서 컴포넌트의 맴버변수 값을 확인하거나 변경하는 기능으로 컴포넌트의 값형식 데이터를 확인하거나 변경할 수 있고 컴포넌트의 참조형식 데이터를 드래그 앤 드랍 방식으로 연결한다.

public class UnityScript : MonoBehaviour
{
//Debug.LogError("에러표시");
//Debug.LogWarning("경고표시");
//Debug.Log("정보표시");

// <인스펙터창 직렬화가 가능한 자료형>
[Header("C# Type")]
public bool boolValue;
public int intValue;
public float floatValue;
public string stringValue;
// 그 외 기본 자료형

// 기본 자료형의 선형자료구조
public int[] array;
public List<int> list;

[Header("Unity Type")]
public Vector3 vector3; //xyz 값 부여 float
public Vector3Int vector3Int; //xyz 값 부여 int
public Color color; //컬러 변경
public LayerMask layerMask; //그룹을 대상으로 기능적용
public AnimationCurve curve; //곡선그래프로 속도,확률 등 보간
public Gradient gradient; //그라데이션 컬러 적용

[Header("Unity GameObject")]
public GameObject obj; //GameObject 참조변수

[Header("Unity Component")]
public new Transform transform; //Transform 참조변수
public new Rigidbody rigidbody; //Rigidbody 참조변수
public new Collider collider; //Collider 참조변수

[Header("Unity Event")]
public UnityEvent OnEvent; //이벤트 발생 시 지정한 함수 작동

// <어트리뷰트>
// 클래스, 프로퍼티 또는 함수 위에 명시하여 특별한 동작을 나타낼 수 있는 마커
[Space(30)] //픽셀 간격

[Header("Unity Attribute")] //구분자 제목
[SerializeField] //private 인스펙터에서 표시 
private int privateValue;
[HideInInspector] //public 인스펙터에서 숨기기
public int publicValue;

[Range(0, 10)] //최소, 최댓값 설정 / 슬라이드 형태
public float rangeValue;

[TextArea(3, 5)] //최소, 최대 보여지는 열 설정
public string textField;

유니티 메시지 함수

유니티가 보내는 메시지에 반응하는 함수이며 MonoBehavior 클래스에 같은 이름의 함수를 포함할 경우 반응한다. 스크립트는 유니티 엔진이 보내는 메시지에 반응하여 자신의 행동을 정의하는데, 같은 이름의 함수를 포함할 경우 유니티메시지에 반응하지만 포함하지 않을 경우 무시한다.

 private void Awake()
 {
     // 스크립트가 씬에 포함되었을 때 1회 호출되는 함수
     // 스크립트가 비활성화 되어 있는 경우에도 호출됨

     // 역할 : 스크립트가 필요로 하는 초기화 작업 진행
     //          (스크립트만의 초기화 작업, 외부 게임상황과 무관한 초기화 작업)
     // ex) 데이터 초기화, 컴포넌트 연결
     Debug.Log("Awake");
 }

 private void Start()
 {
     // 스크립트가 씬에 처음으로 Update하기 직전에 1회 호출됨
     // 스크립트가 비활성화된 경우 호출되지 않음

     // 역할 : 스크립트가 필요로 하는 초기화 작업 진행
     //          (다른 스크립트와의 연관 초기화 작업, 외부 게임상황이 필요한 초기화 작업)
     // ex) 몬스터의 플레이어 타겟선정
     Debug.Log("Start");
 }

 private void OnEnable()
 {
     // 스크립트가 활성화될 때마다 호출, 순서상 Start보다 먼저  

     // 역할 : 스크립트가 활성화 되었을 때 작업 진행
     Debug.Log("OnEnable");
 }
 private void OnDisable()
 {
     // 스크립트가 비활성화될 때마다 호출

     // 역할 : 스크립트가 비활성화 되었을 때 작업 진행
     Debug.Log("OnDisable");
 }

 private void Update()
 {
     // 게임의 프레임마다 호출

     // 역할 : 핵심 게임 로직 구현
     Debug.Log("Update");
 }

 private void LateUpdate()
 {
     // 씬의 모든 게임오브젝트의 Update가 진행된 후 호출

     // 역할 : 게임프레임의 진행 결과가 필요한 동작이 있는 기능 구현
     // ex) 플레이어의 위치가 결정된 후에 카메라의 위치 설정, 승패 판정
     Debug.Log("LateUpdate");
 }

 private void FixedUpdate()
 {
     // 유니티의 물리설정 단위시간마다 호출 (기본 1초에 50번)
     // Update와 다르게 프레임당 연산과 단위시간이 일정
     // 단, 게임로직 등, 연산이 많은 작업을 FixedUpdate에 구현하지 않아야 함

     // 역할 : 성능과 프레임 드랍에 영향을 받지 않아야 하는 작업
     // ex) 물리적 처리
     Debug.Log("FixedUpdate");
 }

 private void OnDestroy()
 {
     // 스크립트가 삭제되었을 경우 호출

     // 역할 : 스크립트의 마무리 진행
     Debug.Log("OnDestory");
 }

타일맵(Tilemap)

2차원 평면의 그래프를 정점이 아닌 위치를 통해 표현하는 그래프로 위치의 이동가능 유무만을 표현하는 bool 이차원 타일맵이다. 타일의 종류를 표현한 이차원 타일맵이 있고 인접하여 이동가능한 위치간에 간선이 있으며 가중치는 동일하다.

 internal class Tilemap
 {

  <타일맵 그래프>
 //예시 - 위치의 이동가능 표현한 이차원 타일맵
 //true: 이동 가능한 정점, false: 이동 불가한 정점

 bool[,] tileMap1 = new bool[7, 7]
    {
        { false, false, false, false, false, false, false },
        { false,  true, false,  true, false, false, false },
        { false,  true, false,  true, false,  true, false },
        { false,  true, false,  true,  true,  true, false },
        { false,  true, false,  true, false, false, false },
        { false,  true,  true,  true,  true,  true, false },
        { false, false, false, false, false, false, false },
    };

    // 예시 - 타일의 종류를 표현한 이차원 타일맵
    enum TileType//타일 종류를 지정하여 char로 표현
    {
        None = ' ',
        Wall = '#',
        Door = '*',
        Shop = 'S',
        Gate = 'G',
    }

    char[,] tileMap2 = new char[9, 9]
    {
        { '#', '#', '#', '#', '#', '#', '#', '#', '#' },
        { '#', ' ', '#', '#', ' ', ' ', '#', '#', '#' },
        { '#', ' ', '#', '#', ' ', '#', '#', ' ', '#' },
        { '#', ' ', '#', '#', '*', '#', '#', '*', '#' },
        { '#', ' ', '#', ' ', ' ', ' ', ' ', ' ', '#' },
        { '#', ' ', '#', ' ', '#', '#', '#', ' ', '#' },
        { '#', ' ', '#', ' ', '#', '#', '#', ' ', '#' },
        { '#', ' ', ' ', 'S', ' ', ' ', ' ', 'G', '#' },
        { '#', '#', '#', '#', '#', '#', '#', '#', '#' },
    };
}

A*(AStar) 알고리즘

다익스트라(Dijkstra) 알고리즘을 확장하여 만든 최단경로 탐색 알고리즘이다. 경로 탐색의 우선순위를 두고 유망한 해부터 우선적으로 탐색한다.

<A* 알고리즘 구현>

 public class AStar
 {
     const int CostStraight = 10; //직선 가중치
    const int CostDiagonal = 14; //대각선 가중치

    static Point[] Direction =  //방향 
    {
        new Point(  0, +1 ),            // 상
        new Point(  0, -1 ),            // 하
        new Point( -1,  0 ),            // 좌
        new Point( +1,  0 ),            // 우
        new Point( -1, +1 ),            // 좌상
        new Point( -1, -1 ),            // 좌하
        new Point( +1, +1 ),            // 우상
        new Point( +1, -1 )             // 우하
    };

    public static bool PathFinding(in bool[,] tileMap, in Point start, in Point end, out List<Point> path)
    //경로 찾기 bool 함수(bool 2차원 배열 타일맵, 포인트 시작 위치, 포인트 끝 위치, 포인트 리스트 경로)
    {
        int ySize = tileMap.GetLength(0); //?
        int xSize = tileMap.GetLength(1); //?

        ASNode[,] nodes = new ASNode[ySize, xSize]; //노드 데이터 보관 ASNode 2차원 배열
        bool[,] visited = new bool[ySize, xSize]; //방문 확인 visited 2차원배열 
        PriorityQueue<ASNode, int> nextPointPQ = new PriorityQueue<ASNode, int>();
        //f가 낮은 것부터 탐색하기 위한 우선순위큐<ASNode,int>  

        // 0. 시작 정점을 생성하여 추가
        ASNode startNode = new ASNode(start, new Point(), 0, Heuristic(start, end));
        //시작 정점 데이터 입력 ASNode(현재정점, 이전정점, g, h)

        nodes[startNode.pos.y, startNode.pos.x] = startNode;
        //시작 위치 노드에 대입
        nextPointPQ.Enqueue(startNode, startNode.f); 
        //우선순위큐에 f를 기준으로 값 대입

        while (nextPointPQ.Count > 0)//우선순위 큐 갯수만큼 반복
        {
            // 1. 다음으로 탐색할 정점 꺼내기 : f가 가장 낮은 정점
            ASNode nextNode = nextPointPQ.Dequeue();

            // 2. 탐색한 정점은 방문표시
            visited[nextNode.pos.y, nextNode.pos.x] = true;

            // 3. 다음으로 탐색할 정점이 도착지인 경우
            // 도착했다고 판단해서 경로 반환, 종료
            if (nextNode.pos.x == end.x && nextNode.pos.y == end.y)//다음 정점 x,y가 끝 위치와 같을 때
            {
                path = new List<Point>(); //경로 반환용 path 리스트

                Point point = end;
                while ((point.x == start.x && point.y == start.y) == false)
                    //도착지부터 시작점에 돌아올 때까지
                {
                    path.Add(point);//정점을 path에 추가
                    point = nodes[point.y, point.x].parent;//parent 추적
                }
                path.Add(start); //마지막에 시작지점 추가

                path.Reverse();//path 값 반전

                return true;//끝 위치를 찾은 경우니까 true
            }

            // 4. AStar 탐색을 진행 : 탐색한 정점 주변의 정점 점수 계산
            // 방향 탐색
            for (int i = 0; i < Direction.Length; i++)//방향배열 길이만큼 반복
            {
                int x = nextNode.pos.x + Direction[i].x;//?
                int y = nextNode.pos.y + Direction[i].y;//?

                // 4-1. 탐색하면 안되는 경우
                // 맵을 벗어났을 경우 : 0보다 작거나 배열보다 클때
                if (x < 0 || x >= xSize || y < 0 || y >= ySize)
                    continue;
                // 탐색할 수 없는 정점일 경우 : 벽을 만났을 때
                else if (tileMap[y, x] == false)
                    continue;
                // 이미 탐색한 정점일 경우 : visited == true
                else if (visited[y, x])
                    continue;
                // 대각선으로 이동이 불가능 지역인 경우
                // 대각선 방향의 양 옆이 막혀있을 때 대각선이동 불가 &&
                // 대각선 방향의 양 옆 중 하나라도 막혀 있을 때 대각선 이동불가 ||
                else if (i >= 4 && tileMap[y, nextNode.pos.x] == false || tileMap[nextNode.pos.y, x] == false)
                    continue;

                // 4-2. 탐색후 점수를 계산한 정점 만들기
                int g = nextNode.g + ((nextNode.pos.x == x || nextNode.pos.y == y) ? CostStraight : CostDiagonal);
                int h = Heuristic(new Point(x, y), end);//지금 위치부터 도착지까지 h
                ASNode newNode = new ASNode(new Point(x, y), nextNode.pos, g, h); //새로운 정점

                // 4-3. 정점의 갱신이 필요한 경우 새로운 정점으로 할당
                if (nodes[y, x] == null ||      // 점수계산을 하지 않은 정점이거나
                    nodes[y, x].f > newNode.f)  // 새로운 정점의 가중치가 더 낮을 때 
                {
                    nodes[y, x] = newNode;//새로운 정점의 값으로 갱신 
                    nextPointPQ.Enqueue(newNode, newNode.f);//새로운 정점 데이터 우선순위큐에 입력
                }
            }
        }
        //모든 정점을 탐색해도 도착지가 없을 떄 null, false
        path = null;
        return false;
    }

    // 휴리스틱 (Heuristic) : 최상의 경로를 추정하는 순위값, 휴리스틱에 의해 경로탐색 효율이 결정됨
    private static int Heuristic(Point start, Point end) //휴리스틱 계한 함수 생성
    {
        int xSize = Math.Abs(start.x - end.x);  // 가로로 가야하는 횟수, 절댓값 Math.Abs
        int ySize = Math.Abs(start.y - end.y);  // 세로로 가야하는 횟수, 절댓값 Math.Abs

        // 맨해튼 거리 : 직선을 통해 이동하는 거리
        // return CostStraight * (xSize + ySize);

        // 유클리드 거리 : 대각선을 통해 이동하는 거리 (가로제곱+세로제곱)에 루트Math.Sqrt = 대각선 거리
        // return CostStraight * (int)Math.Sqrt(xSize * xSize + ySize * ySize);

        // 타일맵 거리 : 직선과 대각선을 통해 이동하는 거리
        int straightCount = Math.Abs(xSize - ySize); //대각선을 먼저쓰고 남은 갯수 = 직선 갯수
        int diagonalCount = Math.Max(xSize, ySize) - straightCount; //xSize, ySize 중 큰 것 - 직선 갯수 = 대각선 갯수
        return CostStraight * straightCount + CostDiagonal * diagonalCount;
        //직선가중치*직선갯수 + 대각선가중치*대각선갯수 = h

        //다익스트라
        //return 0;
    }

    public class ASNode// 정점이 가지는 데이터 ASNode 생성
    {
        public Point pos;       // 현재 정점 위치
        public Point parent;    // 이 정점을 탐색한 정점 위치

        public int g;           // 현재까지의 값, 즉 지금까지 경로 가중치(g가 높은 걸 우선탐색 경향, 남은거리가 짧기 때문)
        public int h;           // 휴리스틱, 앞으로 예상되는 값, 목표까지 추정 경로 가중치
        public int f;           // 총 예상거리, f(x) = g(x) + h(x);

        public ASNode(Point point, Point parent, int g, int h) //생성자
        {
            this.pos = point;
            this.parent = parent;
            this.g = g;
            this.h = h; 
            this.f = g + h;
        }
    }
}

public struct Point //x,y 값을 가지는 포인트 구조체
{
    public int x;
    public int y;

    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}

<출력 코드>

 internal class Program
 {
     static void Main(string[] args)
     {
         bool[,] tileMap = new bool[9, 9]
         {
             { false, false, false, false, false, false, false, false, false },
             { false,  true,  true,  true, false, false, false,  true, false },
             { false,  true, false,  true, false, false, false,  true, false },
             { false,  true, false,  true,  true,  true,  true,  true, false },
             { false,  true, false,  true, false,  true,  true,  true, false },
             { false,  true, false,  true, false,  true,  true,  true, false },
             { false, false, false, false, false, false, false,  true, false },
             { false,  true,  true,  true,  true,  true,  true,  true, false },
             { false, false, false, false, false, false, false, false, false },
         };

         AStar.PathFinding(tileMap, new Point(1, 1), new Point(1, 7), out List<Point> path);
         PrintResult(tileMap, path);
     }

     static void PrintResult(in bool[,] tileMap, in List<Point> path)
     {
         char[,] pathMap = new char[tileMap.GetLength(0), tileMap.GetLength(1)];
         for (int y = 0; y < pathMap.GetLength(0); y++)
         {
             for (int x = 0; x < pathMap.GetLength(1); x++)
             {
                 if (tileMap[y, x])
                     pathMap[y, x] = ' ';//빈공간
                 else
                     pathMap[y, x] = 'X';//막힌공간
             }
         }

         foreach (Point point in path)
         {
             pathMap[point.y, point.x] = '*';//이동경로
         }

         Point start = path.First();
         Point end = path.Last();
         pathMap[start.y, start.x] = 'S';//시작위치
         pathMap[end.y, end.x] = 'E';//도착위치

         for (int i = 0; i < pathMap.GetLength(0); i++)
         {
             for (int j = 0; j < pathMap.GetLength(1); j++)
             {
                 Console.Write(pathMap[i, j]);
             }
             Console.WriteLine();
         }
     }
 }

데이크스트라 알고리즘 (Dijkstra Algorithm)

특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하기 위해 사용한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 후, 해당 노드를 거쳐 다른 노드로 가는 비용을 계산한다.

<데이크스트라 알고리즘 (Dijkstra Algorithm) 구현>

internal class Dijkstra
{
     const int INF = 99999;
    //단절 INF 최댓값 상수설정, int.Maxvalue 사용 시 오버플로우 위험있음

    public static void ShortestPath(in int[,] graph, in int start,out bool[] visited, out int[] distance, out int[] parents)
    //최단거리 함수 생성
    {
        int size = graph.GetLength(0);//첫 배열길이를 가지는 size 변수
        visited = new bool[size];//첫 배열길이 대입
        distance = new int[size];//첫 배열길이 대입
        parents = new int[size];//첫 배열길이 대입

        for (int i = 0; i < size; i++)// 갯수만큼 반복
        {
            visited[i] = false; //초기값 대입
            distance[i] = INF; //초기값 대입
            parents[i] = -1;  //초기값 대입
        }
        distance[start] = 0; //시작지점 0;

        for (int i = 0; i < size; i++) // 갯수만큼 반복
        {
            // 1. 방문하지 않은 정점 중 가장 가까운 정점부터 탐색
            int next = -1;//다음 정점 next 초기값 대입
            int minDistance = INF;//다음 정점까지 거리 minDistance 초기값 대입

            for (int j = 0; j < size; j++)//갯수만큼 반복
            {
                if (!visited[j]&& 
                    distance[j] < minDistance) 
                    //방문하지 않았으면서(false) And 거리가 더 가까운 경우
                {
                    next = j;//j가 다음 정점
                    minDistance = distance[j];//distance[j]가 최소거리
                }
            }

            if (next < 0)// 반복이 끝났을 때, 해당되는 값이 없을 때
                break; //멈춘다.

            // 2. 직접연결된 거리보다 다른 정점을 거쳐서 더 짧아진다면 갱신.
            for (int j = 0; j < size; j++)
            {
                // distance[j] : 목적지까지 직접 연결된 거리
                // distance[next] : 탐색중인 정점까지 거리
                // graph[next, j] : 탐색중인 정점부터 목적지의 거리
                if (distance[j]> distance[next]+ graph[next, j])
                    //직접거리가 탐색중인 정점을 거쳐서 목적지까지의 거리보다 먼 경우
                {
                    distance[j] = distance[next] + graph[next, j];
                    //탐색정점을 거쳐서 간 거리를 직접거리로 대입

                    parents[j] = next;
                    //직전 정점 값 next;
                }
            }
            visited[next] = true;//방문한 정점 true 표기
        }
    }
}

<함수 출력>

internal class Program
{
    const int INF = 99999;

    static void Main(string[] args)
    {
        int[,] graph = new int[8, 8] //사용할 그래프 생성
        {
        //예시, 임의로 작성
            { INF, INF, INF, 5, 4, INF, INF, INF },
            { INF, INF, 6, INF, INF, INF, INF, INF },
            { 6, INF, INF, INF, INF, 8, INF, INF},
            { INF, INF, INF,INF, INF, 6, INF, INF },
            { INF, INF, 6, INF, INF, INF, INF, INF},
            { INF, INF, INF, INF, INF, INF, 4, 6},
            { INF, INF, 9, INF, INF, 1, INF, INF},
            { INF, INF, INF, INF, INF, INF, INF, INF },

        };

        Dijkstra.ShortestPath(in graph, 0,out bool[] visited, out int[] distance, out int[] parents);//함수에 값 대입

        Console.WriteLine("<Dijkstra>");

        PrintDijkstra(visited, distance, parents); 
    }

    private static void PrintDijkstra(bool[] visited, int[] distance, int[] parents)//값 출력 함수 생성
    {
        Console.WriteLine($"{"Vertex",8}{"Visited",10}{"Distance",10}{"Parents",10}");

        for (int i = 0; i < distance.Length; i++)
        {
            Console.Write($"{i,8}");

            Console.Write($"{visited[i],10}");

            if (distance[i] == INF)
            {
                Console.Write($"{"INF",10}");
            }
            else
            {
                Console.Write($"{distance[i],10}");
            }

            Console.WriteLine($"{parents[i],10}");
        }
    }
}

키 값을 해시함수로 해싱하여 해시테이블의 특정 위치로 직접 엑세스하도록 만든 방식이다. 해시 : 임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑

    <해시테이블 구현>
    데이터를 담을 테이블을 이미 크게 확보해 놓은 후
    입력받은 키를 해싱하여 테이블 고유한 index를 계산하고 데이터를 담아 보관

              해싱
             ┌────┐
        27 ─→│    │─→  27
       385 ─→│해시│─→ 192
       581 ─→│함수│─→   2
      1031 ─→│    │─→  66
             └────┘
    [0]   [1]   [2]       [27]      [66]      [191] [192] [193]
    ┌─────┬─────┬─────┬─  ─┬────┬─  ─┬──────┬─  ─┬─────┬─────┬─────┐
    │    │     │ 582 │....│ 27 │...│ 1031 │....│    │ 385 │     │
    └─────┴─────┴─────┴─  ─┴────┴─  ─┴──────┴─  ─┴─────┴─────┴─────┘


     <해시함수>
     키값을 해싱하여 고유한 index를 만드는 함수
     하나의 키값을 해싱하는 경우 반드시 항상 같은 결과여야 함
     효율 : 해시의 결과가 분산적일수록 효율이 좋음

     나눗셈법   : 데이터 % 테이블크기
     자리수접기 : 데이터의 각 자리수의 합
     SHA-2      : 미국 국가안보국(NSA)이 설계한 암호화 해시 함수

     나눗셈법   예시 : 132031 → (132031 % 1000) = 31
     자리수접기 예시 : "hash" → h(104) + a(97) + s(115) + h(104) = 420


     <해시테이블 주의점 - 충돌>
     해시함수가 서로 다른 입력 값에 대해 동일한 해시테이블 주소를 반환하는 것
     모든 입력 값에 대해 고유한 해시 값을 만드는 것은 불가능하며 충돌은 피할 수 없음

               해싱
              ┌────┐
        274 ─→│해시│─→  81
        660 ─→│함수│─→  81
              └────┘

      [0]   [1]   [2]        [81]        [191] [192] [193]
     ┌─────┬─────┬─────┬─  ─┬─────────┬─  ─┬─────┬─────┬─────┐
     │    │     │     │...│ 274 660 │...│     │     │     │
     └─────┴─────┴─────┴─  ─┴─────────┴─  ─┴─────┴─────┴─────┘


      <충돌해결방안 - 체이닝>
      해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식
      장점 : 해시테이블에 자료가 많아지더라도 성능저하가 적음
      단점 : 해시테이블 외 추가적인 저장공간이 필요

                해싱
               ┌────┐
         274 ─→│해시│─→  81
         660 ─→│함수│─→  81
               └────┘

       [0]   [1]   [2]      [81]     [191] [192] [193]
      ┌─────┬─────┬─────┬─  ─┬─────┬─  ─┬─────┬─────┬─────┐
      │     │    │     │...│  │  │...│     │     │     │
      └─────┴─────┴─────┴─  ─┴──│──┴─  ─┴─────┴─────┴─────┘
                              ↓
                      ┌─────┬─┐ ┌─────┬─┐
                      │ 274 │──→│ 660 │ │
                      └─────┴─┘ └─────┴─┘


       <충돌해결방안 - 개방주소법> C#에서 사용
       해시 충돌이 발생하면 다른 빈 공간에 데이터를 삽입하는 방식
       해시 충돌시 선형탐색, 제곱탐색, 이중해시 등을 통해 다른 빈 공간을 선정
       장점 : 추가적인 저장공간이 필요하지 않음, 삽입삭제시 오버헤드가 적음
       단점 : 해시테이블에 자료가 많아질수록 성능저하가 많음

       개방주소법 해시테이블의 공간 사용률이 높을 경우(통계적으로 70% 이상) 급격한 성능저하가 발생
       이런 경우 재해싱을 통해 공간 사용률을 낮추어 다시 효율을 확보함
       재해싱 : 해시테이블의 크기를 늘리고 테이블 내의 모든 데이터를 다시 해싱하여 보관

                 해싱
                ┌────┐
          274 ─→│해시│─→  81
          660 ─→│함수│─→  81
                └────┘

        [0]   [1]   [2]      [81]  [82]      [191] [192] [193]
       ┌─────┬─────┬─────┬─  ─┬─────┬─────┬─  ─┬─────┬─────┬─────┐
       │     │     │    │....│ 274 │    │....│    │     │     │
       └─────┴─────┴─────┴─  ─┴─────┴─────┴─  ─┴─────┴─────┴─────┘
                               ↑660(충돌)

        [0]   [1]   [2]      [81]  [82]     [191] [192] [193]
      ┌─────┬─────┬─────┬─  ─┬─────┬─────┬─  ─┬─────┬─────┬─────┐
      │     │    │    │....│ 274 │ 660 │....│    │     │     │
      └─────┴─────┴─────┴─  ─┴─────┴─────┴─  ─┴─────┴─────┴─────┘
                                   ↑(다음위치에 저장)


        <해시테이블의 시간복잡도>
 접근       탐색       삽입       삭제(*삭제된 위치 재사용불가)
  X         O(1)       O(1)       O(1)
충돌하는 특성으로 인해 삽입, 삭제에 불리하다.



        static void Main(string[] args)
        {
            // 해시테이블 기반의 HashSet 자료구조
            // 중복이 없는 해시기반의 저장소
            //HashSet 0(1) 입력순서 출력// SortedSet(logN) 정렬 출력
            //둘 다 값을 중복 없이 모아두는 저장소로 활용
            HashSet<string> set = new HashSet<string>();

            // 삽입
            set.Add("D");
            set.Add("B");
            set.Add("B");   //중복추가 무시
            set.Add("C");
            set.Add("A");
            set.Add("A");
            set.Add("A");
            set.Add("E");

            // 삭제
            set.Remove("B");

            // 탐색
            set.Contains("A");      // 포함 확인

            // 순서대로 출력시 포함된 순서대로 결과 확인
            foreach (string value in set)
            {
                Console.Write(value);   // output : DCAE
            }
            Console.WriteLine();


            // 해시테이블 기반의 Dictionary 자료구조
            // 중복을 허용하지 않는 key를 기준으로 해시기반의 value 저장소
            // Dictionary 0(1) 입력순서출력 // SortedDictionary(logN)정렬출력
            Dictionary<int, string> dictionary = new Dictionary<int, string>();

            // 삽입
            dictionary.Add(2, "A");
            dictionary.Add(1, "B");
            dictionary.Add(4, "C");
            dictionary.Add(3, "D");
            dictionary.Add(5, "E");
            // dictionary.Add(4, "F");    // error : Dictionary는 중복을 허용하지 않음
            dictionary.TryAdd(4, "E"); // SortedDictionary와 같은 명령어들 사용가능
            // 삭제
            dictionary.Remove(5);

            // 탐색
            dictionary.ContainsKey(3);                        // 포함 확인
            dictionary.TryGetValue(3, out string dicValue);   // 탐색 시도
            dictionary[4] = "F";

            // 순서대로 출력시 정렬된 결과 확인
            foreach (string value in dictionary.Values)
            {
                Console.Write(value);     // output : ABCD
            }
            Console.WriteLine();

            dictionary.TryGetValue(4,out string ivalue);
Console.WriteLine(ivalue); // output: F
        }

<해시테이블(HashTable)기능 구현>

namespace DataStructure
{   //Dictionary 클래스 생성<key,value 자료형 일반화>
    //key 값을 비교할 필요가 없기 때문에 IComparable이 아닌
    //키 값이 같은지 다른지 비교하는 where TKey : IEquatable<TKey>
    public class Dictionary<TKey, TValue> where TKey : IEquatable<TKey>
    {
        private const int DefaultCapacity = 1000; //기본 크기 설정(소수로 설정 시 효율 증가)

        private struct Entry //구조체 Entry
        {
            public enum State { None, Using, Deleted } //Entry의 상태를 구별하는 열거형 

            public State state; //state값
            public TKey key; //key값
            public TValue value; //value값         
        }

        private Entry[] table; //key와 value, state를 가진 테이블 배열 생성
        private int usedCount; //사용중인 갯수

        public Dictionary()
        {
            table = new Entry[DefaultCapacity]; //테이블 기본크기 
            usedCount = 0; //갯수 0
        }

        public TValue this[TKey key] //this 인덱서, dictionary[4] = "F"; 구현
        {
            get //가져오기
            {
                if (Find(key, out int index)) //키값 찾았을 때
                {
                    return table[index].value; //값 확인
                }
                else //키값 못 찾았을 때
                {
                    throw new KeyNotFoundException(); //예외처리
                }
            }
            set //갱신하기
            {
                if (Find(key, out int index)) //키값 찾았을 때
                {
                    table[index].value = value; //value값 인덱스 위치에 입력
                }
                else //키값 못 찾았을 때
                {
                    Add(key, value); //비어있는 위치에 키,데이터 입력
                    //table[index].key = key;
                    //table[index].value = value;
                    table[index].state = Entry.State.Using; //인덱스위치를 사용중으로 상태변경
                    usedCount++; //갯수 증가
                }
            }
        }

        public void Add(TKey key, TValue value) //값 입력 함수 Add
        {
            if (Find(key, out int index))  //입력한 키값이 있다면 
            {
                throw new InvalidOperationException("Already exist key"); //예외처리
            }
            else // 입력한 키값이 없다면
            {
                if (usedCount > table.Length * 0.7f) // 테이블의 70%이상 사용중이라면
                {
                    ReHashing(); //테이블 크기 증가 
                }

                table[index].key = key; //지금 key값 현재인덱스key값에 입력
                table[index].value = value; // 지금 value값 현재인덱스 value값에 입력
                table[index].state = Entry.State.Using; //값을 추가했으니 사용중으로 상태변경
                usedCount++; //갯수 증가
            }
        }

        public void Clear()
        {
            table = new Entry[DefaultCapacity];
            usedCount = 0;
        }

        public bool ContainsKey(TKey key) //키값으로 데이터 확인하는 함수
        {
            if (Find(key, out int index)) //찾는 키값이 있을때
            {
                return true;
            }
            else //찾는 키값이 없을때
            {
                return false;
            }
        }

        public bool Remove(TKey key) //키값을 찾아 삭제하는 함수 구현
        {
            if (Find(key, out int index)) //찾는 키값이 있다면
            {
                table[index].state = Entry.State.Deleted; //삭제된 것으로 상태변경
                return true; //완료
            }
            else //찾는 키값이 없다면
            {
                return false; //실패
            }
        }

        private bool Find(TKey key, out int index) //key값이 있는지 확인하는 bool함수
        {
            if (key == null) //key값이 없으면
                throw new ArgumentNullException(); //예외처리

            index = Hash(key); //key값을 해싱하여 index입력

            for (int i = 0; i < table.Length; i++) //빈자리를 발견할 때까지 반복
            {
                if (table[index].state == Entry.State.None) //테이블 인덱스위치가 비어있는 경우
                {
                    return false; //찾지 못했으니 false
                }
                else if (table[index].state == Entry.State.Using) //테이블 인덱스위치가 사용중인 경우
                {
                    if (key.Equals(table[index].key)) //현재 키 값이 테이블에 있는 키 값과 같은지 확인
                    {
                        return true; //같으면 true
                    }
                    else // 같지 않다면
                    {
                        // 다음칸으로
                        index = Hash2(index);
                    }
                }
                else // if(table[index].state==Entry.state.Deleted) 테이블 인덱스 위치가 지워진 상태일 때
                {
                    //다음칸으로
                    index = Hash2(index);
                }
            }
            index = -1; //빈칸이 없을경우, 인덱스를 찾을 수 없다는 표현
            throw new InvalidOperationException();
        }

        private int Hash(TKey key) //key값으로 해싱하는 함수
        {

            return Math.Abs(key.GetHashCode() % table.Length); //key값을 받아서 테이블크기로 나눠서 나머지, 절댓값으로 고정, 나눗셈법 구현
        }

        private int Hash2(int index) //충돌했을 떄 선형탐사하는 함수
        {
            // 선형 탐사
            return (index + 1) % table.Length; //다음 인덱스에 나눗셈법하여 입력

            // 제곱 탐사
            // return (index + 1) * (index + 1) % table.Length;

            // 이중 해싱
            // return Math.Abs((index + 1).GetHashCode() % table.Length);
        }

        private void ReHashing() //데이터가 일정 부분 채워지면 크기 변경
        {
            Entry[] oldTable = table; //기존 테이블을 변수에 저장
            table = new Entry[table.Length * 2]; //기존테이블의 2배 크기로 인스턴스 생성
            usedCount = 0; //갯수 초기화

            for (int i = 0; i < oldTable.Length; i++) //기존테이블을 전부 확인
            {
                Entry entry = oldTable[i]; //인덱스 위치를 순서대로 넣고
                if (entry.state == Entry.State.Using) // 사용중인 위치가 있다면
                {
                    Add(entry.key, entry.value); // 입력해준다.
                }
            }
        }
    }
}

부모 노드가 자식 노드보다 우선순위가 높은 속성을 만족하는 트리기반의 자료구조이다. 많은 자료 중 우선순위가 가장 높은 요소를 빠르게 가져오기 위해 사용한다.

<힙 구현>
힙은 노드들이 트리의 왼쪽부터 채운 완전이진트리를 구조를 가지며
부모 노드가 두 자식노드보다 우선순위가 높은 값을 위치시킴
힙 상태를 만족하는 경우 가장 최상단 노드가 모든 노드 중 우선순위가 가장 높음

             2
      ┌───────┴───────┐
      8              52
  ┌───┴───┐       ┌───┴───┐
  13     37      67     92
┌─┴─┐   ┌─┘
17 43  52


<힙 노드 삽입>
1. 힙의 최고 깊이, 최우측에 새 노드를 추가

             2
      ┌───────┴───────┐
      8              52
  ┌───┴───┐       ┌───┴───┐
  13     37      67      92
┌─┴─┐   ┌─┴─┐
17  43  52 (7)

2. 삽입한 노드와 부모 노드를 비교하여 우선순위가 더 높은 경우 교체

             2                              2                             2
      ┌───────┴───────┐               ┌───────┴───────┐               ┌───────┴───────┐
      8              52             8              52             (7)             52
  ┌───┴───┐       ┌───┴───┐  =>   ┌───┴───┐       ┌───┴───┐  =>   ┌───┴───┐       ┌───┴───┐
 13      37      67     92      13     (7)     67      92      13      8      67      92
┌─┴─┐   ┌─┴─┐                   ┌─┴─┐   ┌─┴─┐                   ┌─┴─┐   ┌─┴─┐
17  43  52 (7)                 17  43  52  37                 17  43  52  37

3. 더이상 교체되지 않을때까지 과정을 반복

             2                              2
      ┌───────┴───────┐               ┌───────┴───────┐
     (7)            52              7              52
  ┌───┴───┐       ┌───┴───┐  =>   ┌───┴───┐       ┌───┴───┐
  13     8       67     92      13      8      67      92
┌─┴─┐   ┌─┴─┐                   ┌─┴─┐   ┌─┴─┐
17 43  52  37                  17 43  52  37


<힙 노드 삭제>
1. 최상단의 노드와 최우측 노드를 교체한 뒤 최우측 노드를 삭제

             (2)                           (37)                         (37)
      ┌───────┴───────┐               ┌───────┴───────┐              ┌───────┴───────┐
      7             52              7              52             7              52
  ┌───┴───┐       ┌───┴───┐  =>   ┌───┴───┐       ┌───┴───┐  =>  ┌───┴───┐       ┌───┴───┐
  13     8       67     92      13      8      67      92     13     8       67      92
┌─┴─┐   ┌─┴─┐                   ┌─┴─┐   ┌─┴─┐                  ┌─┴─┐   ┌─┘
17 43  52 (37)                 17  43  52 (2)                17  43  52

2. 교체된 노드와 두 자식 노드를 비교하여 우선순위가 더 높은 노드와 교체

            (37)                            7                             7
      ┌───────┴───────┐               ┌───────┴───────┐               ┌───────┴───────┐
      7              52            (37)            52              8              52
  ┌───┴───┐       ┌───┴───┐  =>   ┌───┴───┐       ┌───┴───┐  =>   ┌───┴───┐       ┌───┴───┐
  13      8      67     92      13      8      67      92      13    (37)     67      92
┌─┴─┐   ┌─┘                     ┌─┴─┐   ┌─┘                     ┌─┴─┐   ┌─┘
17 43  52                      17  43  52                     17  43  52

3. 더이상 교체되지 않을때까지 과정을 반복

             7                              7
      ┌───────┴───────┐               ┌───────┴───────┐
      8             52              8              52
  ┌───┴───┐       ┌───┴───┐  =>   ┌───┴───┐       ┌───┴───┐
  13    (37)     67      92     13      37      67     92
┌─┴─┐   ┌─┘                     ┌─┴─┐   ┌─┘
17 43  52                      17  43  52


<힙 구현>
힙의 완전이진트리 특징의 경우 배열을 통해서 구현하기 좋음
노드의 위치를 배열에 순서대로 저장
노드가 위치한 인덱스에 연산을 진행하여 노드 이동이 가능

부모로 이동         : (index - 1) / 2
왼쪽자식으로 이동   : 2 * index + 1
오른쪽자식으로 이동 : 2 * index + 2

       0
   ┌───┴───┐
   1       2       ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
 ┌─┴─┐   ┌─┴─┐ =>  │0│1│2│3│4│5│6│7│8│9│
 3   4   5   6     └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
┌┴┐ ┌┘
7 8 9

우선순위큐(PriorityQueue)

정해진 순서보다 기준에 따라 우선순위를 정하는 것이 적합한 경우

//입력 순서대로 출력하는 Queue를 사용했을 때
Queue<string> queue = new Queue<string>();

queue.Enqueue("환자1 - 감기");
queue.Enqueue("환자2 - 타박상");
queue.Enqueue("환자3 - 심장마비");
//입력 순서대로 처리
while (queue.Count > 0)
{
    Console.WriteLine(queue.Dequeue()); //output: 환자1 - 감기, 환자2 - 타박상, 환자3 - 심장마비 
}


//기준에 따라 우선순위대로 처리하는 PriorityQueue를 사용했을 때
PriorityQueue<string, int>priorityQueue = new PriorityQueue<string, int>();

//priorityQueue.Enqueue(Value, Key);
priorityQueue.Enqueue("환자1 - 감기", 5);
priorityQueue.Enqueue("환자2 - 타박상", 8);
priorityQueue.Enqueue("환자3 - 심장마비", 1);
priorityQueue.Enqueue("환자4 - 교통사고", 3);

//각 증상에 따라 등급을 매겨 순서대로 처리
for (int i =0;i<3;i++)//3번 출력
{
    Console.WriteLine(priorityQueue.Dequeue());//output: 환자3 - 심장마비,환자4 - 교통사고,환자1 - 감기
}

priorityQueue.Enqueue("환자3 - 심장마비", 1);//중간에 추가 입력

while (priorityQueue.Count > 0)//전부 출력
{
    Console.WriteLine(priorityQueue.Dequeue());//output: 환자3 - 심장마비, 환자2 - 타박상                                                
                                             //중간에 추가 입력해도 우선순위대로 출력
}

Console.WriteLine(priorityQueue.Peek());   //다음 우선순위 확인


// 오름차순 : 기본 int 우선순위
PriorityQueue<string, int> pq1 = new PriorityQueue<string, int>();

pq1.Enqueue("Data1", 1);
pq1.Enqueue("Data7", 7);
pq1.Enqueue("Data5", 5);
pq1.Enqueue("Data3", 3);
pq1.Enqueue("Data9", 9);

for (int i = 0; i < 3; i++)
{
    Console.WriteLine(pq1.Dequeue());   // output : Data1, Data3, Data5
}
pq1.Enqueue("Data4", 4);
pq1.Enqueue("Data2", 2);
pq1.Enqueue("Data6", 6);
pq1.Enqueue("Data8", 8);

while (pq1.Count > 0)
{
    Console.WriteLine(pq1.Dequeue());   // output : Data2, Data4, Data6, Data7, Data8, Data9
}

// 내림차순 : int 우선순위에 * -1을 적용하여 사용
PriorityQueue<string, int> pq2 = new PriorityQueue<string, int>();

pq2.Enqueue("Data1", -1);
pq2.Enqueue("Data7", -7);
pq2.Enqueue("Data5", -5);
pq2.Enqueue("Data3", -3);
pq2.Enqueue("Data9", -9);

for (int i = 0; i < 3; i++)
{
    Console.WriteLine(pq2.Dequeue());   // output : Data9, Data7, Data5
}
pq2.Enqueue("Data4", -4);
pq2.Enqueue("Data2", -2);
pq2.Enqueue("Data6", -6);
pq2.Enqueue("Data8", -8);

while (pq2.Count > 0)
{
    Console.WriteLine(pq2.Dequeue());   // output : Data8, Data6, Data4, Data3, Data2, Data1
}

<우선순위큐(PriorityQueue) 기능구현>

namespace DataStructure
{                       
    //우선순위큐 클래스<일반화>
    //우선순위는 비교가 필요하기 때문에 where TPriority : IComparable<TPriority>
    public class PriorityQueue<TElement, TPriority> where TPriority : IComparable<TPriority>
    {
        private struct Node //배열로 구현하기 위해 구조체로 Node 생성
        {
            public TElement element;   //데이터
            public TPriority priority; //우선순위

            public Node(TElement element, TPriority priority)//생성자
            {
                this.element = element;
                this.priority = priority;
            }
        }

        private List<Node> nodes; 

        public PriorityQueue()       //생성자
        {
            nodes = new List<Node>(); //리스트 생성
        }

        public int Count { get { return nodes.Count; } }

        public void Enqueue(TElement element, TPriority priority)//입력함수 구현
        {
            Node newNode = new Node(element, priority);
            nodes.Add(newNode);  //리스트에 새 노드 입력
            int index = nodes.Count - 1; //인덱스 위치는 리스트의 갯수-1

            while (index > 0) //인덱스0(최상단)에 도착하기 전까지 반복
            {
                int parentIndex = (index - 1) / 2; //부모 인덱스 위치
                Node parentNode = nodes[parentIndex]; //부모 값을  parentNode에 입력

                if (newNode.priority.CompareTo(parentNode.priority) < 0)
                    //새 노드의 우선순위와 부모의 우선순위를 비교했을 때 더 작다면
                {
                    //새노드가 상단으로 올라가야 한다.
                    nodes[index] = parentNode; //부모노드를 새 노드 위치에 입력
                    nodes[parentIndex] = newNode;//새 노드를 부모 노드 위치에 입력
                    index = parentIndex; //인덱스 상승
                }   
                else //부모가 더 우선순위가 높을 때
                {
                    break;//반복 중지
                }
            }
           // nodes[index] = newNode;
        }

        public TElement Peek() //다음 출력 확인
        {
            if (nodes.Count == 0)
                throw new InvalidOperationException();

            return nodes[0].element;
        }

        public TElement Dequeue() //출력함수 구현
        {
            if (nodes.Count == 0)
                throw new InvalidOperationException();

            Node rootNode = nodes[0];//root 노드를 변수에 보관

            //제거 작업
            Node lastNode = nodes[nodes.Count - 1];//마지막노드 변수에 보관
            nodes[0] = lastNode; //마지막 노드 root노드 위치에 입력
            nodes.RemoveAt(nodes.Count - 1);//마지막노드 제거

            int index = 0;//인덱스 위치 최상단
            while (index < nodes.Count)// 인덱스가 마지막 위치까지 반복
            {
                int leftIndex = 2 * index + 1; //왼쪽 자식노드 인덱스 위치
                int rightIndex = 2 * index + 2; //오른쪽 자식노드 인덱스 위치

                if (rightIndex < nodes.Count)//자식이 둘 다 있는 경우
                {
                    int lessIndex;
                    if (nodes[leftIndex].priority.CompareTo(nodes[rightIndex].priority) < 0)
                        //왼쪽 인덱스 우선순위와 오른쪽 인덱스 우선순위를 비교해서 더 작다면
                    {   
                        lessIndex = leftIndex;//왼쪽 인덱스를 작은인덱스 변수에 입력
                    }
                    else//반대일 경우
                    {
                        lessIndex = rightIndex;//오른쪽 인덱스를 작은인덱스 변수에 입력
                    }
                    Node lessNode = nodes[lessIndex]; //작은 인덱스 노드 값을 작은노드변수에 입력 
                    if ((nodes[index].priority.CompareTo(nodes[lessIndex].priority) > 0))
                        //현재 인덱스 우선순위와 작은 인덱스 우선순위를 비교해서 더 크다면
                    {
                        nodes[lessIndex] = lastNode;//마지막노드에서 가져온 값을 작은 인덱스 위치에 입력
                        nodes[index] = lessNode; //작은 인덱스 노드 값을 최상단 인덱스 위치로 입력
                        index = lessIndex; //작은인덱스 위치를 현재 인덱스로 변경
                    }
                    else //현재 인덱스가 자식인덱스보다 작을 때
                    {
                        break; //반복 종료
                    }
                }
                else if (leftIndex < nodes.Count)//자식이 하나만 있는 경우
                {
                    Node leftNode = nodes[leftIndex];//왼쪽 자식노드의 값을 변수에 입력
                    if (nodes[index].priority.CompareTo(nodes[leftIndex].priority) > 0)
                        //현재노드의 우선순위와 왼쪽자식노드의 우선순위를 비교했을 때 크다면
                    {
                        nodes[leftIndex] = lastNode; //마지막 인덱스에서 가져온 값을 왼쪽인덱스에 입력
                        nodes[index] = leftNode;//왼쪽노드를 현재 인덱스에 입력
                        index = leftIndex;//왼쪽자식인덱스를 현재인덱스로 변경
                    }
                }
                else //자식이 없는 경우
                {
                    break;//반복 종료
                }
            }
            return rootNode.element;//보관한 root노드 출력
        }
    }
}

선입후출(FILO), 후입선출(LIFO) 방식의 자료구조이다. 가장 최근에 입력된 순서대로 처리해야 하는 상황에 이용한다.

<스택 구현>

스택은 리스트를 사용법만 달리하여 구현 가능

  - 삽입 -
          top                      top
           ↓                        ↓
  ┌─┬─┬─┬─┬─┬─┬─┬─┐      ┌─┬─┬─┬─┬─┬─┬─┬─┐
  │1│2│3│4│5│ │ │ │  => │1│2│3│4│5│6│ │ │
  └─┴─┴─┴─┴─┴─┴─┴─┘      └─┴─┴─┴─┴─┴─┴─┴─┘

  - 삭제 -
            top                  top
             ↓                    ↓
  ┌─┬─┬─┬─┬─┬─┬─┬─┐      ┌─┬─┬─┬─┬─┬─┬─┬─┐
  │1│2│3│4│5│6│ │ │  => │1│2│3│4│5│ │ │ │
  └─┴─┴─┴─┴─┴─┴─┴─┘      └─┴─┴─┴─┴─┴─┴─┴─┘

  static void Main(string[] args)
  {
      Stack<int> stack = new Stack<int>();

      for (int i = 0; i < 5; i++)
      {                                              // Push함수로 입력
          stack.Push(i);                          // 입력순서 : 0, 1, 2, 3, 4
      }
                                                  // Peek함수로 다음으로 출력 될 최상단 값 확인
      Console.WriteLine(stack.Peek());            // 최상단 : 4

      for (int i = 0; i < 3; i++)
      {                                              // Pop함수로 출력
          Console.WriteLine(stack.Pop());         // 출력순서 : 4, 3, 2
      }

      for (int i = 5; i < 10; i++)
      {
          stack.Push(i);                          // 입력순서 : 5, 6, 7, 8, 9
      }

      while (stack.Count > 0)
      {
          Console.WriteLine(stack.Pop());         // 출력순서 : 9, 8, 7, 6, 5, 1, 0
      }
  }

어댑터 패턴(Adapter)

한 클래스의 인터페이스를 사용하고자 하는 다른 인터페이스로 변환하는 것을 의미한다.

<List의 기능을 사용해 Stack의 기능을 구현>

 public class Stack<T> // Stack 클래스 생성, 자료형 일반화
 {
     private List<T> container; // 입력값을 담을  List container 생성 

     public Stack()  //Stack 생성자 함수
     {
         container = new List<T>(); //List 인스턴스 생성
     }
     public int Count { get { return container.Count; } }//Count 변수로 List의 갯수 container.Count 참조

     public void Push(T item) //Push함수로 item 입력 기능 구현
     {
         container.Add(item); //List container에 item 추가
     }

     public T Pop() //Pop함수로 item 출력 기능 구현
     {
         T item = container[container.Count - 1]; //List container에 마지막으로 입력된 값을 item에 입력
         container.RemoveAt(container.Count - 1); //List container에 마지막으로 입력된 값을 제거
         return item; //item에 입력된 값 출력
     }

     public T Peek() //Peek함수로 다음으로 출력될 값 확인하는 기능 구현
     {
         return container[container.Count - 1]; //container에 마지막으로 입력된 값 출력
     }
 }

큐(Queue)

선입선출(FIFO), 후입후출(LILO) 방식의 자료구조이다. 입력된 순서대로 처리해야 하는 상황에 이용한다.

<큐 구현>

 1. 배열 사용
 선입선출(FIFO), 후입후출(LILO) 을 구현하기 위해 배열을 생성하고 순차적으로 데이터를 배치
     ┌─┬─┬─┬─┬─┬─┬─┬─┐
  앞 │1│2│3│4│5│ │ │ │  뒤
     └─┴─┴─┴─┴─┴─┴─┴─┘

 - 삽입 -
 비어있는 가장 뒷쪽에 데이터를 배치
  ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐
  │1│2│3│4│5│ │ │ │   =>  │1│2│3│4│5│6│ │ │
  └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘

 - 삭제 -
 가장 앞쪽 데이터를 출력하고 빈자리를 채우기 위해 나머지 데이터를 앞당기기 진행
  ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐
  │1│2│3│4│5│6│ │ │   =>  │2│3│4│5│6│ │ │ │
  └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘

 - 문제발생 -
 큐의 삭제 과정시 나머지 데이터를 앞당겨야하는 N번의 작업 발생
  ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬──┬─┬─┬─┬─┬─┐
  │1│2│3│4│5│6│ │ │   =>  │ │2│3│4│5│6│ │ │   =>   │2│3│4│5│6│ │ │ │
  └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴──┴─┴─┴─┴─┴─┘

 2. 전단 & 후단
 삽입 & 삭제 시 데이터를 앞당기지 않고 head와 tail을 표시하여 삽입할 위치와 삭제할 위치를 지정

 - 삽입 -
 tail 위치에 데이터를 추가하고 tail을 한칸 뒤로 이동
     h      t               h        t
     ↓      ↓               ↓        ↓      
  ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐
  │ │2│3│4│5│ │ │ │   =>  │ │2│3│4│5│6│ │ │
  └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘

 - 삭제 -
 head 위치에 데이터를 추가하고 head을 한칸 뒤로 이동
     h        t               h      t
     ↓        ↓               ↓      ↓
  ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐
  │ │2│3│4│5│6│ │ │   =>  │ │ │3│4│5│6│ │ │
  └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘

 - 문제발생 -
 큐의 배열 마지막 위치까지 사용하는 경우 빈자리가 없어 저장 불가한 상황 발생
       h        t             h          t
       ↓        ↓             ↓          ↓
  ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐
  │ │ │3│4│5│6│7│ │   =>  │ │ │3│4│5│6│7│8│
  └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘

 3. 순환배열
 배열의 끝까지 도달하여 빈자리가 없을 경우 처음으로 돌아가서 빈공간을 활용

 - 마지막위치 도달시 -
 다시 가장 앞 위치를 사용하여 빈공간을 재활용
         h     t         t       h           
         ↓     ↓         ↓       ↓           
 ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐
 │ │ │ │ │5│6│7│ │   =>  │ │ │ │ │5│6│7│8│
 └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘

 - 문제발생 -
 tail이 head을 침범하는 경우 모든 공간이 비어있는 상황과 가득차 있는 상황을 구분할 수 없음

         th                       th       
         ↓↓                       ↓↓       
 ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐
 │ │ │ │ │ │ │ │ │       │5│6│7│8│1│2│3│4│
 └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘
   비어있는 경우             가득찬 경우

 4. 포화상태확인
 head와 tail이 일치하는 경우를 비어있는 경우로 판정
 tail이 head 전위치에 있는 경우를 실제로는 한자리가 비어있지만 가득찬 경우로 판정
         th                    t h       
         ↓↓                    ↓ ↓       
 ┌─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┐
 │ │ │ │ │ │ │ │ │       │5│6│7│ │1│2│3│4│
 └─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┘
   비어있는 경우         가득찬 경우(로 판정)

        static void Main(string[] args)
        {
            Queue<int> queue = new Queue<int>();

            for (int i = 0; i < 5; i++)
            {                                           // Enqueue함수로 입력
                queue.Enqueue(i);                       // 입력순서 : 0, 1, 2, 3, 4
            }
                                                        // Peek함수로 다음 출력될 값 확인
            Console.WriteLine(queue.Peek());            // 다음순서 : 0

            for (int i = 0; i < 3; i++)
            {                                           // Dequeue함수로 출력
                Console.WriteLine(queue.Dequeue());     // 출력순서 : 0, 1, 2
            }

            Console.WriteLine(queue.Peek());            // 다음순서 : 3

            for (int i = 5; i < 10; i++)
            {
                queue.Enqueue(i);                       // 입력순서 : 5, 6, 7, 8, 9
            }

            Console.WriteLine(queue.Peek());            // 다음순서 : 3

            while (queue.Count > 0)
            {
                Console.WriteLine(queue.Dequeue());     // 출력순서 : 3, 4, 5, 6, 7, 8, 9
            }
        }
    }
}

<Queue 기능구현>

public class Queue<T> //클래스 Queue 생성, 자료형 일반화
{
    private const int DefaultCapacity = 4; //상수로 기본크기 생성

    private T[] array; //array 생성
    private int head;  //head 생성
    private int tail;  //tail 생성
    private int Count; //Count 생성
    public Queue() // 생성자 함수
    {
        array = new T[DefaultCapacity]; //배열 기본크기 초기화
        head = 0; //head 0초기화
        tail = 0; //tail 0초기화
        Count = 0; //Count 0초기화
    }
    public void Clear() //Queue를 초기화시키는 함수
    {
        array = new T[DefaultCapacity];
        head = 0;
        tail = 0;
        Count = 0;
    }
    public void Enqueue(T item) //Enqueue함수로 아이템 입력 구현
    {
        if (IsFull()) //배열이 전부 차있을 떄
        {
            Grow(); //배열의 크기를 늘려준다.
        }
        array[tail] = item; //현재 tail 위치에 item 입력
        tail++; // tail을 다음 칸으로 이동
        if(tail == array.Length) //tail이 배열의 마지막 위치에 있을 때는                     
        {
            tail = 0;        //다음 칸이 아닌 처음 칸으로 이동
        }
        Count++; //Count 1증가
    }
    public T Dequeue() //Dequeue 함수로 아이템 출력 구현
    {
        if (Count == 0) // 가지고 있는 값이 없을 때 출력하려고 하면
            throw new InvalidOperationException(); //예외처리

        T item = array[head];//head 위치의 값을 item에 입력
        head++;//head를 다음칸으로 이동
        if(head == array.Length) //head가 배열의 마지막 위치라면
        {
            head = 0;            //처음 칸으로 이동
        }
        Count--;              //Count 1감소
        return item; //head에서 꺼낸 item 출력
    }
    public T Peek() //Peek 함수로 다음 출력 될 head값 확인
    {
        if (IsEmpty()) //배열이 비어있는 경우 예외처리
            throw new InvalidOperationException();

        return array[head]; //head 값 확인
    }
    private void Grow() //배열이 다 채워졌을 때를 대비한 배열 늘리기
    {
        T[] newArray = new T[array.Length * 2];//기존 배열의 2배크기 newArray 생성

        if (head < tail) // head가 tail보다 앞에 있을 때 
        {
            Array.Copy(array, head, newArray, 0, tail);//처음부터 끝까지 복사
        }
        else // tail이 head보다 앞에 있을 때 그대로 복사하는게 아닌
             // head부터 끝까지 복사
             // 처음부터 tail까지 복사
        {
            Array.Copy(array, head, newArray, 0, array.Length - head);
            Array.Copy(array, 0, newArray, array.Length - head, tail);
        }
        array = newArray; //array에 newArray 크기 대입
        tail = Count; //tail은 마지막위치
        head = 0; //head는 처음위치를 가리키도록
    }
    private bool IsFull() // 배열이 다 채워졌을 때
    {
        if (head > tail)
        {
            return head == tail + 1; //head가 tail 앞칸에 있을 때 가득 찬 것으로 판정
        }
        else
        {
            return head == 0 && tail == array.Length - 1; //head가 맨 앞일 때 tail이 마지막일 때도 가득 찬 것으로 판정
        }
    }
    private bool IsEmpty() // 배열이 비어있는 경우
    {
        return head == tail; //head와 tail이 같은 위치에 있을 때
                             //비어있다고 판정
    }
}

문제를 해결하기 위해 정해진 진행절차나 방법을 의미하며, 컴퓨터에서 알고리즘이란 어떠한 행동을 하기 위해서 만들어진 프로그램 명령어의 집합이다.

<알고리즘 조건>

1. 입력 : 알고리즘은 0개 이상의 입력을 가져야 함
2. 출력 : 알고리즘은 최소 1개 이상의 결과를 가져야 함
3. 명확성 : 수행 과정은 모호하지 않고 정확한 수단을 제공해야 함
4. 유한성 : 수행 과정은 무한하지 않고 유한한 작업 이후에 정지해야 함
5. 효과성 : 모든 과정은 명백하게 실행 가능해야 함

자료구조(DataStructure)

프로그래밍에서 데이터를 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리 저장을 의미한다. 데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령을 의미한다.

<자료구조 형태> 선형구조 : 자료 간 관계가 1 대 1인 구조 배열, 연결리스트, 스택, 큐, 덱 비선형구조 : 자료 간 관계가 1 대 다 혹은 다 대 다인 구조 트리, 그래프

알고리즘 성능

효율적인 문제해결을 위해선 알고리즘의 성능을 판단하 수 있는 기준이 필요하다. 상황에 따라 적합한 알고리즘을 선택할 수 있도록 하는 기준이다.

<알고리즘 평가 기준> 컴퓨터에서 알고리즘과 자료구조의 평가는 시간과 공간 두 자원을 얼마나 소모하는지가 효율성의 중점을 둔다. 일반적으로 시간을 위해 공간이 희생되는 경우가 많다. 시간복잡도 : 알고리즘의 시간적 자원 소모량 공간복잡도 : 알고리즘의 공간적 자원 소모량

<Big-O 표기법> 알고리즘의 복잡도를 나타내는 점근표기법으로 이터 증가량에 따른 시간 증가량을 계산한다. 가장 높은 차수의 계수와 나머지 모든 항을 제거하고 표기하며 고리즘의 대략적인 효율을 파악할 수 있는 수단으로 사용한다.

 int Case1(int n) //n을 n곱한다
 {
     int sum = 0;
     sum = n * n;
     return sum;
 }
 int Case2(int n) //n을 n번만큼 더한다
 {
     int sum = 0;
     for (int i = 0; i < n; i++)
         sum += n;
     return sum;
 }
 int Case3(int n) //1을 n만큼 더하는 것을 n만큼 더한다.
 {
     int sum = 0;
     for (int i = 0; i < n; i++)
         for (int j = 0; j < n; j++)
             sum++;
     return sum;
 }

 // 입력값       Case1        Case2          Case3
// n = 1            1           1              1
// n = 10           1          10            100
// n = 100          1         100         10,000
// n = 1000         1        1000      1,000,000
// Big-O         O(1)         O(n)          O(n²)

// ex) 0(n+3) → +3 중요성 낮음
//     0(2n²+2) → n²이 작업량에 따라 시간복잡도의 증가폭을 결정하는 핵심으로 나머지 항은 무시

<수행 시간 분석> 알고리즘의 성능은 상황에 따라 수행 시간이 달라지는데, 수행 시간을 분석하는 경우 평균의 상황과 최악의 상황을 기준으로 평가한다. 최선의 상황의 경우 알고리즘의 성능을 분석하는 수단으로 적합하지 않다.

int FindIndex(int[] array, int value) //배열 array에서 값 value 찾기
{
    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] == value)
            return i;
    }
    return -1;
}
// 최선   평균               최악
// O(1)   O(n/2)→0(n)       O(n)

프로그래밍 언어에서는 일반적인 수학 연산과 유사한 연산자들이 지원된다. c#에서는 여러 연산자를 제공하며 기본 연산을 수행할 수 있다.

산술 연산자

<이진 연산자>

//변수 생성
 bool b = false;
 int i = 0;
 float f = 0.0f;

 i = 1 + 2;     // +(더하기)
 i = 3 - 1;     // -(빼기)
 i = 4 * 2;     // *(곱하기)
 f = 5f / 3f;   // /(나누기) : 주의! 5 / 3 과 같이 int의 나눗셈은 소수점을 버림
 i = 13 % 3;    // %(나머지)

<단항 연산자>

 i = +i;   // + 단항연산자(양수)  : 값을 그대로 반환
 i = -i;   // - 단항연산자(음수)  : 값의 마이너스를 변환, 2의 보수로 만든다.
 ++i;           // ++ 전위증가연산자   : 값을 1 증가
 i++;           // ++ 후위증가연산자   : 값을 1 증가
 --i;           // -- 전위감소연산자   : 값을 1 감소
 i--;           // -- 후위감소연산자   : 값을 1 감소

<전위연산자와 후위연산자>

// 전위연산자 : 값을 반환하기 전에 연산
i = 0;
Console.WriteLine(i);   // output : 0
Console.WriteLine(++i); // output : 1
Console.WriteLine(i);   // output : 1
// 후위연산자 : 값을 반환한 후에 연산
i = 0;
Console.WriteLine(i);   // output : 0
Console.WriteLine(i++); // output : 0
Console.WriteLine(i);   // output : 1

대입 연산자

<대입 연산자>

i = 10;        // = : 오른쪽의 값을 왼쪽 변수에 대입

<복합 대입 연산자>

//이진 연산자(op)의 경우
// x op= y 는 x = x op y 와 동일
i += 5;        // i = i + 5; 와 동일

비교 연산자

<비교 연산자>

b = 3 > 1;     // >  : 왼쪽 피연산자가 더 클 경우 true
b = 3 < 1;     // <  : 왼쪽 피연산자가 더 작을 경우 true
b = 3 >= 1;    // >= : 왼쪽 피연산자가 더 크거나 같은 경우 true
b = 3 <= 1;    // <= : 왼쪽 피연산자가 더 작거나 같은 경우 true
b = 3 == 1;    // == : 두 피연산자가 같은 경우 true
b = 3 != 1;    // != : 두 피연산자가 다를 경우 true

논리 연산자

<논리 연산자>

b = !false;            // !(Not)  : true →false, false→true
b = true && false;     // &&(And) : 두 데이터 모두 true 일 경우 true
b = true || false;     // ||(Or)  : 둘 중 하나라도 true 일 경우 true
b = true ^ false;      // ^(Xor)  : 두 데이터가 다를 경우 true

<조건부 논리 연산자>

// 조건부 논리 And 연산자 &&
// 빠른 계산을 위해 false && x(논리자료형) 의 경우 어떠한 논리자료형이 있어도
// 결과는 항상 false이기 때문에 false && x 에서 x는 무시하게 됨
iValue = 10;
bValue = false && (++iValue > 5);
Console.WriteLine(iValue);  // output : 10

// 조건부 논리 Or 연산자 ||
// 빠른 계산을 위해 true || x(논리자료형) 의 경우 어떠한 논리자료형이 있어도
// 결과는 항상 true이기 때문에 true || x 에서 x는 무시하게 됨
iValue = 10;
bValue = true || (++iValue > 5);
Console.WriteLine(iValue);  // output : 10

비트 연산자

＊컴퓨터 친화적인 연산으로 다른 연산에 비해 속도가 빠르다.

<단항 연산자>

i = ~0x35;         // ~(비트 보수) : 데이터를 비트단위로 보수 연산 (보수 : 0->1, 1->0)

<이진 연산자>

i = 0x11 & 0x83;   // &(And) : 데이터를 비트단위로 And 연산
// 0001 0001  
// 1000 0011   &는 겹치는 것만 연산
// 0000 0001
// output: 0x01 or 1
Console.WriteLine(i);

i = 0x11 | 0x83;
// 0001 0001
// 1000 0011  |는 하나만 있어도 연산
// 1001 0011
// output: 0x93 or 147 
Console.WriteLine(i);// |(Or)  : 데이터를 비트단위로 Or 연산
i = 0x11 ^ 0x83;   // ^(Xor) : 데이터를 비트단위로 Xor 연산

<비트 쉬프트 연산자>

iValue = 0x20 << 2;     // << : 데이터의 비트를 입력값 만큼 왼쪽으로 이동
iValue = 0x20 >> 2;     // >> : 데이터의 비트를 입력값 만큼 오른쪽으로 이동
// 왼쪽으로 1만큼 이동했을 때 *2와 같다.
// 오른쪽으로 1만큼 이동했을 때 /2와 같다.
// 100/2 → 100*0.5 → 100>>1 같은 계산이지만 오른쪽으로 갈수록 훨씬 연산속도가 빠르다.

연산자 우선순위

여러 연산자가 있는 식에서 우선 순위가 높은 연산자가 먼저 계산

<연산자 우선순위>

// 1. 기본 연산        : a[i], x++, x--
// 2. 단항 연산        : +x, -x, !x, ~x, ++x, --x, (Type)x
// 3. 곱하기 연산      : x * y, x / y, x % y
// 4. 더하기 연산      : x + y, x - y
// 5. 시프트 연산      : x << y, x >> y
// 6. 비교 연산        : x < y, x > y, x <= y, x >= y
// 7. 같음 연산        : x == y, x != y
// 8. 논리 AND 연산    : x & y, x && y
// 9. 논리 XOR 연산    : x ^ y
// 10. 논리 OR 연산    : x | y, x || y
// 11. 대입 연산       : x = y, x op= y

1.1+0.1이 1.2가 아니라는게 무슨 의미일까, 설명에 앞서 코드를 확인해 보겠다.

static void Main()
{
    if(1.1+0.1==1.2)
    {
        Console.WriteLine("맞음");
    }
    else
    {
        Console.WriteLine("틀림"); // output : 틀림
    }
}

이와 같이 틀림이 출력되는 이유를 이해하려면 부동소수점을 알 필요가 있다.

●부동소수점

고정소수점

부동 소수점이 있다면 반대되는 고정소수점 또한 존재한다. 고정소수점과 부동소수점의 차이는 말 그대로 소수점의 위치에 따라 나뉜다. 해당 그림과 같이 고정소수점의 경우 32bit를 정확히 반으로 나누고 맨 앞자리를 부호에 사용하는 형태로 소수점의 위치는 고정된다.

직관적이고 쉬운 방법이지만, 소수점이 고정인 만큼 표현할 수 있는 수의 범위는 약 -3만~+3만 정도가 최대이다.

부동소수점

반대되는 부동소수점의 경우 소수점의 위치가 비교적 자유롭다. 예를 들어, 0.000001 → 1x10^-6 이런식으로 표현이 가능하다는 의미이다.

자세히 알아보면 다음과 같이 표현되는데

지수x2^가수

고정소수점과 같은 32bit여도 훨씬 넓은 범위의 수를 표현할 수 있기 때문에 사용되는 것이다.

●1.1 + 0.1이 1.2가 아닌 이유

이 때 발생되는 문제가 처음 얘기한 내용인데, 컴퓨터가 2진수로 0.1을 표현할 방법이 없기 때문이다. 2^-4(0.0625)+2^-5(0.03125)+... 이와 같이 최대한 0.1과 근사치를 만들어 사용할 뿐 정확한 0.1은 아니기에 컴퓨터는 1.1+0.1==1.2 가 아니라고 판단하는 것이다.