[C#]TIL (26) | 2023.08.29

들어가기 앞서

C#의 팀 프로젝트를 진행하면서 C# 문법종합반 강의를 정리하는 건 힘드네요.
오늘은 팀 프로젝트의 회의 및 필수 기능구현을 한번 해보았습니다.
기능 하나를 만들어서 테스트하면 문제가 보이고 그걸 고치고 다시 테스트하면 다른 문제가 보이고
이걸 반복하다보니 벌써 하루가 끝나 갑니다. 그래도 열심히 TIL을 작성해보겠습니다.

오늘 배운 것

탐색 알고리즘

• 탐색 알고리즘 ( Search Algorithm )
  주어진 데이터나 자료구조에서 원하는 값을 찾는 과정.
  데이터를 효율적으로 탐색하는 것은 데이터베이스, 검색 엔진, 게임 개발, 인공 지능 등 다양한 분야에서 필요한 기능.

  • 선형 탐색 ( Linear Search )
    간단한 탐색 알고리즘 중 하나.
    리스트나 배열과 같은 자료구조에서 특정 값을 찾기 위해 순차적으로 요소를 검색하는 방법.
    데이터가 정렬되어 있지 않거나, 특정한 조건이 없는 한 가지 상황에서 사용.

    • 작동 방식
    1. 탐색을 시작할 리스트나 배열의 첫 번째 요소부터 시작
    2. 현재 요소와 찾고자 하는 값이 일치하는지 확인
    3. 일치하지 않을 경우 다음 요소로 이동하여 반복
    4. 원하는 값이 발견될 때까지 이 과정을 반복
       
       
    • 구현

      static int LinearSearch(int[] arr, int target)
      {
          for (int i = 0; i < arr.Length; i++)
          {
              if (arr[i] == target)
              {
                  return i;  // 값을 찾은 경우 해당 인덱스 반환
              }
          }
          return -1;  // 값을 찾지 못한 경우 -1 반환
      }

  • 이진 탐색 ( Binary Search )
    정렬된 리스트나 배열에서 특정 값을 빠르게 찾는 알고리즘.
    이진 탐색은 선형 탐색보다 훨씬 효율적으로 작동하며, 탐색 범위를 반으로 줄이는 방식으로 동작.
    데이터의 중간 값을 확인하고 찾고자 하는 값과 비교하여 찾고자 하는 값을 찾을 때까지 탐색 범위를 조절.
    이진 탐색은 탐색 범위를 반씩 줄이므로, 시간 복잡도는 O(log n).

    • 작동방식
    1. 탐색 범위의 시작점을 가리키는 low와 끝점을 가리키는 high 변수를 설정
    2. low와 high의 중간 지점을 찾고, 중간 지점의 값과 찾고자 하는 값을 비교
    3. 중간 값이 찾고자 하는 값과 같다면 탐색이 완료
       3-1. 중간 값이 찾고자 하는 값보다 작다면 low를 중간 지점 다음으로 조정
       3-2. 중간 값이 찾고자 하는 값보다 크다면 high를 중간 지점 이전으로 조정
    4. low가 high보다 커지거나 같아진다면 값을 찾을 수 없는 경우
       
       
    • 구현

      static int BinarySearch(int[] arr, int target)
      {
          int low = 0;
          int high = arr.Length - 1;
      
          while (low <= high)
          {
              int mid = low + (high - low) / 2;
      
              if (arr[mid] == target)
              {
                  return mid;  // 값을 찾은 경우 해당 인덱스 반환
              }
              else if (arr[mid] < target)
              {
                  low = mid + 1;  // 중간 값보다 작은 경우 탐색 범위를 오른쪽으로 조절
              }
              else
              {
                  high = mid - 1;  // 중간 값보다 큰 경우 탐색 범위를 왼쪽으로 조절
              }
          }
      
          return -1;  // 값을 찾지 못한 경우 -1 반환
      }

• 그래프 ( Graph )
  다양한 객체들 간의 관계를 표현하는 추상적인 자료 구조.
  노드(node)나 정점(vertex)들의 집합과 이들을 연결하는 간선(edge)들의 집합으로 구성.

  • 그래프의 종류

    1. 무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프
       두 노드 간의 연결이 상호적인 관계를 가짐
    2. 방향 그래프 (Directed Graph 또는 Digraph): 간선에 방향이 있는 그래프
       한 노드에서 다른 노드로의 방향이 있는 경우를 나타냄
    3. 가중치 그래프: 간선에 가중치(weight)나 비용(cost)를 할당하여 노드 간의 관계를 나타냄.
    4. 사이클이 없는 그래프: 사이클이 형성되지 않는 그래프를 의미
       트리는 사이클이 없는 방향 그래프의 특수한 형태로 계층 구조를 표현하는 데 사용

  • 그래프 탐색 방법

    • 깊이 우선 탐색 (Depth-First Search, DFS)
      • 시작 노드에서부터 출발하여 한 경로를 따라 가능한 멀리까지 탐색
      • 더 이상 진행할 수 없을 때, 이전 노드로 돌아가서 다른 경로로 계속 탐색
      • 스택(stack)이나 재귀(recursion)를 이용하여 구현할 수 있음
      • 그래프 내의 사이클을 탐지하거나, 연결 요소의 개수를 파악하는 데 유용
      • 시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)

    • 너비 우선 탐색 (Breadth-First Search, BFS)
      • 시작 노드에서부터 출발하여 현재 노드와 인접한 노드들을 먼저 탐색
      • 같은 레벨의 노드들을 먼저 탐색한 후, 다음 레벨로 넘어감
      • 큐(queue)를 이용하여 구현할 수 있음
      • 최단 경로를 찾거나, 두 노드 간의 거리를 계산하는 데 유용
      • 시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)

