기본적인 문제 해결 방법

기본적인 문제 해결 접근 방법

넘버링 되어있지만, 순서는 없다.

• 순서대로 접근하진 않아도 되지만, 위에서 아래로 접근하는 것이 좋긴 하다.
• 상위 단계가 충분히 되어있지 않다면, 언제든 다시 위로 올라가는 것이 좋다.
• 하지만, 이 다섯가지가 정교하게 되어있어야, 흔들림 없고 견고한 결과물이 완성된다.
• 그렇다고 하더라도, 외부 요구사항이 “견고한 결과물” 보다, “돌아가는 결과물”을 원한다면, 이에 맞출 수 있는 것도 능력이다.
• 모든 것에는 트레이드오프가 있다. 현재 상황에 알아서 잘 판단하자.

접근 방법

1. 문제 정의
2. 문제 분석
3. 도구 선택
4. 구현
5. 평가

지금부터, 각각이 무엇을 의미하는지 설명하도록 하겠다.

문제 정의

현재 주어진 요구사항이 무엇인지 파악하고, 문제에 맞는 종속변수 y, 상수 c, 독립변수 x를 명확히 정의하라!

다음과 같은 예제를 들어보도록 하겠다.

예제: Codeforces Div.2 #915 B번

https://codeforces.com/contest/1905/problem/B

굳이 들어가서 볼 필요는 없다. 번역본은 다음과 같다.

트리가 주어진다. 하나의 zelda-연산에서 다음과 같은 작업을 수행할 수 있다:

• 두 정점 u와 v를 선택한다;
• u에서 v까지의 경로에 있는 모든 정점을 하나의 정점으로 압축한다. 즉, u에서 v까지의 경로 상에 있는 모든 정점이 트리에서 제거되고, 새로운 정점 w가 생성된다.
• 그리고 경로 상의 어떤 정점과 인접했던 모든 정점 s는 정점 w와 인접하게 된다.

정점 1과 5에 대해 수행된 zelda-연산을 나타낸다.

문제: 트리가 오직 하나의 정점만 남을 때까지 최소 몇 번의 zelda-연산이 필요한지 구하라.

이 문제를 지금 풀지 말고, 문제의 요구사항을 명확히 판단한 뒤, 독립변수와 종속변수, 상수를 구분지어보자.

• 종속변수: 하나의 정점만 남을때까지 필요한 zelda-연산의 횟수
• 상수: 문제에서 정의되어서, 바꿀 수 없는 것.
  • 입력으로 주어진 트리의 구조는 바꿀 수 없다.
  • 주어진 연산은, “두 정점이 지나는 모든 정점을 하나의 정점으로 압축”한다. 이 연산의 입력과 출력 결과값은 바뀔 수 없다.
  • 즉, 기능/입력에도 규칙이 있을 경우, 기능/입력도 상수처럼 관리할 수 있음을 명심하자.
• 독립변수: 내가 조절 가능한 것
  • 정점 두개를 어떻게 고를 것인가?
  • 나는 이 문제를 어떻게 해결할 것인가?
  • x를 자유롭게 정해보자. 나는 “두개의 리프 노드들을 고르는 규칙”을 독립변수 x로 정의했다.

그럼, 이런 경우 문제의 난이도가 올라가는 원인은 무엇일까?

난이도가 올라가는 원인 - 독립변수/종속변수/상수 개념이 두종류 이상 포함되어 있을 때.

• 여러 문제가 중첩되어 있을 때는, 한 세트의 x,y,c로 문제가 해결되지 않는 경우가 많다.
  • 예를 들어, 특정 정수 집합의 원소 중 최댓값을 찾는 연산의 경우, “모든 원소 이상인 정수들 중 최소 정수를 반환”한다고 할 수 있다.
    그렇다면, 모든 원소 이상인 수를 탐색하고, 그 수들 중 최소 정수를 찾는다면, 최댓값을 찾을 수 있을 것이다.
    (물론, 실제로 모든 원소 이상인 수는 무한하기 때문에, 이런 방식으로 구현하진 않는다.)
• 이럴때는 두가지 방식으로 접근한다.

