|    종 이    |

📖 Study Memo 📖

[TIL] 21 탐색알고리즘. 그래프(Graph), 유니티 ⭐⭐⭐

업데이트:

카테고리:

태그: , ,

BFS DFS Graph



개인공부, 유니티 3일차

   [o] 9시 ~ 10시 알고리즘 문제 25~27
   [o] c# 5강듣기
   [o] 유니티 강의 듣기 1-6부터 다시 듣기
   [o] 2시 객체지향 강의
   [o] 4시 반 OT
   [o] 강의 못들은거 1 정리, 1개 다시듣기.
   주말에 알고리즘 과제 풀어보기.






1. 탐색 알고리즘

주어진 데이터 집합에서 특정 항목을 찾는 방법을 제공

배열의 각 요소를 하나씩 차례대로 검사

int SequentialSearch(int[] arr, int target)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == target)
        {
            return i;
        }
    }

    return -1;
}

배열에서 빠르게 원하는 항목을 찾는 방법
중간 요소와 찾고자 하는 항목을 비교하여 대상이 중간 요소보다 작으면 왼쪽을, 크면 오른쪽을 탐색

int BinarySearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (arr[mid] == target)
        {
            return mid;
        }
        else if (arr[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    return -1;
}






2. 그래프 (Graph)

정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조
방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉨
가중치 그래프(Weighted Graph)는 간선에 가중치가 있음

탐색방법

깊이 우선(DFS)

Depth-First Search
dfs

너비 우선(BFS)

Breadth-First Search
bfs

그래프, DFS, BFS 예제

Graph, DFS, BFS 
using System;
using System.Collections.Generic;

public class Graph
{
    private int V; // 그래프의 정점 개수
    private List<int>[] adj; // 인접 리스트

    public Graph(int v)
    {
        V = v;
        adj = new List<int>[V];
        for (int i = 0; i < V; i++)
        {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    public void DFS(int v)
    {
        bool[] visited = new bool[V];
        DFSUtil(v, visited);
    }

    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true;
        Console.Write($"{v} ");

        foreach (int n in adj[v])
        {
            if (!visited[n])
            {
                DFSUtil(n, visited);
            }
        }
    }

    public void BFS(int v)
    {
        bool[] visited = new bool[V];
        Queue<int> queue = new Queue<int>();

        visited[v] = true;
        queue.Enqueue(v);

        while (queue.Count > 0)
        {
            int n = queue.Dequeue();
            Console.Write($"{n} ");

            foreach (int m in adj[n])
            {
                if (!visited[m])
                {
                    visited[m] = true;
                    queue.Enqueue(m);
                }
            }
        }
    }
}

public class Program
{
    public static void Main()
    {
        Graph graph = new Graph(6);

        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(2, 3);
        graph.AddEdge(2, 4);
        graph.AddEdge(3, 4);
        graph.AddEdge(3, 5);
        graph.AddEdge(4, 5);

        Console.WriteLine("DFS traversal:");
        graph.DFS(0);
        Console.WriteLine();

        Console.WriteLine("BFS traversal:");
        graph.BFS(0);
        Console.WriteLine();
    }
}






3. 최단 경로 알고리즘 (Sortest path problem)

다익스트라 알고리즘
벨만 포드 알고리즘
A*알고리즘 등 많은 알고리즘이 존재한다.






4. 고급 알고리즘

문제를 푸는 방법들
문제를 풀 때 첫시작점


1. 동적 프로그래밍

작은 문제 단위로 쪼개서 반복
동적 프로그래밍은 큰 문제를 작은 하위 문제로 분할하여 푸는 접근 방식입니다.
동적 프로그래밍은 중복되는 하위 문제들을 효율적으로 해결하기 위해 사용됩니다.
동적 프로그래밍은 최적 부분 구조와 중복 부분 문제의 특징을 가진 문제들을 효과적으로 해결할 수 있습니다.



2. 그리드 알고리즘

현재에 집중하는
그리디 알고리즘은 각 단계에서 가장 최적인 선택을 하는 알고리즘입니다.
각 단계에서 가장 이익이 큰 선택을 하여 결과적으로 최적해에 도달하려는 전략을 따릅니다.
동적 프로그래밍은 최적 부분 구조와 중복 부분 문제의 특징을 가진 문제들을 효과적으로 해결할 수 있습니다.



3. 분할 정복

작은 부분부터 착실히 해결
재귀적인 구조를 가지므로 문제 해결 방법의 설계가 단순하고 직관적






5. 문제 해결 전략

   1. 문제이해
   2. 예제와 테스트 케이스
   3. 알고리즘 설계
   4. 코드 작성
   5. 효율성
   6. 디버깅과 테스트
   7. 시간 관리
   8. 연습과 경험

연습문제 - 백준, 프로그래머스

문제종류

   1. 탐색과 정렬
   2. 그래프
   3. 동적 프로그래밍
   4. 그리디 알고리즘
   5. 분할 정복
   6. 동적 그래프
   7. 문자열 처리
   8. 기타











6. 유니티 강의 메모


단축키, 설정

  • 비쥬얼 스튜디오 단축키 ctrl k c : 주석, ctrl k u : 주석해제
  • 유니티 씬뷰 단축키 Q W E R T
    image
  • 오브젝트 생성 시 리셋하기 습관
    image
  • 텍스트 생성 시 text canvas scaler - screen size 확인
    image


유니티 실행순서


Physic Material

  • rigidbody의 재질은 실질적인 재질 (보여지는 재질 x)
    image
  • dynamic friction : 이미 움직이고 있을 때 마찰 0 ~ 1
  • static friction : 정지 시 마찰 0 ~ 1
  • bounciness : 1이면 에너지 손실 없이 바운스


Update

  • update는 프레임 단위. 다른 프레임의 화면마다 한프레임의 초가 달라진다.
  • Time.deltaTime = 1/프레임 초
  • update에서 코드에 * Time.deltaTime 로 다른 프레임의 환경에서도 동일하게 실행.


좌표, 벡터

  • 월드 좌표 : 전체적 좌표 기준 .Position
  • 로컬 좌표 : 부모의 좌표 기준 .LocalPosition
  • Vector2.normalized 크기 1로 반환 -> 대각선 움직임 시 동일한 속도로 움직이기 위해 사용


직렬화

  • [Header(“제목”)] 제목정하기
  • [SerializeField] -> private일 때 인스펙터 뷰에 보이게
    image
[Header("헤더 사용")]
public int a = 0;
public int b = 0;
[Header("seriallizefield, private")]
[SerializeField] private int c = 0;
[Range (0.5f, 1.5f)] //슬라이더 형식
public float d = 0;


이동 INPUT 패키지

  • input 패키지 사용해서 캐릭터 이동 코드 event Action 구독 호출 패턴 캡처
  • MOVE -> 키보드 W A S D 로 INPUT을 받아 OnMove 실행
public void OnMove(InputValue value) // 
{       
    Vector2 moveInput = value.Get<Vector2>();
    CallMoveEvent(moveInput);
    
}

input



타일맵

  • 이미지 팔레트에 드래그
  • tilemap 종류별로 생성 후 그리기
  • tilemap Collider 컴포넌트 확인

타일맵
docs
image



각도, mathf

RotaeArm

private void RotaeArm(Vector2 direction)
{
    float rotZ = Mathf.Atan2(direction.y,direction.x) * Mathf.Rad2Deg;

    armRenderer.flipY = Mathf.Abs(rotZ) > 90f;
    characterRenderer.flipX = armRenderer.flipY;
    armPivot.rotation = Quaternion.Euler(0,0,rotZ);
}

Atan2(y,x) -> y,x tan 를 이용하여 각도 값 구하기(0~3.14)
mathf.Rad2Deg 를 곱해주면 우리가아는 0 ~ 180도 로 변환된다.
mathf.abs -> 절대값

flipx => x뒤집기
image


mathf

mathf

// 절댓값
Mathf.Abs(float num) 

// min(최소값)과 max(최대값) 범위 안에서 value값을 반환해준다.
Mathf.Clamp(float num, float min, float max)    

// value값이 Max(최대값)에 도달하게 되면 -값이 되고 0이 되면 다시 Max(최대값)까지 +
Mathf.PingPong(float value, float Max)

// 올림 버림 반올림
Mathf.Cell(float num)
Mathf.Floor(float num)
Mathf.Round(float num)

//시작점(from)과 종료점(to) 사이의 보간값(0과 1사이의 실수값)(t)에 해당하는 값을 반환
// 값을 부드럽게 변환
Mathf.Lerp(float from, float to, float t)

//lerp와 비슷하지만 가속도가 있다.
Mathf.SmoothStep(float from, float to, float t)



Instantiate

Instantiate(prefab, transform 부모) 부모 아래에 생성
image


Instantiate(prefab, Vector Position, rotation) 부모x 생성 image






7. 객체지향

객체지향 강의 정리 추상화 - 객체의 공통적인 속성과 기능을 추출하여 정의하는것.
상속 - 기존 클래스를 재활용 해 새로운 클래스 만듬, 반복코드 최소화.
다형성 - 메서드 오버라이딩과 메서드 오버로딩.
캡슐화 - private, public 등을 이용해 정보보호.

SOLID원칙

SRP(단일책임의 원칙) 한 클래스는 최소한의 기능만 갖는다.
OCP(개방폐쇄의 원칙) 확장에 대해 개방, 수정 폐쇄적.
LSP(리스코프 치환 원칙) 하위클래스는 인터페이스의 규약을 지켜야한다. 설계 많이해보기.
ISP(인터페이스 분리 원칙) 병용 인터페이스 하나 보다는 여러개의 인터페이스 분리가 더 좋다, 다중상속으로 사용.
DIP(의존관계 역전 원칙) 특정 클래스를 할당 X -> 부모,인터페이스를 사용하라 (편집됨)






정리, 잡담

C# 알고리즘 강의
생각하고 코드에 활용은 못할 거 같다.
이런 게 있구나 하고 넘어가야겠다.
다음에 또 보면 다시 이해 해보자.
주말에 알고리즘 과제 풀어보기.

객체지향
클래스 사이에서 값 주고받고, 클래스의 중심으로 생각하기.

1120강의
메타인지
악에 받친 사람
오늘 할 일은 오늘 하자.
메타인지 -> 질문
업무의 전문성을 키우자.
기능이 아닌 서비스를 개발하는 사람.
커뮤니케이션 - 겸손
코드 : SOLID, 코드컨벤션, 예측가능코드, 변수명 (좋은코드를 짜자)
나의 무기를 단련해 나가야 한다.
책 타이탄의 도구들



[Unity] TIL 21


참고 : 유니티 TOP

📔

댓글남기기





최근 글 10 개