[鐘萬冊] 02.問題解決戦略

問題解決のプロセス

• 問題を読んで理解する。

• 問題を身近な用語で再定義する。

• どのように解くか計画を立てる。

• 計画を検証する。

• プログラムで実装する。

• どのように解決したかを振り返り、改善する方法があるか探す。

1) 問題を読んで理解する

問題を読み間違えないように、問題を積極的に読み、問題が求めていることを完全に理解しようとする努力が必要です。些細な制約条件を見逃してしまうと解けなくなる場合も多く、大会では小さなミスも許されない場合がほとんどだからだ。

2) 再定義と抽象化

自分が扱いやすい概念を使って、問題を自分の言語で解くこと、問題が要求することを直感的に理解するために必要なプロセスであり、複雑なプロセスであればあるほど重要である。 問題の本質をどのような方法で再構成するかによって、同じことをするプログラムでも全く違うものになる。 難しい問題を簡単に、簡単な問題を難しく解くことができるので、抽象化がプログラムが進むべき方向を決定すると見ることができる。

抽象化: 現実世界の概念を私たちが扱いやすい数学的/計算学的概念に置き換えて表現する過程。

3) 計画を立てる

問題をどのように解決するかを決定し、使用するアルゴリズムとデータ構造を選択する過程。最も重要な過程であり、問題を見てすぐに解決方法が思い浮かばない場合、この過程で最も多くの悩みを抱えることになる。

4) 計画を検証する

実装を始める前に計画を検証する段階を経なければならない。この過程で、私たちが設計したアルゴリズムがすべての場合について要求条件を正確に実行することを証明し、実行にかかる時間と使用するメモリが問題の制限内に収まることを確認しなければならない。

5) 計画を実行する

実装においては、効率性と正確性を常に考慮すること。

6) 回顧すること

すぐに直接的な影響はないが、長期的に最も大きな影響を与える段階。 一度解いた問題をもう一度解くことで、より効率的なアルゴリズムを見つけたり、簡潔なコードを書くことができるようになったり、同じアルゴリズムを誘導できるより直感的な方法を見つけたりすることができます。 効果的に回顧を行う方法としては、問題を解くたびに自分の経験を記録に残すことが一番有効だと思います。

アプローチ方法、決定的な気づき、誤答の原因などを記録することで、間違いを減らし、パターン化に役立つこともある。解決した他の人のコードを確認することで、思いもよらない洞察を得ることもある。

解決できなかった場合でも、一定時間が経過したら他の人のコードや解答を参照するが、必ず復習を伴うこと。

問題解決戦略

1) 直感と体系的なアプローチ

• 似たような問題を解いたことがあるか？

  • 単純に解いた経験ではなく、原理の理解と変形が可能でなければならない。

• 単純な方法から始められるか？

  • 無知で解けるか？から始まる最も単純なアルゴリズムを作り、最適化を通じて実装する方法も存在する。

  • アルゴリズムの効率のベースラインを決めることができる。

• 私が問題を解く過程を数式化できるだろうか？

  • 問題に与えられた例題などを解きながら定式化する

• 問題を単純化できないだろうか？

  • 与えられた問題のもう少し簡単な変形版を先に解いてみること。

• 絵で描いてみることはできないだろうか？

  • 幾何学的な図形の方が直感的に受け止めやすい。

• 数式で表現できるか？

  • 平文 → 数式が問題を解決するのに役立つ可能性がある。

• 問題を分解できるだろうか？

  より扱いやすい形に問題を変形させる方法のうち、制約条件を分解する方法 *制約条件の分解方法

• 後ろから考えて問題を解くことができるか？

  • 代表的な例：ラダーゲーム

  • 前面からすべてのルートを試すよりも、到着地から逆方向に乗ることで回数を減らすことができる。

• 順番を強制することができるか？

  順序のない問題に順序を強制する方法 * 順序のない問題に順序を強制する方法

  • 例示：1つの変数に対して変形をするか、しないか、2つの場合しか存在しない / 順序が関係ない → 順番に変形するかしないかを決めるケース

• 特定の形の答えだけを考慮できるのか？

  • 正規化手法

  • 様々な答えのうち、形は違うが結果的に同じものをグループ化し、グループの代表的なものだけを考慮する方法。