TIL(2023.08.28)

오늘의 공부내용

===탐색 알고리즘, 그래프, 하샤드수 알고리즘===

1. 탐색 알고리즘

• 탐색 알고리즘이란?
  -주어진 데이터 집합에서 특정 항목을 찾는 방법
• 선형 탐색 (Linear Search)
  -가장 단순한 탐색 알고리즘
  -배열의 각 요소를 하나하나 차례대로 검사하여 탐색
  -시간복잡도: 최악의 경우 O(n)
  -배열이 정렬되어 있지 않을 경우에 사용

int SequentialSearch(int[] arr, int target)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == target)
        {
            return i;
        }
    }

    return -1;
}

• 이진 탐색 (Binary Search)
  -정렬된 배열에서 빠르게 원하는 항목을 찾는 방법
  -중간(mid)와 찾고자 하는 항목을 비교하여 대상이 mid보다 작으면 왼쪽, 크면 오른쪽을 탐색
  -시간복잡도: 최악의 경우 O(log n)
  -배열이 정렬되어 있을 경우 사용

int BinarySearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (arr[mid] == target)
        {
            return mid;
        }
        else if (arr[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    return -1;
}

2.그래프 (Graph)

• 깊이 우선 탐색 (Depth-First Search, DFS)
  -트리나 그래프를 탐색하는 알고리즘
  -루트에서 시작하여 vertex를 더 이상 못만날때까지 탐색
  -시간복잡도: 최악의 경우 O(V+E) (V는 노드수, E는 간선 수)
• 너비 우선 탐색 (Breadth-First Search, BFS)
  -루트에서 가까운 vertex들부터 모두 체크 한뒤에 그 다음에 만난 vertex의 edge들을 검색 해 나갑니다.
  -시간복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)
  

3.알고리즘 문제 풀이 (하샤드 수)

• 하샤드 수는 양의 정수 X가 X의 자릿수의 합으로 나머지 없이 나누어지면 하샤드 수이다.
• 숫자를 분해해서 각 자릿수의 합을 구하는 방법을 이용
  -문자열로 변환해서 배열처럼 각 자릿수에 접근
  -이후에 다시 문자열을 정수형으로 변환
• for문 이용
• 조건 연산자를 이용

using System;

public class Solution {
    public bool solution(int x) 
    {
        //x를 문자열로
        string temp = x.ToString();
        
        //for문
        int sum =0;
        for (int i =0; i<temp.Length; i++)
        {
            sum += (int)Char.GetNumericValue(temp[i]);
        }
        //나머지가 0이면 참, 아니면 거짓
        bool answer = x % sum ==0 ? true:false;
        return answer;
    }
}

• 이런 식으로 문자열 temp에 양의 정수 X를 문자열로 저장하고, for문을 이용해서 각 자리의 수를 합산한뒤에 조건 연산자를 이용해 양의 정수 X를 총합 sum으로 나뉘었을 때 나머지 값이 0일 경우에만 true가 실행되고 answer를 출력.