Computer Science/알고리즘

문제 해결을 위한 전략적 접근

길순이 2020. 9. 22. 19:12

코딩 테스트의 목적

  1. 문제 해결 여부
  2. 예외 상황과 경계값 처리
  3. 코드 가독성과 중복 제거 여부 등 코드 품질
  4. 언어 이해도
  5. 효율성

궁극적으로는 문제 해결 능력을 측정하기 위함이며 이는 '어떻게 이 문제를 창의적으로 해결할 것인가'를 측정하기 위함이라고 볼 수 있다.

접근하기

  1. 문제를 공격적으로 받아들이고 필요한 정보를 추가적으로 요구하여, 해당 문제에 대해 완벽하게 이해하는게 우선이다.
  2. 해당 문제를 익숙한 용어로 재정의하거나 문제를 해결하기 위한 정보를 추출한다. 이 과정을 추상화라고 한다.
  3. 추상화된 데이터를 기반으로 이 문제를 어떻게 해결할 지 계획을 세운다. 이 때 사용할 알고리즘과 자료구조를 고민한다.
  4. 세운 계획에 대해 검증을 해본다. 수도 코드 작성도 해당될 수 있고 문제 출제자에게 의견을 물어볼 수도 있다.
  5. 세운 계획으로 문제를 해결해본다. 해결이 안 된다면 앞선 과정을 되짚어본다.

생각할 때

  • 비슷한 문제를 생각해본다.
  • 단순한 방법으로 시작하여 점진적으로 개선해나간다.
  • 작은 값을 생각해본다.
  • 그림으로 그려본다.
  • 수식으로 표현해본다.
  • 순서를 강제해본다.
  • 뒤에서부터 생각해본다.

 

해결 방법 분류

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]
}

 

접근방법

  1. 모든 답을 만들어보고 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계한다.
  2. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 저수만을 반환하도록 부분 문제 정의를 변경한다.
  3. 재귀 호출의 입력 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다.
  4. 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션할 수 있도록 조정한다.
  5. 메모이제이션을 적용한다.

Greedy (탐욕법)

 

모든 선택지를 골해보고 그 중 가장 좋은 것을 찾는 방법이 Divide conquer or dp 였다면 greedy 는 각 단계마다 지금 당장 가장 좋은 방법만을 선택하는 해결 방법이다. 탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다. 많은 경우 최적해를 찾지 못하고 적용될 수 있는 경우가 두 가지로 제한된다.

  1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 경우
  2. 시간이나 공간적 제약으로 최적해 대신 근사해를 찾아서 해결하는 경우

접근 방법

  1. 문제의 답을 만드는 과정을 여러 조각으로 나눈다.
  2. 각 조각마다 어떤 우선순위로 선택을 내려야 할지 결정한다. 작은 입력을 손으로 풀어본다.
  3. 다음 두 속성이 적용되는지 확인해본다.
  1. 탐욕적 성택 속성 : 항상 각 단계에서 우리가 선택한 답을 포함하는 최적해가 존재하는가
  2. 최적 부분 구조 : 각 단계에서 항상 최적의 선택만을 했을 때, 전체 최적해를 구할 수 있는가

Reference