250926 알고리즘

문제를 해결하기 위한 과정을 논리적 절차에 따라 구성한 일련의 단계

문제 이해 → 예시와 테스트 케이스 작성 → 알고리즘 설계 → 알고리즘 구현 및 검증 → 알고리즘 분석과 개선

 

Fisher Yates Shuffle

/// <summary>
/// 카드 섞어주는 기능
/// </summary>
/// <param name="inputArr"> 섞이지 않은 카드배열 </param>
public static void FisherYatesShuffle(int[] inputArr)
{
    Random rnd = new Random(); // 섞을거니 랜덤을 만듦

    for ( int i = inputArr.Length - 1; i > 0; i-- ) // 인덱스 역순
    {
        int j = rnd.Next(0, i + 1); // 0부터 i까지 랜덤 인덱스 선택 (+1 이유는 0 이상 i 미만이기 때문)

        int temp = inputArr[i];
        inputArr[i] = inputArr[j];
        inputArr[j] = temp;
    }
}

static void Main(string[] args)
{
    int[] num = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    FisherYatesShuffle(num);

    foreach ( var a in num )
    {
        Console.Write(a);
    }
}

// 배열을 반복하면서, 인접한 두 값을 비교
// 두 값이 크기 순서에 맞지 않으면 위치를 교환
// 배열 끝까지 비교를 반복하면 가장 큰 값이 배열 끝으로 이동
// 배열이 정렬될 때까지 위 과정을 반복

public static void BubbleSort(int[] Array)
{
    for( int i = 0; i < Array.Length - 1; i++ ) // 일단 0부터 모든 요소 돌 예정
    {
        for ( int j = 0; i < Array.Length - i - 1; j++ )
        {
            if (Array[j] == Array[j+1] ) // 잘못된 순서라면?
            {
                // 스왑 실행
                int temp = Array[j];
                Array[j] = Array[j + 1];
                Array[j + 1] = temp;
            }
        }
    }
}

https://www.youtube.com/watch?v=Iv3vgjM8Pv4

// 선택 정렬
// 매 단계마다 배열에서 가장 작은걸 찾아서 배열 맨 앞에 가져다 두는 방식
// 비교횟수가 여전히 많긴 하지만, 버블 정렬보다는 낫다

public static void SelectionSort(int[] array)
{
    for (int i = 0; i < array.Length - 1; i++ )
    {
        int minIndex = i; // 하나를 선택하여 기준

        for(int j = i +1; j < array.Length; j++ )
        {
            if (array[j] < array[minIndex]) // 반복문을 돌며 선택한 j 와 비교
            {
                minIndex = j; // 반복을 돌다가 필요할 경우 최소값을 j로 바꾼다
            }
        }
        //여기까지 왔다는 뜻은, 배열 끝까지 다 봤다는 의미

        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

https://www.youtube.com/watch?v=hFhf9djnM5A

 

Stopwatch watch = new Stopwatch();

watch.Start(); // 스탑워치 On

SelectionSort(ints);

Console.WriteLine(watch.ElapsedMilliseconds + "여기있음");
watch.Stop(); // 스탑워치 Off

// Sleep 은 진짜 모든게 그 시간만큼 멈춤
// StopWatch는 시간은 시간대로 흐르고, 필요할 경우 3초 후에 수행 등등

Stopwatch watch = new Stopwatch();

Console.CursorVisible = false;

watch.Start(); // 스탑워치 On

while (true)
{
    Console.WriteLine(watch.ElapsedMilliseconds / 1000);
    Console.SetCursorPosition(0, 0);
}

// Sleep 은 진짜 모든게 그 시간만큼 멈춤
// StopWatch는 시간은 시간대로 흐르고, 필요할 경우 3초 후에 수행 등등