🐣 알고리즘(Algorithm)
🤔 알고리즘?
- 문제를 해결하기 위한 명확한 절차나 방법
- 입력을 받아 원하는 출력을 생성하기 위한 절차
- 입력, 출력, 명확한 단계, 실현 가능성, 속도, 메모리 관리
- 주어진 입력에 정확하고 일관된 결과를 제공해야 한다.
✨ 알고리즘의 중요성
- 효율적인 알고리즘을 통해 더 효율적인 프로그램을 작성할 수 있다.
- 효율적인 알고리즘은 그렇지 않은 경우보다 더 적은 컴퓨팅 자원을 사용한다.
🙆 Big O 표기법
알고리즘의 전투력 측정기!
- 알고리즘의 효율성을 나타내는 표기법이다.
👉 특히, Big O 표기법은 입력의 크기에 따라 알고리즘이 얼마나 많은 시간, 공간을 필요로 하는지를 설명한다! - Big O 표기법은 알고리즘의 최악의 경우 성능을 나타내므로 알고리즘의 효율성을 과장하지 않는다!
Big O 표기법의 예
- O(1) : 상수 시간. 입력의 크기에 상관없이 항상 일정한 시간이 걸린다.
- O(n) : 선형 시간. 입력의 크기에 비례하여 시간이 걸린다.
- O(n^2) : 이차 시간. 입력의 크기의 제곱에 비례하여 시간이 걸린다.
- O(log n) : 로그 시간. 입력의 크기의 로그에 비례하여 시간이 걸린다.
Big O 표기법 계산
- 상수 버리기
- 최고 차수만 남기기
- 연산자 상수 무시
ex) O(3n^3 + 5n^2 + 2n + 7)의 경우, Big O 표기법으로 O(n^3)이 된다.
⏱️ 시간 복잡도(Time Complexity)
🤔 시간 복잡도?
- 알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도.
- 코드의 실행 시간을 실제 시간으로 측정하는 것이 아니라, 입력 크기에 대한 연산 횟수로 측정!
- Big O 표기법을 사용하여 표시함
▪️ 예제)
아래 코드의 시간 복잡도를 구해보자!
int Sum(int n)
{
int sum = 0;
for (int i = 0; i <= n; i++)
{
sum += i;
}
return sum;
}for문을 n번 반복하기 때문에 시간 복잡도는 O(n)이다.
아래 코드의 시간 복잡도를 구해보자 2222222
void PrintPairs(int n)
{
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
Console.WriteLine(i + ", " + j);
}
}
}중첩 for문을 n × n 번을 돌기 때문에 시간 복잡도는 O(n^2)이다.
아래 코드의 시간 복잡도를 구해보자 3333333
int Fibonacci(int n)
{
if (n <= 1)
{
return n;
}
else
{
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}재귀적으로 피보나치 수열을 계산하는 함수! 이 함수는 각 호출마다 두 번의 재귀 호출을 수행하기 때문에 시간 복잡도는 O(2^n)이다. 매우 비효율적인 방법!!!!!!!!!
🏠 공간 복잡도(Space Complexity)
🤔 공간 복잡도?
- 실제 메모리 크기로 측정하는 것이 아니라 입력의 크기에 따라 필요한 저장 공간의 양을 측정.
- Big O 표기법을 사용하여 표시
▪️ 예제)
// 시간 복잡도: O(n)
int FindMax(int[] arr)
{
int max = arr[0];
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
return max;
}
// 시간 복잡도: O(n^2)
int FindMax2(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
bool isMax = true;
for (int j = 0; j < arr.Length; j++)
{
if (arr[j] > arr[i])
{
isMax = false;
break;
}
}
if (isMax)
{
return arr[i];
}
}
return -1;
}
int[] arr = new int[] { 1, 2, 3, 4, 5 };
// FindMax 메서드의 시간 복잡도: O(n), 공간 복잡도: O(1)
int max = FindMax(arr);
// 배열의 크기에 비례하여 실행 시간이 증가하므로 O(n)이라 할 수 있다.
// 또한 추가적인 메모리 공간을 사용하지 않기 때문에 공간 복잡도는 O(1)이라 할 수 있다.
// FindMax2 메서드의 시간 복잡도: O(n^2), 공간 복잡도: O(1)
int max2 = FindMax2(arr);
// 이중 반복문을 사용하기 때문에 배열의 크기에 제곱에 비례하여 실행 시간이 증가하므로
// O(n^2)이라 할 수 있다. 이 알고리즘은 추가적인 메모리 공간을 사용하지 않기 때문에
// 공간 복잡도는 O(1)이라 할 수 있다.🤓 예제 문제)
시간 복잡도와 공간 복잡도 계산해보기
▪️ 문제 1번)
public static bool FindNumber(int[] array, int target)
{
for (int i = 0; i < array.Length; i++)
{
if (array[i] == target)
{
return true;
}
}
return false;
}FindNumber는 array를 한 번 돌면서 target과 같은지 비교를 하고 있기 때문에 시간 복잡도는 O(n)이다. 또한 추가적인 메모리 공간을 사용하지 않았기 때문에 공간 복잡도는 O(1)이다.
👉 시간 복잡도 : O(n), 공간 복잡도 : O(1)
▪️ 문제 2번)
public static int FindMax(int[] array)
{
int max = int.MinValue;
for (int i = 0; i < array.Length; i++)
{
if (array[i] > max)
{
max = array[i];
}
}
return max;
}FindMax는 array를 돌며 최대값을 찾기 때문에 시간 복잡도는 O(n)이다. 공간 복잡도의 경우, 변수가 하나만 새로 추가 되기 때문에 O(1)이다.
👉 시간 복잡도 : O(n), 공간 복잡도 : O(1)
▪️ 문제 3번)
public static int[] RemoveDuplicates(int[] array)
{
List<int> distinctList = new List<int>();
foreach (int num in array)
{
if (!distinctList.Contains(num))
{
distinctList.Add(num);
}
}
return distinctList.ToArray();
}해당 코드는 배열을 돌면서 중복되는 인덱스를 제거하는 코드이다. 배열을 1번 돌기 때문에 시간 복잡도는 O(n)이다. 중복되는 인덱스를 제거한 배열을 새로 만들기 때문에 공간 복잡도는 O(n)이다.
👉 시간 복잡도 : O(n), 공간 복잡도 : O(n)
