신입 개발자 기술면접 질문 정리 - 알고리즘

목차

1. 동적 계획법(DP, Dynamic Programming)에 대해 설명해주시오.
2. 동적 계획법(DP, Dynamic Programming)이 갖는 2가지 조건은 무엇인가요?

1) 동적 계획법(DP, Dynamic Programming)에 대해 설명해주시오.

• 주어진 문제를 풀기 위해, 문제를 여러 개의 하위 문제로 나우어 푸는 방법
• 어떤 부분 문제가 다른 문제들을 해결하는데 사용될 수 있어, 답을 여러번 게산하는 대신 한번 만 계산하고
  그 결과를 재활용하는 메모이제이션기법으로 속도를 향상 시킬 수 있다.

1-1) 메모이제이션

• 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 재사용 함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를
  빠르게 하는 기술

1-2) DP 사용 예

• 체스, 바둑 등의 게임 전략 최적화
• 경제학, 금융 분야의 의사결정 문제
• 캐시 교체 정책 최적화
• 자원 할당 및 스케줄링 문제
• 네트워크 라우팅 아로길즘

1-3) 장점

• 최적의 해 도출 : 모든 가능한 경우를 고려하여 최적의 해를 찾아 낼 수 있다.
• 계산 속도 향상 : 중복된 계산을 피하고 이전에 계산한 겨로가를 재사용하여 계산 속도 향상

1-4) 단점

• 모든 가능성 고려 : 문제의 크기가 커질수로 계산 복잡도가 높아짐
• 메모리 사용량 : 중복 계산을 피하기 위해 결과를 저앙해야 하므로, 메모리 사용량이 증가

2. 동적 계획법(DP, Dynamic Programming)이 갖는 2가지 조건은 무엇인가요?

1) 중복되는 부분 문제

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

2) 최적 부분 구조

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

출처

신입 개발자 기술면접 질문 정리 - 알고리즘