1. 이전 문제의 풀이를, 현재 풀이에 응용한다
   • 이전의 해답으로 현재의 해답을 빠르게 구할 수 있을 경우 활용한다.
   • 대표적으로, 위에서 이야기한 “최댓값을 찾는 방법” 을 일반적으로 직접 찾을 때를 생각해보자.
   • 우리는 각 정수를 하나씩 보면서, “현재 내가 알고 있는 이 배열 내 최대 정수” 를 갱신해나간다.
2. 문제를 “쪼개서” Divide&Conquer로 해결해야 한다.
   • 두 문제 사이에 새로운 독립변수가 추가되어야 할 때 사용한다.
   • 문제를 A부터 해결한 뒤, 해결한 y에 추가 독립변수 x를 넣어 z를 얻어내야 한다.
   • 문제에서 요구하는 순서대로 처리할 수도 있고, 다른 관점으로 먼저 전처리한 뒤, 결과값을 합칠 수도 있다.

문제 분석

“구조적 사고” 로 접근해야 한다.

크게 “탑-다운”, “바텀-업” 두가지 방식으로 접근한다.

예제: 현재 회사에 있는 사람 중, 기운이 넘치는 사람과 기운이 없는 사람을 구분해보자.

• 탑-다운
  • 아침을 먹으면 기운이 있을 것 같은데, 아침을 먹은 사람과, 아침을 먹지 않은 사람으로 구분해보자.
• 바텀-업
  • 기운 넘치는 사람들을 모아 조사해보니, 다들 아침을 먹고 왔더라.
• 기준의 평가
  • 기준이 일관되어 있는가?
    • 아침을 먹은 사람은 모두 기운이 넘치는가?
    • 아침을 먹지 않은 사람은, 모두 기운이 없는가?
  • MECE를 지켰는가?
    • 중복되는 범주는 없는가?
      아침을 먹었으면서, 먹지 않은 사람은 없다.
    • 예외 범주는 없는가?
      아침을 먹지도, 안먹지도 않은 사람 또한 없다.
• 정답은 없다.
  • 중요한 것은 새로운 관점과 관찰이기 때문에, 어느 하나만 고집하지 않고, 둘을 자유롭게 전환하며 사용할 수 있어야 한다.
  • 이것이 “구조적 사고” 이다.

말만 들어보면, 굉장히 쉬워보인다.
그렇다면, 기준 선택에 있어서, 난이도가 올라가는 경우는 무엇일까?

난이도가 올라가는 원인 - 다중 분류 기준

만약 아침을 안먹은 사람들은 모두 기운이 없었는데, 아침을 먹은 사람들 중에도 기운이 없는 사람이 있었다고 해보자. 이럴땐, 우리는 여러가지 선택을 할 수 있다.

• 아침을 먹음/안먹음 개념이, 기운이 있고 없고를 가를 수 있는 기준이 아니다.
• 아침을 먹었어도, “700kcal” 이상 먹지 않으면, 기운이 없을 수도 있다.
• 아침을 먹었어도, 잠을 7시간 이상 자지 않았다면, 기운이 없을 수도 있다.

이처럼, 일관된 기준 수립은 매우 어려운 영역이다.
하지만, 아무것도 하지 않는 것보다, 이런 기준을 갖고 생각을 하게되면, 낭비하는 시간을 줄일 수 있다.

도구 선택

도구를 선택하는 것 또한, 충분한 고민이 이루어져야 한다.
그렇다면, 어떠한 방식으로 접근해야 할까?

나는 다음과 같은 방식을 제안한다.

득실 사이클 만들기

모든 선택지에는 트레이드오프가 존재한다.

• 만약 완벽해보이는 도구가 있다면, 해당 도구에 대해 잘 모른다고 봐야 한다.
• 만약 단점이 없어보이는 도구가 있다면, 해당 도구에 대해 잘 모른다고 봐야 한다.

• 따라서, 현재 고려하고 있는 도구의 장점과 단점을 분석한다.
  • 문제 분석을 하다 보면, 여러 도구들이 떠올랐을 것이다.
  • 각 도구들의 장점과 단점을 기록하고, 해당 단점이 극복되는 새로운 도구는 없는지 탐색해보자.
• 모든 도구들에 대한 분석이 끝나면, 각 도구들에 대한 장단점 사이클이 작성 완료되었을 것이다.
  • 이제 현재 주어진 요구사항을 가장 잘 만족하는 도구를 선택하자!

