알고리즘 & 라이브 코테의 접근 전략

기존 문제 해결 전략은 일반적으로 주어진 요구사항을 구현할 때의 접근 방식을 작성해두었다.

이번 글은 알고리즘과 라이브 코테로 제한해서 좀 더 자세하게 적어보려 한다. 

문제 풀이 단계 - 어떠한 순서대로 문제를 접근해야 하나?

1. 아이디어 획득 : “추론”하기
   • 이 시기는 체계젹인 상태 유지가 특히 중요한 시점이다.
     • 문제만 바라보고 있어선, 아무것도 변화하지 않는다.
   • 지금의 너는 문제를 제대로 이해하지 못하고 있다.
     • 놓친 조건은 없는지 검토하라.
     • 문제의 조건을 "우아한" 수준으로 정의할 수 있는지 검토해라.
   • 문제 알고리즘/특징의 “증명”으로 아이디어
     • 어떻게 이 동작이 수학적으로 증명되는가?
     • {BruteForce, Greedy, D&C, DP, Graph, math}
   • 전체 알고리즘이 “결국 구하고자 하는 것” 놓치지 않기
   • “책임” 뽑아내기
     • 각 기능들이 어떤 책임을 가지고 있는지
     • “어떤 패턴”으로 동작하는지
   • 가장 Naive한 상태/알고리즘부터 시작하기 (완전 탐색, 단순 자료구조)
   • 뚜렷한 증명이 나오지 않을 땐, 어떤 기준을 만들고 나눠서 보기
   • 뚜렷한 최적화 기법이 떠오르지 않을 땐, 문제에 주어진 특이한 특징을 잡기
   • 단위 동작의 조건 분기 파악
   • 가장 극단적인 경우에서 추론 (가장 차이가 뚜렷한 예제 or 가장 경계가 모호한 예제)
2. “처음”부터 경우의 수 직접 전개 (수식&도식화)
   • 알고리즘 내에 어떤 역할들이 있는지 → 직접 들어가보기
   • 알고리즘 내에 어떤 기능들이 있는지 → 직접 수행해보기
   • "끝까지 구체화"로 접근해야, "깔끔한 추상화"가 나온다.
3. cutting | 구현 (차근차근 단순화 & 최적화)
   • 문제 진행이 막힐 때마다, 수시로 문제를 재정의해라.
     • 수시로 왜 이렇게 된건지 의심해라.
     • 막연히 마법같은 논리와 알고리즘을 떠올리는 것보다, 수시로 내가 막힌 원인을 문제로 재정의하는 것이 현실적으로 도움이 된다.

문제 풀이 시의 규칙

1. 아무것도 하지 않는 대신 무언가를 수행하기. 체계적인 상태를 유지
   • 알고리즘의 작동 방식 “완전히”이해하려고 노력하기
2. 적어두기, 구하고자 하는 것의 계층 구조 표현하기.
   → 구하고자 하는 것이 무엇인지 정확히 & 입체적으로 파악
3. 한가지 접근방식에 얽메이지 말기 → 응용의 끝 알기
   • 경험이 중요한 이유!!!!
     • 경험이 없으면 응용의 끝을 알기 어렵다.
     • 어떠한 명제가 거짓임을 증명하는 과정은 어떠한 명제가 참임을 증명하는 과정만큼 어렵다.
     • 이는 만나는 모든 코딩 문제를 “똑똑함” 으로 해결하려는 것은 멍청한 짓인 이유임을 증명한다.
     • 효율을 위해선, 어느정도는 기존에 알던 지식으로 문제를 해결하는 “노련함”이 필요하다.

• 안되면 답지 보기. 지나치게 고민하지 말자. 문제 지문이 이해 안되면 → Test Case랑 함께 보기
• 문제를 정확히 읽고, 예제를 직접 전개하며 문제의 알고리즘이 어떻게 작동되는지 “완전히" ,"다방면으로” 이해하기. → “도식화”. 현재의 흐름을 잘 이어갈 수 있도록.
  • 내가 해당 알고리즘 안으로 들어갔을 때
    • 어느 역할들이 있는지
    • 각 역할들이 어떤 때 어느 동작들을 수행하는지
  • 각자 어떤 책임이 있는지를 빠르게 뽑아낼 것.
• 현재 주어진 정보를 바탕으로 그리디하게 “추론”하기. → “증명” → a→c 에서 a→b→c 를 만족하는 “b” 찾기.

최적화 테크닉

• 깔끔한 코드 & 빠른 테스트가 버그를 없앤다.
  • 깔끔한 조건문 전개 → 예외 발생 가능성이 낮은 조건문!
  • 갈수도/안갈수도 처리가 있을 땐 → 갈지 / 말지 조건문으로 결정하는 것보다, 일단 가놓고 이걸 써먹을지/말지 결정하는게 더욱 코드가 직관적이다.
• 시간 단축 테크닉
  • 순회/방문을 비트마스킹
  • 반복을 1회 연산 수식으로 압축
• 가정이 느슨하면 증명이 어려워지고, 증명이 거짓이 된다
• 가정이 엄격하면 증명은 참이 되지만, 전칭 한정이 불가능해진다.
• 사고 과정 : 백트래킹!
  • 응용의 끝을 알고, 이미 끝에 도착했을 경우,
  • 정확히 이전 단계가 어딘지를 알고 다시 돌아가서
  • 해당 단계에서 이전에 했던 생각을 지우고 다시 생각해보는 것.
  • 만약 잘못된 게 늘어나면, 차근차근 뒤로간다.

꼼꼼히 코딩했는지 검토할 때, 찾아야 할 것들

1. int 오버플로우, out of bounds
2. 특수한 경우 (n=1?)
3. 잘못된 가정 & 증명

“코드가 간결해야” 실수를 줄일 수 있다! (직관적인 코드, 더욱 단순한 풀이 로직)

문제의 난이도

• 나에게 좋은 난이도
  • 문제와 좀 씨름해서 품
  • 한단계 모자라서 못품 → 풀이 바로 전부 읽지 말기!
• 나에게 안좋은 난이도
  • 보자마자 풀이가 떠오름
  • 여러 단계 모자라서 못품