C# 문법 5주차 - 1 (자료구조와 알고리즘)
📌 알고리즘 기초
1) 알고리즘(Algorithm)
문제를 해결하기 위한 단계적인 방법
01. 알고리즘 개념
-
알고리즘은 문제를 해결하기 위한 명확한 절차나 방법이다.
-
알고리즘은 입력을 받아 원하는 출력을 생성하기 위한 절차이다.
-
알고리즘은 입력, 출력, 명확한 단계, 실행 가능성의 특성을 갖는다.
-
알고리즘은 주어진 입력에 대해 정확하고 일관된 결과를 제공해야 한다.
-
알고리즘은 컴퓨터 프로그래밍뿐만 아니라 다양한 분야에서 사용된다.
02. 알고리즘의 중요성
-
효율적인 알고리즘은 컴퓨터 프로그래밍에서 매우 중요하다.
-
같은 문제를 해결하는 두 알고리즘이 있다면, 효율적인 알고리즘은 덜 효율적인 알고리즘보다 더 적은 컴퓨터 자원(시간, 메모리 등)을 사용한다.
-
따라서, 가능한 한 효율적인 알고리즘을 사용하는것이 중요하다.
2) Big O 표기법
알고리즘 전투력 측정기
01. Big O 표기법
-
Big O 표기법은 알고리즘의 효율성을 나타내는 표기법이다.
-
특히, Big O 표기법은 입력의 크기에 따라 알고리즘이 얼마나 많은 시간이나 공간을 필요호 하는지를 설명한다.
-
Big O 표기법은 알고리즘의 최악의 경우 성능을 나타내므로 알고리즘의 효율성을 과장하지 않는다.
02. Big O 표기법의 예
-
O(1) : 상수 시간. 입력의 크기에 상관없이 항상 일정한 시간이 걸린다.
-
O(n) : 선형 시간. 입력의 크기에 비례하여 시간이 걸린다.
-
O(n^2) : 이차 시간. 입력의 크기의 제곱에 비례하여 시간이 걸린다.
-
O(log n) : 로그 시간. 입력의 크기의 로그에 비례하여 시간이 걸린다.
03. Big O 표기법 계산
-
상수 버리기
알고리즘의 시간 복잡도에서 가장 큰 영향을 주는 항목을 중심으로 살펴본다. 상수 항목이나 낮은 차수의 항목은 Big O 표기법에서 중요하지 않으므로 버린다. 예를 들어, O(2n), O(3n^2)와 같은 경우 O(n), O(n^2)로 간소화할 수 있다. -
최고 차수 항목만 남기기
Big O 표기법에서는 가장 빠르게 증가하는 항목에 초점을 맞춘다. 따라서 가장 큰 차수의 항목만을 남기고 나머지는 버린다. 예를 들어, O(n^2 + n)의 경우 O(n^2)로 간소화할 수 있다. -
다항식의 경우 최고 차수 항목만 고려
다항식의 경우 가장 빠르게 증가하는 항목에 초점을 맞춘다. 상수항이나 낮은 차수의 항목은 무시한다. 예를 들어, O(3n^3 + 5n^2 + 2n + 7)의 경우 O(n^3)로 간소화할 수 있다. -
연산자 상수 무시
Big O 표기법에서는 연산자나 상수값을 무시한다. 예를 들어, O(3n^2 + 4n + 2)의 경우 O(n^2)로 간소화할 수 있다.
3) 시간 복잡도(Time Complexity)
How Long?
01. 시간 복잡도란?
-
시간 복잡도란 알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도이다.
-
코드의 실행 시간을 실제 시간(초)으로 측정하는 것이 아니라, 입력 크기에 대한 연산 횟수로 측정한다.
-
Big O 표기법을 사용하여 표시한다.
02. 활용 예제
- 예제 1
int Sum(int n)
{
int sum = 0;
for (int i = 0; i <= n; i++)
{
sum += i;
}
return sum;
}for 루프가 0부터 n까지 순회하며 합계를 계산한다. 따라서 n회의 연산이 필요하며, 시간 복잡도는 O(n)이다.
- 예제 2
void PrintPairs(int n)
{
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
Console.WriteLine(i + ", " + j);
}
}
}두 개의 중첩된 for 루프를 포함하고 있다. 각 루프는 0부터 n까지 순회하므로, 전체 연산 횟수는 n^2이며, 시간 복잡도는 O(n^2)이다.
- 예제 3
int Fibonacci(int n)
{
if (n <= 1)
{
return n;
}
else
{
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}재귀적으로 피보나치 수열을 계산하는 함수이다. 이 함수는 각 호출마다 두번의 재귀 호출을 수행하므로, 시간 복잡도는 O(2^n)이다.
이는 매우 비효율적인 방법으로, 실제 문제 해결에서는 동적 프로그래밍 등의 기법을 사용해 효율성을 높이는 것이 중요하다.
4) 공간 복잡도(Space Complexity)
How Many?
01. 공간 복잡도란?
-
코드의 메모리 사용량을 실제 메모리 크기(바이트)로 측정하는 것이 아니라, 입력 크기에 따라 필요한 저장 공간의 양을 측정하는 이유를 설명한다.
-
Big O 표기법을 사용하여 표시함
02. 활용 예제
// 시간 복잡도: 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)이라 할 수 있습니다.5) 예제 문제
문제 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;
}
시간 복잡도 : 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;
}시간 복잡도 : 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();
}시간 복잡도 : O(n)
공간 복잡도 : O(n)
📌 정렬 알고리즘 ★★★
1) 정렬 알고리즘
01. 정렬 알고리즘 이란?
-
정렬 알고리즘은 컴퓨터 과학에서 중요한 주제 중 하나이다.
-
주어진 데이터 세트를 특정 순서(대개는 숫자의 오름차순 또는 내림차순, 문자열의 사전식 순서)로 배열하는 방법을 제공한다.
02. 선택 정렬(Selection Sort)
-
선택 정렬은 배열에서 최소값(또는 최대값)을 찾아 맨 앞(또는 맨 뒤)와 교환하는 방법이다.
-
시간 복잡도 : 최악의 경우와 평균적인 경우 모두 O(n^2)
-
공간 복잡도 : O(1) (상수 크기의 추가 공간이 필요하지 않음)
구현 예제
가장 작은 원소를 찾아서 맨 앞에 위치하는 것을 반복하여 정렬하는 알고리즘
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
for (int i = 0; i < arr.Length - 1; i++)
{
int minIndex = i;
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
foreach (int num in arr)
{
Console.WriteLine(num);
}
03. 삽입 정렬(Insertion Sort)
-
삽입 정렬은 정렬되지 않은 부분에서 요소를 가져와 정렬된 부분에 적절한 위치에 삽입하는 방법
-
시간 복잡도 : 최악의 경우 O(n^2), 하지만 정렬되어 있는 경우에는 O(n)
-
공간 복잡도 : O(1) (상수 크기의 추가 공간이 필요하지 않음)
구현 예제
현재 위치에서 그 이하의 배열을 정렬된 배열 부분에 삽입하는 방법으로 정렬하는 알고리즘
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
for (int i = 1; i < arr.Length; i++)
{
int j = i - 1;
int key = arr[i];
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
foreach (int num in arr)
{
Console.WriteLine(num);
}
04. 퀵 정렬(Quick Sort)
-
퀵 정렬은 피벗을 기준으로 작은 요소들을 왼쪽, 큰 요소들을 오른쪽으로 분할하고 이를 재귀적으로 정렬하는 방법
-
시간 복잡도 : 최악의 경우 O(n^2), 하지만 평균적으로 O(n log n)
-
공간 복잡도 : 평균적으로 O(log n), 최악의 경우 O(n) (재귀 호출에 필요한 스택 공간)
구현 예제
분할 정복 방법을 이용하여 정렬하는 알고리즘
void QuickSort(int[] arr, int left, int right)
{
if (left < right)
{
int pivot = Partition(arr, left, right);
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
}
}
int Partition(int[] arr, int left, int right)
{
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++)
{
if (arr[j] < pivot)
{
i++;
Swap(arr, i, j);
}
}
Swap(arr, i + 1, right);
return i + 1;
}
void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
QuickSort(arr, 0, arr.Length - 1);
foreach (int num in arr)
{
Console.WriteLine(num);
}
05. 병합 정렬(Merge Sort)
-
병합 정렬은 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 병합하는 방법
-
시간 복잡도 : 모든 경우에 대해 O(n log n)
-
공간 복잡도 : O(n) (정렬을 위한 임시 배열이 필요함)
구현 예제
분할 정복 방법을 이용하여 정렬하는 알고리즘
void MergeSort(int[] arr, int left, int right)
{
if (left < right)
{
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
void Merge(int[] arr, int left, int mid, int right)
{
int[] temp = new int[arr.Length];
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
while (i <= mid)
{
temp[k++] = arr[i++];
}
while (j <= right)
{
temp[k++] = arr[j++];
}
for (int l = left; l <= right; l++)
{
arr[l] = temp[l];
}
}
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
MergeSort(arr, 0, arr.Length - 1);
foreach (int num in arr)
{
Console.WriteLine(num);
}2) C# Sort
01. Sort메서드
-
Sort메서드는 배열이나 리스트의 요소들을 정렬하는 메서드이다. -
정렬은 오름차순으로 수행되며, 요소들의 자료형에 따라 다양한 정렬 기준을 사요할 수 있다.
-
Sort메서드는 원래의 배열이나 리스트를 직접 수정하므로 반환값이 없다.
02. 사용예제
// 정수 배열 정렬 예제
int[] numbers = { 5, 2, 8, 3, 1, 9, 4, 6, 7 };
Array.Sort(numbers);
Console.WriteLine(string.Join(", ", numbers));
// 문자열 리스트 정렬 예제
List<string> names = new List<string> { "John", "Alice", "Bob", "Eve", "David" };
names.Sort();
Console.WriteLine(string.Join(", ", names));
📌 프로그래머스(개인공부)
using System;
using System.Linq;
public class Solution {
public long solution(long n) {
long answer = 0;
string s = n.ToString(); // 입력된 수(long)을 string으로 변환
char[] c = s.ToCharArray(); // string형을 Char형으로 변환
// LINQ를 이용해 내림차순(OrderByDescending)으로 변환
answer = long.Parse(c.OrderByDescending(x => x).ToArray());
return answer;
}
}// 이런 방식으로도 가능
public long solution(long n) {
long answer = long.Parse(n.ToString().OrderByDescending(c => (int)c).ToArray());
return answer;
} Array.Sort(배열); : 오름차순 정렬
Array.Reverse(배열); : 내림차순 정렬
