[TIL]2024-1-8 / 11일차 - 인터페이스&열거형, 알고리즘 자습시간

 

오늘은 개인 과제 추가 제출 날, 이미 기본 기능은 완성 시켜 내었기 때문에 제대로 못 봤던 4주차 / 5주차 강의를 보기로 했다.

 

4주차 5주차 강의 내용은 많이 어려운 내용을 다루었다.

 

1. C# 인터페이스와 열거형

2. 예외 처리 및 값형과 참조형

3. 델리게이트, 람다 및 LINQ

4. 고급 자료형 및 기능

5. 알고리즘

6. 정렬 알고리즘

7. 탐색 알고리즘

8. 고급 알고리즘

9. 문제 해결 전략과 실전 연습

 

람다와 같은 기능들도 어려웠지만

알고리즘의 내용은 아예 새로운 분야를 배우는 느낌이었다.

 

빅O를 통해 효율성을 체크한다는, 엄청 중요한 부분이지만

단기간에 배우기에는 어려운 개념이었다. 후에 복습이 필수적일 것 같다.

하지만 내일은 알고리즘 특강 이후 심화 C#으로 넘어가게 된다.

 

 

 

오늘은 직접 코딩한 내용은 극히 적기에 주요 개념들만 메모 해두고 마무리 한다.

 

---

 

• Big O 표기법의 예
  • O(1): 상수 시간. 입력의 크기에 상관없이 항상 일정한 시간이 걸립니다.
  • O(n): 선형 시간. 입력의 크기에 비례하여 시간이 걸립니다.
  • O(n^2): 이차 시간. 입력의 크기의 제곱에 비례하여 시간이 걸립니다.
  • O(log n): 로그 시간. 입력의 크기의 로그에 비례하여 시간이 걸립니다.

• 빅오 표기법 계산
  1. 상수 버리기 알고리즘의 시간 복잡도에서 가장 큰 영향을 주는 항목을 중심으로 살펴봅니다. 상수 항목이나 낮은 차수의 항목은 빅오 표기법에서 중요하지 않으므로 버립니다. 예를 들어, O(2n), O(3n^2)와 같은 경우 O(n), O(n^2)로 간소화할 수 있습니다.
  2. 최고 차수 항목만 남기기 빅오 표기법에서는 가장 빠르게 증가하는 항목에 초점을 맞춥니다. 따라서 가장 큰 차수의 항목만을 남기고 나머지는 버립니다. 예를 들어, O(n^2 + n)의 경우 O(n^2)로 간소화할 수 있습니다.
  3. 다항식의 경우 최고 차수 항목만 고려 다항식의 경우 가장 빠르게 증가하는 항목에 초점을 맞춥니다. 상수항이나 낮은 차수의 항목은 무시합니다. 예를 들어, O(3n^3 + 5n^2 + 2n + 7)의 경우 O(n^3)로 간소화할 수 있습니다.
  4. 연산자 상수 무시 빅오 표기법에서는 연산자나 상수 값을 무시합니다. 예를 들어, O(3n^2 + 4n + 2)의 경우 O(n^2)로 간소화할 수 있습니다.

• 1) 시간 복잡도란?
  • 시간 복잡도란 알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도입니다.
  • 코드의 실행 시간을 실제 시간(초)으로 측정하는 것이 아니라, 입력 크기에 대한 연산 횟수로 측정합니다.
  • Big-O 표기법을 사용하여 표시함

• 2) 공간 복잡도란?
  • 코드의 메모리 사용량을 실제 메모리 크기(바이트)로 측정하는 것이 아니라, 입력 크기에 따라 필요한 저장 공간의 양을 측정하는 이유를 설명합니다.
  • Big-O 표기법을 사용하여 표시함

• 3) Sort 메서드
  • Sort 메서드는 배열이나 리스트의 요소들을 정렬하는 메서드입니다.

// 정수 배열 정렬 예제
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));

• 코딩 테스트나 알고리즘 문제의 종류
  1. 탐색과 정렬: 배열, 리스트, 문자열 등의 데이터에서 특정 값을 찾거나 정렬하는 문제입니다. 선형 탐색, 이진 탐색, 퀵 정렬, 병합 정렬 등의 알고리즘이 주로 활용됩니다.
  2. 그래프: 그래프 구조를 활용하여 문제를 해결하는 문제입니다. 최단 경로, 신장 트리, 네트워크 연결 등의 문제가 있을 수 있으며, 대표적인 알고리즘으로는 DFS(Depth-First Search), BFS(Breadth-First Search), Dijkstra, 크루스칼, 프림 등이 있습니다.
  3. 동적 프로그래밍: 큰 문제를 작은 하위 문제로 분할하여 해결하는 동적 프로그래밍 알고리즘을 활용하는 문제입니다. 피보나치 수열, 최장 공통 부분 수열, 0-1 배낭 문제 등이 있습니다.
  4. 그리디 알고리즘: 각 단계에서 가장 최적인 선택을 하는 알고리즘으로, 지역적 최적해를 찾는 문제입니다. 거스름돈 문제, 회의실 배정, 작업 스케줄링 등이 있습니다.
  5. 분할 정복: 문제를 작은 부분으로 분할하여 해결하는 분할 정복 알고리즘을 사용하는 문제입니다. 퀵 정렬, 병합 정렬, 이진 탐색 등이 있습니다.
  6. 동적 그래프: 그래프 구조에서 동적인 변화를 다루는 문제입니다. 플로이드-와샬 알고리즘, 벨만-포드 알고리즘 등이 있습니다.
  7. 문자열 처리: 문자열에 대한 다양한 처리를 다루는 문제입니다. 문자열 압축, 회문 판별, 문자열 매칭 등이 있을 수 있습니다.
  8. 기타: 그 외에도 수학적인 문제, 비트 연산 문제, 시뮬레이션 문제, 동적 계획법과 그래프의 결합 문제 등 다양한 유형의 문제가 출제될 수 있습니다.