📚 [CS면접] 웹 면접 질문 [14] [알고리즘]

1. 동적 계획법(DP, Dynamic Programing) 이란 ?

주어진 문제를 풀기 위해, 문제를 여러 개의 하위 문제로 나누어 푸는 방법

동적 계획법에서는 어떤 부분 문제가 다른 문제들을 해결하는데 사용될 수 있어, 답을 여러 번 계산하는 대신 한 번만 계산하고 그 결과를 재활용하는 메모이제이션(Memoization) 기법으로 속도를 향상시킬 수 있다.

 

동적 계획법이 갖는 2가지 조건

1. 중복되는 부분(작은) 문제

중복되는 부분 문제는 나눠진 부분 문제가 중복되는 경우로, 메모이제이션 기법을 사용해 중복 계산을 없앤다.

 

2. 최적 부분 구조

최적 부분 구조를 가진다는 것은 문제의 최적해가 부분 문제의 최적해들로써 구성된다는 것이다.

 

2. 버블 정렬(Bubble Sort) 란 ?

버블 정렬은 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘이다.

0번 인덱스부터 n-1번 인덱스까지 n번까지의 모든 인덱스를 비교하여 정렬한다. 시간 복잡도는 O(n^2) 이다.

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

 

2. 선택 정렬(Selection Sort) 이란 ?

선택 정렬은 첫 번째 값을 두번째 부터 마지막 값까지 차례대로 비교하여 최솟값을 찾아 첫 번째에 놓고, 두 번째 값을 세 번째 부터 마지막 값까지 비교하여 최솟값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬하는 알고리즘이다. 시간복잡도는 O(n^2) 이다.

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

 

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