[TIL] 내일배움캠프_Unity DP, BinarySearch

C# 문법 종합반 5주차 강의 과제를 풀기 위한 알고리즘 공부 ! 

 - 다이나믹 프로그래밍 (DP) 

: 여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아 올려 주어진 문제를 해결하는 알고리즘 

푸는 과정 

1. 테이블 정리하기 

2. 점화식 찾기 

3 . 초기값 정하기 

 

ex)  백준 1463번 1로 만들기 

1. 테이블 정의하기
 D[i]를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값
2. 점화식 찾기 
D[k] = D[k/3] +1 (3으로 나누어지면 3으로 나누거나) 
D[k] = D[k/2] +1 (2로 나누어지면 2로 나누거나)
D[k] = D[k-1] +1 (1을 빼거나)
3. 초기값 정의하기 
D[1] = 0

 

코드

static void Main(string[] arge)
{
    int n = int.Parse(Console.ReadLine());
    int[] d = new int[n + 1];

    d[1] = 0;

     for (int i = 2; i <= n; i++)
     {
     	d[i] = d[i - 1] + 1;
        if (i % 2 == 0) d[i] = Math.Min(d[i], d[i / 2] + 1);
        if (i % 3 == 0) d[i] = Math.Min(d[i], d[i / 3] + 1);
     }
     Console.WriteLine(d[n]);
}

 

이분 탐색 : 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법 

 

st = 배열의 처음, en = 배열의 끝 , mid = 배열의 중간으로 배열의 반을 나눠가며 탐색 

st가 en을 넘어가면 탐색하는 숫자가 배열에 없음 (st<=en)

 

ex) 백준 1920 수찾기 

 

코드

public static int BS(int[] arr,int target)
{
    int st = 0;
    int en = arr.Length-1;

    while (st <= en)
    {
        int mid = (st + en) / 2;
        if (target < mid) en = mid - 1;
        else if (target > mid) st = mid + 1;
        else return 1;
     }
     return 0; 
}

 

알고리즘 공부는 끝이 없고 어렵다 

5주차 과제 해설은 내일 ... 개발일지로...