[기술면접] 알고리즘 - 2/2

1편에 이어서 작성해 보겠습니다.

 

😎 동적 프로그래밍(Dynamic Programming)이란?

주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 해결하는 방식입니다. 동적 프로그래밍에서는 어떤 부분 문제가 다른 문제들을 해결하는 데 사용될 수 있어, 답을 여러 번 계산하는 대신 한 번만 계산하고 그 결과를 재활용하는 메모이제이션(Memoization) 기법으로 속도를 향상 시킬 수 있습니다. 

▶ 동적 프로그래밍(Dynamic Programming)의 두 가지 조건에 대해 말씀해 주세요.

동적 프로그래밍(Dynamic Programming)으로 문제를 해결하기 위해서는 주어진 문제가 다음의 조건을 만족해야 합니다.

• Overlapping Subproblem(중복되는 부분문제): 주어진 문제는 같은 부분 문제가 여러 번 재사용된다.
• Optimal Substructure(최적 부분구조): 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다.

 

😎 재귀 알고리즘이란?

함수 내부에서 자기 자신을 또다시 호출하여 문제를 해결하는 알고리즘입니다.
자기 자신을 계속해서 호출하여 끝없이 반복되게 되므로 반복을 중단할 조건이 반드시 필요합니다.

▶ 피보나치수열 재귀/반복문 손코딩

private static int recursiveFibonacci(int index) {
        if (index <= 2){
            return 1;
        }
        return recursiveFibonacci(index - 1) + recursiveFibonacci(index - 2);
    }

▶ 팩토리얼의 재귀/반복문 손코딩 

private static int recursiveFactorial(int num) {
    if(num > 1) {
        return recursiveFactorial(num -1) * num;
    }
    return 1;
}

 

😎 이분 탐색(Binary Search)이란?

탐색 범위를 두 부분으로 분할하면서 찾는 방식으로 처음부터 끝까지 돌면서 탐색하는 것보다 훨씬 빠른 장점이 있습니다. 

 

시간 복잡도

전체 탐색: O(N)

이분 탐색: O(logN)

 

과정

• 우선 정렬을 해야 함
• left와 right로 mid 값 설정
• mid와 내가 구하고자 하는 값과 비교
• 구할 값이 mid보다 높으면 : left = mid+1 구할 값이 mid보다 낮으면 : right = mid - 1
• left > right가 될 때까지 계속 반복하기

자바 코드로 구현

public static int solution(int[] arr, int M) { // arr 배열에서 M을 찾자
	
    Arrays.sort(arr); // 정렬
	
    int start = 0;
    int end = arr.length - 1;
    int mid = 0;

    while (start <= end) {
        mid = (start + end) / 2;
        if (M == arr[mid]) {
            return mid;
        }else if (arr[mid] < M) {
            start = mid + 1;
        }else if (M < arr[mid]) {
            end = mid - 1;
        }
    }
    throw new NoSuchElementException;
}

😎 DFS & BFS에 대해 설명해 주세요.

그래프 알고리즘으로, 문제를 풀 때 상당히 많이 사용하며 경로 찾는 문제에선 상황에 맞게 DFS와 BFS를 활용하게 됩니다.

 

DFS

• 루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법
• 모든 경로를 방문해야 할 경우에 적합
• 스택, 재귀함수를 통해 구현 

BFS

• 루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법
• 최소 비용에 적합
  • 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때
• 큐를 통해 구현

 

 

 

 

 

 

---

출처:

https://mangkyu.tistory.com/90

https://dev-coco.tistory.com/160

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html