C# #13 알고리즘 기초 3

병합

• 오름차순으로 정렬되어 있는 정수 배열을 하나로 병합하는 알고리즘이다. 
• 각 배열의 병합을 통해 만들어진 머지 배열의 길이는 각 배열의 길이의 합과 같다. 
• 각 배열의 첫번째 인덱스의 값을 비교하여 작은 것을 머지 배열에 넣는다. 머지 배열에 들어가지 않은 값과 다른 배열의 다음 인덱스의 값을 비교하여 작은 것을 머지 배열에 넣는다. 머지 배열의 인덱스 k는 값이 넣어졌을 때 무조건 증가하고 비교 후 값이 빠진 쪽 배열의 인덱스(i or j)를 증가시킨다.
• 위 작업을 둘 중 하나라도 배열의 끝에 도달할 때까지 반복한다. 그 때, 배열이 끝나지 않은 다른 배열의 나머지 값들을 모두 머지 배열에 넣는다.

//Input
int[] first = { 1, 3, 5 };
int[] second = { 2, 4 };
int M = first.Length; int N = second.Length; //각 배열의 길이
int[] merge = new int[M + N]; //병합된 배열
int i = 0; int j = 0; int k = 0; 

//Process: MERGE
while (i < M && j < N) //둘 중 하나라도 배열의 끝에 도달할 때까지 반복
{
    if (first[i] <= second[j]) //더 작은 값을 merge 배열에 저장
    {
        merge[k++] = first[i++]; //인덱스 증가
    }
    else
    {
        merge[k++] = second[j++];
    }
}

while (i < M) //첫 번째 배열이 끝까지 도달할 때까지 
{
    merge[k++] = first[i++];
}

while(j < N) //두 번째 배열이 끝까지 도달할 때까지 
{
    merge[k++] = second[j++];
}

//Output
foreach(var item in merge)
{
    Console.WriteLine($"{item}");
}

 

최빈값

• 최빈값은 주어진 데이터에서 가장 많이 나타난 값이다.
• 기존 배열의 값이 n개라면 n+1의 길이를 가진 그 배열 값의 인덱스 배열을 선언한다.
• 기존 배열의 값들을 인덱스 배열에 넣어줄 때마다 인덱스 배열의 값을 1씩 증가시킨다. 
• 이때, 인덱스 배열의 값중 가장 큰 값이 들어있는 위치가 최빈값이다.

//Input
int[] scores = { 1, 3, 4, 3, 5 };
int[] indexes = new int[5 + 1]; //0-5까지 점수 인덱스의 개수 저장
int max = int.MinValue; //최빈값이 나타난 수 
int mode = 0;

//Process: MODE
for (int i = 0; i < scores.Length; i++)
{
    indexes[scores[i]]++; //인덱스배열의 인덱스의 COUNT
}
for (int i = 0; i < indexes.Length; i++)
{
    if (indexes[i] > max)
    {
        max = indexes[i]; //최댓값
        mode = i;
    }
}

//Output
Console.WriteLine($"최빈값: {mode}");