문제 해결을 위한 전략적 접근
2020. 9. 22. 19:12ㆍComputer Science/알고리즘
코딩 테스트의 목적
- 문제 해결 여부
- 예외 상황과 경계값 처리
- 코드 가독성과 중복 제거 여부 등 코드 품질
- 언어 이해도
- 효율성
궁극적으로는 문제 해결 능력을 측정하기 위함이며 이는 '어떻게 이 문제를 창의적으로 해결할 것인가'를 측정하기 위함이라고 볼 수 있다.
접근하기
- 문제를 공격적으로 받아들이고 필요한 정보를 추가적으로 요구하여, 해당 문제에 대해 완벽하게 이해하는게 우선이다.
- 해당 문제를 익숙한 용어로 재정의하거나 문제를 해결하기 위한 정보를 추출한다. 이 과정을 추상화라고 한다.
- 추상화된 데이터를 기반으로 이 문제를 어떻게 해결할 지 계획을 세운다. 이 때 사용할 알고리즘과 자료구조를 고민한다.
- 세운 계획에 대해 검증을 해본다. 수도 코드 작성도 해당될 수 있고 문제 출제자에게 의견을 물어볼 수도 있다.
- 세운 계획으로 문제를 해결해본다. 해결이 안 된다면 앞선 과정을 되짚어본다.
생각할 때
- 비슷한 문제를 생각해본다.
- 단순한 방법으로 시작하여 점진적으로 개선해나간다.
- 작은 값을 생각해본다.
- 그림으로 그려본다.
- 수식으로 표현해본다.
- 순서를 강제해본다.
- 뒤에서부터 생각해본다.
해결 방법 분류
DP(동적 계획법)
복잡한 문제를 간단한 여러 개의 하위 문제(sub-problem)로 나누어 푸는 방법을 말한다.
DP 에는 두 가지 구현 방식이 존재한다.
- top-down : 여러 개의 하위 문제(sub-problem) 나눴을시에 하위 문제를 결합하여 최종적으로 최적해를 구한다.
- 같은 하위 문제를 가지고 있는 경우가 존재한다. 그 최적해를 저장해서 사용하는 경우 하위 문제수가 기하급수적으로 증가할 때 유용하다. 위 방법을 memoization 이라고 한다.
- bottom-up : top-down 방식과는 하위 문제들로 상위 문제의 최적해를 구한다.
Fibonacci 수열을 예로 들어보면,
top-down
f (int n) {
if n == 0 : return 0
elif n == 1: return 1
if dp[n] has value : return dp[n]
else : dp[n] = f(n-2) + f(n-1)
return dp[n]
}bottom-up
f (int n){
f[0] = 0
f[1] = 1
for (i = 2; i <= n; i++) {
f[i] = f[i-2] + f[i-1]
}
return f[n]
}
접근방법
- 모든 답을 만들어보고 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계한다.
- 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 저수만을 반환하도록 부분 문제 정의를 변경한다.
- 재귀 호출의 입력 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다.
- 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션할 수 있도록 조정한다.
- 메모이제이션을 적용한다.
Greedy (탐욕법)
모든 선택지를 골해보고 그 중 가장 좋은 것을 찾는 방법이 Divide conquer or dp 였다면 greedy 는 각 단계마다 지금 당장 가장 좋은 방법만을 선택하는 해결 방법이다. 탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다. 많은 경우 최적해를 찾지 못하고 적용될 수 있는 경우가 두 가지로 제한된다.
- 탐욕법을 사용해도 항상 최적해를 구할 수 있는 경우
- 시간이나 공간적 제약으로 최적해 대신 근사해를 찾아서 해결하는 경우
접근 방법
- 문제의 답을 만드는 과정을 여러 조각으로 나눈다.
- 각 조각마다 어떤 우선순위로 선택을 내려야 할지 결정한다. 작은 입력을 손으로 풀어본다.
- 다음 두 속성이 적용되는지 확인해본다.
- 탐욕적 성택 속성 : 항상 각 단계에서 우리가 선택한 답을 포함하는 최적해가 존재하는가
- 최적 부분 구조 : 각 단계에서 항상 최적의 선택만을 했을 때, 전체 최적해를 구할 수 있는가
Reference
'Computer Science > 알고리즘' 카테고리의 다른 글
| 코딩 테스트를 위한 Tip (0) | 2020.09.22 |
|---|