난이도가 올라가는 원인 - 문제 정의가 제대로 완료되지 않음

만약, 문제 정의가 제대로 완료되지 않았다면, 사용자의 요구사항의 경중을 파악하기 어렵고, 따라서 사용자의 요구사항이 아닌, “본인의 감정”에 따라 도구를 선택하게 될 수 있다.

예를 들어, A라는 문제를 해결할 기술이 있다고 해도, 해당 도구를 사용하게 되면 팀원이 학습 곡선을 마주하게 되고, 그로 인해 “납기일을 맞출 수 없는 경우”에는, 과감히 해당 도구를 포기할 결단력도 필요하다.

항상 원래 풀려고 하던 문제가 무엇이었는지 확인하고 검토하고 반영하는 습관을 들이자.

구현

굳이 설명하진 않겠다.

자신의 전문 지식으로, 선택한 도구를 실제로 적용해야 한다.

매우 구체적인 영역이기에, 분야마다 다르다고 생각한다.

평가 - QA

주어진 요구사항을 잘 만족했는지, 문제 정의를 되돌아보며 평가하자.

일반적으로, 문제 정의와 분석을 철저히 하는 사람은 도구 선택 과정에 소홀히 하는 경향이 있다.

• 현재 문제에 대한 “해결책”을 찾다가, 트레이드오프를 놓치는 경우다.
• 습관대로 도구를 선택하다 보니, 장점만 보고 도구를 선택했다가 후회하는 경우도 보았다.
  • 학습 및 유지보수 비용은 무료가 아니다.
• 단순히 deque을 사용하면 되는데, 굳이 lazy segement tree 를 사용하는 경우도 보았고,
• 단순히 DB의 네임드 락을 도입하면 되는데, 레디스의 분산 락을 도입하는 경우도 보았다.

도구 선택 과정을 철저히 하는 사람은, 문제 정의와 분석 과정을 소홀히 하는 경향도 자주 보았다.

• 모든 도구가 각각의 장단점을 갖고 있다보니, 하나의 도구를 결정하는 과정에 지나치게 오래 고민하는 사람들도 종종 보았다.
• 각 문제에 대한 경중이 제대로 분석이 안되어있어, 모든 문제를 완벽히 해결해주는 도구를 탐색하다가, 결정을 제대로 못내리는 경우도 보았다.
• 자신이 선택한 도구가 과연 적절할지, 확신을 못하는 경우가 대부분 이 경우에 속했다.
• “이거 조회 로직 오래걸릴 거 같은데, 과연 이걸 DB에 저장하는게 맞을까? 캐시를 도입해야 하는 거 아닌가?”
• “여기 나중에 확장될거 같은데, 과연 여기에 클래스를 직접 참조시키는게 맞을까?”

둘 다 안되는 경우도 있다.

• 저희 메모 앱의 리텐션을 올리기 위해, 계좌 송금 기능을 도입했습니다!
  • 계좌 송금 기능이 앱에 추가됨으로써, 메모 앱 기능 사용에 영향을 끼치는 것은 없는지?
  • 메모 앱에 계좌 송금 기능이 추가되면, 앱의 유지보수가 잘 되는지?
  • 그냥 계좌 송금 기능을 만들어보고 싶었던건 아닌지?
• 사용자가 100만명 몰릴것을 고려해, 캐시를 적용했더니 성능이 99.99% 감소했습니다.
  • 사용자가 100만명 몰릴것이라는 정량적, 정성적 분석 근거는?
  • 캐시와 DB를 비교했을때 캐시는 장점만 있나?
  • 이 조회 로직이 빠르게 응답해야 한다는 근거는?
  • 캐시를 적용했을 때 고려하였던 것은?
  • 그냥 캐시를 도입하고 싶었던건 아닌지?
• 이런 경우에서 가장 많이 발생하는 실수가, 결과를 위해 과정을 짜맞추는 상황이다.
• 항상 원래 문제는 무엇이었는지, 해당 도구가 최소비용으로 문제를 해결해주는지 검토하자.

지식은 이해와 반복의 영역이지만, 분석과 선택은 훈련의 영역이다.
스스로 피드백하고, 의식적으로 노력하지 않으면 평생 늘지 않는다.