게임 개발 낙서장

아나그램이란? 같은 문자로 이루어진 문자열이지만, 문자들의 정렬이 다른 경우 ( HelloWorld / WrlodHolle) 소스코드 public class Anagram_Source : MonoBehaviour { void Start() { string inputstr = "HelloWorld"; string inputstr2 = "WrlodHolle"; Debug.Log(AnagramChecker(inputstr, inputstr2)); } bool AnagramChecker(string input1, string input2) { //공백 제거 input1 = input1.Replace(" ", ""); input2 = input2.Replace(" ", ""); //1차적으로 길이로 판단 if(i..

문제 10번 동안 1~10까지 랜덤한 숫자를 출력하여 중복된 숫자가 있을 경우 true, false를 리턴하라 랜덤함수 범위만 지정해주면 되는 간단한 문제 소스코드 public class RandomQuiz_Source : MonoBehaviour { const int MAX = 10; void Start() { int[] data = new int[MAX]; int n = MAX; while (0 < n) { Debug.Log(RandomQuiz(data)); n--; } } bool RandomQuiz(int[] data) { RandomData_Init(data); for (int i = 0; i < data.Length; i++) { for(int j = 0; j < data.Length; j++..

개념 과정 참고 : marobiana.tistory.com/80 재귀 호출 과정이 생각보다 복잡해서 이미지 메이킹이 어려운데 해당 포스팅에서 쉽게 설명해주고 있다. 일반 재귀 vs 메모이제이션 재귀 피보나치 구현 시, 일반 재귀 코드는 문제가 있다. 이미 계산한 내용을 또 다시 계산을 하기 때문에 필요없는 연산이 생긴다. 예를들어, n = 5 일때, fibo(1) fibo(2) fibo(1) + fibo(2) fibo(2) + (fibo(1) + fibo(2)) (fibo(1) + fibo(2)) + (fibo(2) + (fibo(1) + fibo(2))) 위와 같이 전에 계산한 값을 매번 다시 계산을 한다. n이 매우 커질 경우 오버헤드가 너무 크다. 실제로 n = 30을 넣어보면, 결과가 안나오거나 ..

개념 Merge sort는 분할정복법을 사용하여 정렬하는 알고리즘이다. 1) 분할: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 2) 정복: 각각의 작은 문제를 순환적으로 해결 3) 합병: 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함 출처: https://excelsior-cjh.tistory.com/47 [EXCELSIOR] 과정 장점 퀵 정렬과 비슷하게 원본 배열을 절반씩 분할해가면서 정렬하는 정렬법으로써 분할하는 과정에서 logNlogN 만큼의 시간이 소요된다. 즉, 최종적으로 보게되면 N×logNN×logN이 된다. 또한 퀵 정렬과 달리 기준값을 설정하는 과정없이 무조건 절반으로 분할하기에 기준값에 따라 성능이 달라지는 경우가 없다. 따라서 항상 O(N×logN)..

개념 하나의 정점으로부터 시작하여 인접한 노드를 모두 방문하고 차례대로 모든 정점들을 한 번씩 방문하는 알고리즘 과정 장점 장점으로는, 출발노드에서 목표노드까지의 최단 길이 경로를 보장합니다. (물론 모든 간선의 가중치가 동일할 경우입니다.) 단점 단점으로는, 최악의 경우 모든 노드에 대한 정보를 위한 공간을 요구한다는 것입니다. 따라서 최대 저장공간을 크게 잡아야 합니다. 또한 목표노드가 깊은 단계에 있을 경우 오랜 시간이 소요됩니다. 시간복잡도 인접 행렬 : O(V^2) 인접 리스트 : O(V+E) 소스코드 - 인접리스트 public class BreadthFirstSearch_Source : MonoBehaviour { void Start() { int n = 5; // 정점의 개수 int m = ..

개념 BFS와는 다르게 루트 노드 혹은 임의의 노드와 인접한 노드를 모두 탐색하는 것이 아니라, 연결된 정점들을 차례대로 한번씩 방문하는 알고리즘이다. 즉, 이름과 같이 넓게 탐색하기 이전에 깊게 탐색하는 알고리즘이다. 과정 장점 장점으로는, 현 경로상의 노드들만 기억하면 되므로 그래프의 높이 만큼의 공간만을 요구합니다. 따라서 최대 저장공간의 수요가 비교적 적습니다. 또한, 목표노드가 깊은 단계에 있을 경우에 해를 빠르게 구할 수 있습니다. 단점 단점으로는, 해가 없는 경로에 깊이 빠질 가능성이 있다는 것입니다. 또한 얻어진 해가 최단 경로가 된다는 보장이 없습니다. (목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이 때 얻어진 해는 최적의 해가 아닐 수 ..

개념 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다. 과정 오름차순으로 정렬된 배열이 있다. { 17, 28, 43, 67, 88, 92, 100 } 이 배열에서 이진 탐색을 이용하여 43의 값을 찾아보자. 첫 번째 시도 우선 가운데에 위치한 임의의 값 67을 선택한다. 선택한 값 67과 찾고자 하는 값 43를 비교한다. 43 < 67 이므로 43은 67의 좌측에 ..

개념 Insertion Sort는 Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘이다. Insertion Sort는 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘이다. 최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다. 과정 정렬은 2번째 위치(index)의 값을 temp에 저장한다. temp와 이전에 있는 원소들과 비교하며 삽입해나간다. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다. 시간복잡도 최악의 경우(역으로 정렬되어 있을 경우) Selection Sort..

개념 Selection Sort는 Bubble Sort과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 과정 주어진 배열 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. (pass) 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 시간복잡도 데이터의 개수가 n개라고 했을 때, 첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1 두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2 ... (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다. 최선, 평균,..

개념 Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다. 과정 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 시간복잡도 주어진 배열 안에서 교환(swap)을 통해..