• 최단 경로 알고리즘 ( Shortest path problem )
  그래프 내에서 두 노드 사이의 최단 경로를 찾는 문제를 해결하는 알고리즘

  • 유형
  1. 단일 출발점 최단 경로 문제 (Single-Source Shortest Path Problem)
     주어진 출발 노드에서 다른 모든 노드로 가는 최단 경로를 찾는 문제
     대표적인 알고리즘으로는 다익스트라 알고리즘
     다익스트라 알고리즘은 음의 가중치를 갖지 않는 그래프에서 사용
  2. 모든 쌍 최단 경로 문제 (All-Pairs Shortest Path Problem)
     그래프 내 모든 노드 쌍 간의 최단 경로를 찾는 문제
     대표적인 알고리즘으로는 플로이드-워셜 알고리즘
     플로이드-워셜 알고리즘은 음의 가중치를 갖는 그래프에서도 사용
     
     

기억 할 것 & 진행 사항

• 노드
  그래프에서 기본적인 구성 요소로, 그래프 내의 한 지점을 나타냄.
  노드는 다양한 이름으로 불리며, 정점(Vertex)이라고도 부름.

• 간선
  그래프에서 노드들을 연결하는 선.
  노드 간의 관계를 표현.
  그래프의 구조를 형성하며, 노드들 간의 연결 정보를 저장.
  방향성 여부와 가중치 여부에 따라 다양한 종류가 있음.

• 트리
  

• 최단 경로 알고리즘 종류

  • 다익스트라 알고리즘 (Dijkstra's Algorithm)
    음의 가중치가 없는 그래프에서 사용 가능하며, 간선의 가중치는 반드시 양수여야 함
    그리디 알고리즘의 일종으로, 탐욕적으로 최단 거리를 업데이트해 나감

  • 벨만-포드 알고리즘 (Bellman-Ford Algorithm)
    음의 가중치가 있는 그래프에서도 사용 가능하며, 음의 가중치 사이클을 포함
    동적 프로그래밍을 활용하여 최단 거리를 계산

  • 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
    음의 가중치가 있는 그래프에서도 사용 가능하며, 음의 가중치 사이클을 포함할 수 있음
    동적 프로그래밍을 활용하여 모든 노드 쌍 간의 최단 거리를 계산

현재 진행 사항

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

내일 할 일

• 하루 계획
  • 오전
    • 09:00 ~ 10:00 : 알고리즘 코드카타
    • 10:00 ~ 10:30 : 팀 회의
    • 10:30 ~ 14:00 :
      • 오늘 계획 (Task)
        • 팀 프로젝트
    • 12시-1시: 점심식사
  • 집중 코딩
    • 14:00 ~ 18:00
  • 저녁
    • 6시-7시: 저녁식사
    • 19:00 ~ 20:00 : 집중 코딩 시간 부족한 부분 해결해보기
    • 20:00 ~ 21:00: TIL 작성, 마무리 회고 진행
    • 21:00 : 내일은 위한 휴식!