[TIL] 내일배움캠프_Unity 최종 프로젝트 3주차: 주요 메카닉 구현 9, 기술 면접 대비 15일차

팀 회의 내용

- DataManager 구조 분리

- 주요 메카닉 완성도 높이기

 

구현한 내용 

- DataManager 구조 분리로 인한 MarketSystem 구현 

 

현재 프로젝트의 UI는 각 패널마다 MVC 패턴을 이용한다 Model은 DataManager View는 각 패널 Controller는 각 패널마다 외부에서 통신하여 데이터를 받아 View에게 넘겨준다 이때, 각 패널들의 공통점은 모두 DataManager를 Model로 사용하고 있다 그래서 DataManager의 하는 일은 많아지고 역할이 모호해지기 시작하여 각 Model을 따로 만들어 분리하고 DataManager는 저장과 로드, 기본데이터만 가지고 있는 방식으로 변경하였다 

기술 면접 대비 16일차 

Q : 정렬 알고리즘이란 무엇이며, 사용 이유에 대해 설명해주세요 

 

A: 주어진 데이터를 정해진 기준에 따라 순서를 재배열하는 알고리즘으로 빠르고 효율적인 문제해결을 위해 사용합니다 

 

* 정렬 알고리즘의 평가 척도 

- 비교횟수와 이동 횟수

- 모든 경우에 최적인 정렬 알고리즘은 없고 응용에 맞게 선택해야한다 

 

* 정렬 알고리즘의 안정성 

같은 값을 갖는 원소의 순서가 정렬 후에도 유지되는 정렬을 안정된 정렬이라고 하고 그렇지 않은 정렬을 안정되지 않은 정렬이라고 한다 

안정된 정렬은 삽입, 버블, 병합 정렬이 있고 

안정되지 않는 정렬은 선택, 퀵 정렬이 있습니다 

 

*Comparison Sort  : 버블, 머지, 퀵

 Non-comparison-Sort : 카운팅, 라딕스 소트

 

Q: 선택 정렬과 버블 정렬에 대해 설명해주시고, 코드를 작성해보세요

 

A:  선택 정렬은 정렬되지 않은 원소들 중에서 최소값 원소를 찾아 맨 왼쪽 원소와 교환하는 작업을 반복하는 알고리즘이고, 버블 정렬은 정렬되지 않은 부분에서 인접한 두 원소의 크기를 비교하여 교환하는 작업을 반복하는 알고리즘이다 

두 알고리즘은 O(n^2) 시간 복잡도를 가지고 있습니다 

 

* 삽입 정렬 : 정렬되지 않은 부분의 첫 번째 원소를 정렬된 부분의 알맞은 위치에 삽입하는 과정을 반복하는 알고리즘

 

*분할 정복 : 주어진 문제의 규모가 커서 한 번에 해결하기 어려운 경우, 이를 작은 부분 문제로 나눠서 해결하는 방식 

 

*병합정렬:  입력 배열을 두 개의 부분 배열로 분할하고 부분 배열을 재귀적으로 정렬 후 병합하는데 이때 병합된 배열의 원소가 정해진 정렬 순서에 맞게 순서를 조정하여 정렬합니다 

 

*퀵정렬: 특정 원소를 피벗으로 선택하고, 주어진 배열을 피벗보다 작은 부분과 큰 부분으로 분할하고 분할된 부분 배열에 대해 재귀적으로 퀵 정렬 분할 작업을 반복합니다 

최선의 경우(항상 절반으로 분할되는 경우) : O(nlogn) 

최악의 경우( 한 쪽은 1, 다른 쪽은  n-1개로 분할되는 경우) O(n^2)

평균적으로 가장 빠른 정렬 알고리즘 입니다 

(피벗 : 비교 기준 원소)

 void Swap(ref int a, ref int b)
 {
     int tmp = a; 
     a = b;
     b = tmp;
 }

 void BubbleSor(int[] data, int n)
 {
     for(int i=0; i<n-1; i++)
     {
         for(int j = n-1; j>i; j--)
         {
             if (data[j] < data[j-1])
                 Swap(ref data[j], ref data[j-1]);
         }
     }
 }

 void SelectionSort(int[] data, int n)
 {
     for(int i = 0;i<n-1;i++)
     {
         int idx = i;
         for (int j = i + 1; j < n; j++)
         {
             if (data[j] < data[idx])
                 idx = j;
             Swap(ref data[i], ref data[idx]); 
         }
     }
 }