극꼼이 이야기 (GG_Tales)

1. 더티 플래그(Dirty Flag)란? : 간단하게 말하면, 불필요한 동작을 피하기 위해 변경된 값에 '더티'라는 플래그를 세워놓고, 실제 그 작업이 필요할 때 플래그가 세워진 값들을 반영하는 것이다. 2. 더티 플래그의 장점 * 값이 변하지 않았을 때의 중복 계산을 피할 수 있음. 3. 더티 플래그의 용도 : 값이 사용되는 횟수보다 더 자주 변경되고, 점진적으로 업데이트하기 어려울 때. 계산이나 동기화에 사용됨. 유니티를 공부하던 도중 알게된 디자인패턴인데, 유니티는 더티 플래그가 설정되지 않은 오브젝트는 저장하지 않습니다. 예를 들어 ScriptableObject를 실행 중에 변경할 경우 이를 저장하지 않는데, 이는 EditorUtility.SetDirty(Object target) 으로 해결할 ..

1. 팩토리 메서드 패턴이란? 2. 팩토리 메서드 패턴의 장단점 3. 팩토리 메서드 패턴 예시 코드 1. 팩토리 메서드 패턴이란? : 객체를 생성하기 위한 인터페이스를 정의하는데, 어떤 클래스의 인스턴스를 만들지 서브클래스에서 결정하는 것입니다. 동일한 인터페이스를 준수하는 클래스들을 생성하는 것이 목적입니다. * 구조 Product Creator Product Creator Concrete ConcreteProduct ConcreteCreator - Product : 팩토리 메서드로 생성될 공용 객체. 주로 추상 클래스 또는 인터페이스 - ConcreteProduct : Product를 상속받는 객체 - Creator : Product가 구현하는 메서드가 존재. 주로 추상 클래스 또는 인터페이스 - C..

1. 싱글톤 패턴이란? 2. 싱글톤 패턴의 장단점 3. 싱글톤 패턴 예시 코드 1. 싱글톤 패턴(Singleton Pattern)이란? : 해당 클래스의 인스턴스가 하나만 생성되게 하고, 어디서든 그 인스턴스에 접근할 수 있도록 하는 패턴입니다. 주로 시스템 자원이나 정보를 관리하는 용도로 사용합니다. 2. 싱글톤 패턴의 장단점 * 장점 : 모든 데이터를 전역으로 관리하기 때문에 쉽게 접근할 수 있고, 초기 객체를 생성하게 되면 정적 메모리에 올라가기 때문에 호출이 빠릅니다. 중복 생성과 메모리 낭비를 방지할 수 있습니다. * 단점 : 정적 메모리(static)에 할당된 객체이기 때문에 메모리 크기가 제한적이라 너무 큰 메모리가 쌓이게 될 경우 프로그램의 성능이 낮아집니다. 하나의 정적 메모리를 사용하기..

: 문제를 해결하기 위해 확인하는 모든 경우를 전부 탐색하는 방법. 주로 DFS를 이용 - 단점 : 전부 탐색하기에 시간 복잡도가 높음 - (ex) 백 트래킹 * N과 M 문제 : N개 중 중복을 허용하는지/아닌지 + M개를 순서있게 나열하는지/고르는지 1) N개 중 중복을 허용 + M개를 순서있게 나열 https://geukggom.tistory.com/3 [백준] 15651번 : N과 M (3) 문제 : https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해 geukggom.tistory.com 2) N개 중 중복을 허용하지..

