[C#]TIL (24) | 2023.08.25

들어가기 앞서

알고리즘에 대해 매일 풀어보는 알고리즘 코드카타를 시작했습니다.
한시간 안에 최대한 풀어보는 것이지만 생각보다 재밌어서 계속 하고 싶어집니다.
알고리즘을 많이 공부하다 보면 저만의 풀이 방법도 있고 다른 사람들이 더 효율적으로 만든 방법들도 있어서
구경하는 재미가 많은 것 같습니다. 신기한 방법들을 많이 찾아보면서 익숙해지도록 하겠습니다.

오늘 배운 것

알고리즘 기초

• 알고리즘 ( Algorithm )
  문제를 해결하기 위한 절차나 방법을 나타내는 단계적인 지침의 집합.
  주어진 입력을 원하는 출력으로 변환하기 위한 명확한 단계를 제공.
  컴퓨터 과학, 수학, 공학 등 다양한 분야에서 사용.

  • 알고리즘 특징
    • 유한성 (Finiteness): 무한루프에 빠지거나 계속 실행되는 상황이 발생해서는 안되며 알고리즘은 한정된 단계 후에 종료되어야 함.
    • 정확성 (Accuracy): 주어진 입력에 대해 올바른 출력을 생성해야 하며, 정확한 결과를 도출해야 함.
    • 입력 (Input): 하나 이상의 입력을 받아들일 수 있어야 함.
    • 출력 (Output): 알고리즘은 입력에 대한 처리를 거쳐 원하는 결과물인 출력을 생성해야 함.
    • 명확성 (Clarity): 각 단계는 명확하게 정의되어야 하며 모호성 없이 해석되어야 함.
    • 유효성 (Effectiveness): 각 단계는 기본적이고 실행 가능한 연산들로 구성되어야 함.

• Big O 표기법
  알고리즘의 시간 복잡도나 공간 복잡도를 나타내는 표기 방법 중 하나.
  알고리즘의 실행 시간이나 사용되는 메모리 공간이 입력 크기에 어떻게 비례하는지를 표현하는 방법.

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

• 시간 복잡도 (Time Complexity)
  알고리즘이 입력 크기에 따라 어떻게 실행 시간이 증가하는지를 나타내는 개념
  시간 복잡도는 주어진 입력에 대해 알고리즘이 얼마나 빠르게 실행되는지를 나타내는 지표로 사용됨
  빅 오 표기법(O(f(n)))을 사용하여 나타내며, 여기서 f(n)은 입력 크기 n에 대한 알고리즘의 실행 시간 함수

  • 예시

    1. 루프 사용

       def sum_array(arr):
       total = 0
       for num in arr:
           total += num
       return total

       루프가 n번 실행되므로 시간 복잡도는 O(n)

    2. 재귀 사용

       def recursive_sum(arr, n):
       if n == 0:
           return 0
       return arr[n-1] + recursive_sum(arr, n-1)

       각 재귀 호출마다 하나의 요소를 더하고, 결국 n번 호출. 
        이 때문에 시간 복잡도도 O(n). 
        하지만 재귀의 경우 추가적인 함수 호출에 따른 오버헤드가 있을 수 있음.

• 공간 복잡도 (Space Complexity)
  알고리즘이 실행되는 동안 필요로 하는 메모리 공간의 양을 나타내는 개념
  주로 알고리즘의 실행 중에 생성되는 변수, 자료 구조, 임시 저장소 등을 고려하여
  빅 오 표기법(O(f(n)))을 사용하여 나타냅니다. 여기서 f(n)은 입력 크기 n에 대한 알고리즘의 메모리 사용량

  • 예시

    1. 재귀적으로 계산하는 팩토리얼 알고리즘

       def factorial(n):
        if n == 0:
            return 1
        return n * factorial(n - 1)

       		이 경우 공간 복잡도는 재귀 호출의 깊이에 따라 달라짐.

기억 할 것 & 진행 사항

• 빅오 표기법 계산

  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)로 간소화

현재 진행 사항

• 체크리스트
  • 개발 환경 설정
  • 기본 코드 구조
  • 변수와 자료형
  • 연산자 문자열 처리
  • 조건문과 반복문
  • 배열과 컬렉션
  • 매서드와 구조체
  • 클래스와 객체
  • 상속과 다형성
  • 고급 문법 및 기능
  • 인터페이스와 열거형
  • 예외 처리 및 값형과 참조형
  • 델리게이트, 람다 및 LINQ
  • 고급 자료형 및 기능
  • 알고리즘 기초 -> 여기까지 정리중
  • 정렬 알고리즘
  • 탐색 알고리즘
  • 고급 알고리즘
  • 문제해결 전략과 실전 연습 -> 현재 여기까지 강의 수강

내일 할 일

• 하루 계획
  • 알고리즘 공부
  • 동료코드 분석
  • 졸업작품