오늘 배운 내용

알고리즘(Algorithm)

---

알고리즘이란?

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

알고리즘의 설계 과정

• 문제이해 -> 예시와 테스트 케이스 작성 -> 알고리즘 설계 -> 알고리즘 구현 및 검증 -> 알고리즘 분석과 개선(실패했다면 알고리즘 설계부터 다시 시작)

• 알고리즘을 설계할 때는 알고리즘의 정확성과 이를 검증할 검증 방법을 최우선으로 고려해야 한다.

while(b가 100보다 작다면?)
{
i를 1올린다;
	if(배열의 i번째 요소가 10보다 크다면?)
    {
    b를 제곱 시킨다;
    n도 올려서 총 b가 몇번 제곱되었는지 측정;
    }
}
// 알고리즘의 문제를 해결하기 위해, 본인만의 알고리즘을 구상하는 단계
// 위와 같은 코드의 흐름을 인간의 언어로 적는것을
// "의사코드" 라고 한다. 

- 재귀 함수

• 함수가 자기 자신을 호출하도록 하는 프로그래밍 기법

static void PrintStep(int startNumber, int stopNumber)
{
	Console.WriteLine(startNumber);
    PrintStep(startNumber + 1, stopNumber);
    		//자기 자신을 호출
}

• 기저 조건 : 재귀 호출을 멈추는 조건
• 재귀 조건 : 자기 자신을 호출하는 부분
• 재귀로 가능한것은 반복문으로도 해결할 수 있다.
• 반복문으로 해결하는 문제를 모두 재귀로 해결할 수는 없다.
• 분할정복법의 핵심적인 역할을 함

- 선택 정렬(Selection Sort)

static void SelectionSort(List<int> list)
{
	for (int i = 0; i < list.Count - 1; 1++)
    {
    	int minIndex = i;
        
        for (int j = i + 1; j < list.Count; j++) //최소값 찾기
        {
        	if (list[j] < list[minIndex])
            {
            	minIndex = j;
            }
        }
        
        if (minIndex != i) // 같은 위치가 아니면 교환
        {
        	SwapInList(list, i, minIndex);
        }
    }
}

static void SwapInList(List<int> list, int a, int b)
{
	int temp = list[a];
    list[a] = list[b];
    list[b] = temp;
}

- 삽입 정렬(Insertion Sort)

static void InsertionSort(List<int> list)
{
	for (int i = 1; i < list.Count; i++)
    {
    	int target = list[i]; // 현재 값
        int j = i - 1;
        
        while (j >= 0 && list[j] > target) // target보다 작은 값들을 한칸씩 뒤로 미루기
    	{
        	list[j + 1] = list[j];
            j--;
        }
        
        list[j + 1] = target; // target을 올바른 위치에 삽입
    }
}

- 버블 정렬(Bubble Sort)

static void BubbleSort(List<int> list)
{
	bool isSorted = false;
	
	for (int i = 0; i < list.Count - 1; i++)
    {
    	isSorted = false;
        
    	for (int j = 0; j < list.Count - i - 1; j++)
        {
        	if(list[j] > list[j + 1])
            {
            	swapInList(list, j, j + 1);
                isSorted = true;
            }
        }
        if (!isSorted) return;
    }
}

탐색 알고리즘 - 이진 탐색

static void BinarySearch(List<int> list, int target)
{
	int count = 0;
	int start = 0;
    int end = list.Count - 1;
    
    while (start <= end)
    {
    	count++;
    	int pivot = start + (end - start) / 2;
        
        if (list[pivot] == target)
        {
        	Console.WriteLine($"찾았음. count : {count}");
            return;
        }
        
        if (list[pivot] < target)
        {
        	start = pivot + 1;
        }
        else
        {
        	end = pivot - 1;
        }
    }
    Console.WriteLine("못찾음")
}