1. 백트래킹이란? 2. 백트래킹 예시(N-Queen) 1. 백트래킹이란? : 제약된 조건을 가진 문제에서 답을 찾기 위한 방법. - DFS 방식으로 확인(https://geukggom.tistory.com/66). - 모든 경우의 수를 상태 공간 트리를 통해 표현해 탐색. Promising : 해당 루트가 제약된 조건에 맞는지 확인 Pruning : 가지치기. Promising단계에서 조건에 맞지 않으면 바로 다른 루트로 가서 탐색 시간 절약. * 상태 공간 트리(State Space Tree) : 문제 해결 과정의 중간 상태를 Node로 나타낸 트리 2. 백트래킹 예시 백트래킹의 대표적인 문제 예시로는 N-Queen 문제가 있습니다. * N-Queen : 크기가 N * N인 체스판 위에 퀸 N개를 서..

저번 크루스칼 알고리즘 포스팅에 이어서, 최소 신장 트리를 찾는 대표 알고리즘인 프림 알고리즘에 대해 알아보겠습니다. * 크루스칼 알고리즘 https://geukggom.tistory.com/177 1. 프림 알고리즘이란? 2. 프림 알고리즘 구현 1. 프림 알고리즘이란? : 크루스칼 알고리즘과 마찬가지로 탐욕 알고리즘을 기반으로 하고 있습니다. 크루스칼 알고리즘과 차이점이 있다면, 크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택한다면, 프림 알고리즘은 특정 정점에서 시작해서 해당 정점에 연결된 가장 작은 가중치를 선택합니다. 2. 프림 알고리즘 구현 1) Edge 만들기 public class Edge : IComparable { public int weight; //가중치 public strin..

1. 최소 신장 트리 알고리즘 2. Disjoint Set (Union-Find, Union-by-Rank) 3. 크루스칼 알고리즘(Kruskal Algorithm) 1. 최소 신장 트리 알고리즘 : Minimum Spanning Tree(MST). * Spanning Tree : 그래프 내의 모든 정점을 포함하는 트리를 말합니다. 최소 신장 트리란 Spanning Tree 중 사용된 간선들의 가중치의 합이 최소인 트리입니다. 신장 트리에서 최소 신장 트리를 찾는 알고리즘에는 크루스칼 알고리즘, 프림 알고리즘이 있습니다. * 최소 신장 트리의 특징 1) 간선의 가중치의 합이 최소여야 함 2) n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 함 3) 사이클이 포함되어서는 안 됨 ..

1. 최단 경로 문제란? : 가장 짧은 경로 내의 두 노드를 찾는 문제입니다. 변마다 가중치가 있는데, 가중치의 합이 최소가 되도록 경로를 찾아야 합니다. 2. 우선순위 큐 : 일반적인 큐(Queue)가 FIFO(First In First Out)구조였던 것에 비해, 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조입니다. 너비우선탐색(BFS)과 유사하며, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내오는 방식으로, 최단 경로 문제를 푸는데 최적화 되어 있는 방법입니다. 저는 MinHeap 방식을 사용해 우선순위 큐를 구현할 것입니다. * Heap : https://geukggom.tistory.com/163 [C# 기초] #21. 힙(Heap) 1. 힙이란? : ..

1. 탐욕 알고리즘이란? : 매순간 최적이라고 생각되는 값을 선택하는 알고리즘입니다. 이렇게만 설명을 들으면 이해하기 어려울 수 있는데요, 아래 예시를 통해 어떤건지 더 자세히 알아봅시다. 2. 탐욕 알고리즘 예시 동전을 거슬러주는 함수를 만들어봅시다. coinList에는 큰 액수의 동전부터 들어가 있습니다. 탐욕 알고리즘은 아래와 같이 큰 액수의 동전부터 몇개 거슬러줄지 개수를 정합니다. public void coinFunc(int pric, List coinList) { int totalCount = 0; int nowPrice = pric; for (int i = 0; i < coinList.Count; i++) { int nowCount = nowPrice / coinList[i]; nowPric..

1. 순차 탐색 (Sequential Search) 데이터들을 하나씩 비교해서 원하는 데이터를 찾는 방법입니다. public int searchIndex(int data, List list) { if (list.Count == 0) return -1; for (int i = 0; i < list.Count; i++) { if (list[i] == data) //원하는 데이터를 찾음 return i; //단, 같은 데이터가 여러개 있어도 제일 앞에 있는 데이터의 index 리턴 } return -1; //원하는 데이터가 없을 경우 } 2. 이진 탐색(Binary Search) 데이터를 둘로 나누고, 둘 중 원하는 데이터가 있을만한 곳을 찾는 방법입니다. 순차 탐색과는 다르게 데이터들이 이미 정렬을 마친 상..