アルゴリズム
[BOJ-2579] 階段登り問題と動的プログラミング (Golang)
はじめに 実際に動的プログラミングをずっとやっていなかったためか、昔にやったときもただそういうものがあるんだなという程度で終わってしまったことが問題だったのか、今回の問題には手を付けられなかった。 そのため、今回は動的プログラミングをしっかり勉強しようと心に決めて、問題を解いてみた。 動的プログラミング(Dynamic Programming)とは？ 動的プログラミング（Dynamic Programming、DP）は、問題を小さなサブ問題に分けて解決するアルゴリズム設計手法である。この手法は主に最適化問題に使用され、重複するサブ問題を効率的に解決するためにメモ化（Memoization）またはテーブルを使用して以前の計算結果を保存・再利用する形で動作する。 動的プログラミングは以下の2つの主な特性を持つ： 最適部分構造（Optimal Substructure）：問題の最適な解決方法はサブ問題の最適な解決方法で構成できる。 重複するサブ問題（Overlapping Subproblems）：同じサブ問題が複数回計算されることがある。 代表的な例としてフィボナッチ数列（Fibonacci Sequence）の計算がある。フィボナッチ数列は以下のような再帰式を持つ。 $$f(n) = f(n - 1) + f(n - 2)$$ 解く方法はトップダウン方式とボトムアップ方式がある。トップダウン方式は再帰を使用してサブ問題を解決し、ボトムアップ方式は繰り返しを使用してサブ問題を解決するという点が異なる。 フィボナッチ数列を求める動的プログラミングを使ったコードは以下の通りである。 トップダウン方式 (Top-Down Approach) package main import "fmt" var memo = make(map[int]int) func fibonacci(n int,) int { if n <= 1 { return n } if val, exists := memo[n]; exists { return val } memo[n] = fibonacci(n-1) + fibonacci(n-2) return memo[n] } func main() { n := 10 result := fibonacci(n) fmt.Println("Fibonacci(", n, ") =", result) } } ボトムアップ方式 (Bottom-Up Approach) package main import "fmt" func fibonacci(n int) int { if n <= 1 { return n } fib := make([]int, n+1) fib[0], fib[1] = 0, 1 for i := 2; i <= n; i++ { fib[i] = fib[i-1] + fib[i-2] } return fib[n] } func main() { n := 10 result := fibonacci(n) fmt.Println("Fibonacci(", n, ") =", result) } } 核心ロジックを見ると、トップダウン方式は再帰とメモ化テーブルmemoを使用して重複するサブ問題を解決し、ボトムアップ方式は繰り返しを使用してサブ問題を解決している。
2025年5月26日
[プログラマーズ] ジョイスティック (Golang)
問題 プログラマーズ - ジョイスティック ジョイスティックでアルファベットの名前を完成させてください。最初はAで構成されています。 ex) 完成させなければならない名前が三文字ならAAA、四文字ならAAAA ジョイスティックを各方向に動かすと、以下のようになります。 ▲ - 次のアルファベット ▼ - 前のアルファベット (Aから下に移動するとZに) ◀ - カーソルを左に移動 (最初の位置から左に移動すると最後の文字にカーソル) ▶ - カーソルを右に移動 (最後の位置から右に移動すると最初の文字にカーソル) 例えば以下の方法で"JAZ"を作成できます。 - 最初の位置でジョイスティックを上に9回操作してJを完成させます。 - ジョイスティックを左に1回操作してカーソルを最後の文字の位置に移動させます。 - 最後の位置でジョイスティックを下に1回操作してZを完成させます。 したがって11回移動させて"JAZ"を作成でき、これが最小移動です。 作りたい名前nameが引数として渡されたとき、名前に対するジョイスティック操作回数の最小値を返すようにsolution関数を作成してください。 この問題はコーディングテスト練習のパートでLEVEL2に分類されていますが、実際にはなぜLEVEL2なのか疑問に思うほど、思ったより私には難しい問題でした。
2025年5月26日
[プログラミング] 入国審査 (Golang)
問題 プログラミング問題 入国審査 n人が入国審査のために並んで待っています。それぞれの入国審査官が審査するのにかかる時間は異なります。 最初はすべての審査場は空いています。一つの審査場では同時に一人だけ審査を行うことができます。最前列にいる人は空いている審査場に行って審査を受けることができます。ただし、より早く終わる審査場がある場合は、そこを待ってから行くこともできます。 すべての人が審査を受けるのにかかる時間を最小にしたいと思います。 入国審査を待っている人数 n と、各審査官が一人を審査するのにかかる時間の配列 times がパラメータとして与えられたとき、すべての人が審査を受けるのにかかる時間の最小値を return するように solution 関数を作成してください。 制限事項 - 入国審査を待っている人数は 1 人以上 1,000,000,000 人以下です。 - 各審査官が一人を審査するのにかかる時間は 1 分以上 1,000,000,000 分以下です。 - 審査官は 1 人以上 100,000 人以下です。 アプローチ 一般的にこのように範囲が広い場合、二分探索を通じて問題を解決できます。
2025年5月23日
[BOJ-3273] 2つの数の合計問題を2つの方法で解決しよう (ハッシュ法, 2ポインタ) With Go
問題 BOJ-3273 こちらをクリック n個の異なる正の整数 a1, a2, ..., an からなる数列がある。 aiの値は1以上、1000000以下の自然数である。 自然数 x が与えられたとき、 ai + aj = x (1 ≤ i < j ≤ n) を満たす (ai, aj) の組み合わせの数を求めるプログラムを書け。 上記のように与えられた配列の中で、合計が指定された数 x になるかを問う問題である。
2025年5月21日
[BOJ-9934] 完全二分木 (Golang)
概要 転職を準備しながら、久しぶりに木のアルゴリズムを勉強することになり、投稿することになった。 完全二分木の問題は、中間順序の配列を通じて完全二分木の形を知り、それを出力する問題で、まず中間順序という概念を理解しておく必要がある。 中間順序 前順/中順/後順の基準はノードの視点を見て判断する。 ノード -> 左の部分木 -> 右の部分木の順番で行うと、ノードが前にあるので前順であり、 左の部分木 -> ノード -> 右の部分木の順番で行うと、ノードが真ん中にあるので中間順である。 左の部分木 -> 右の部分木 -> ノードの順番で行うと、ノードが最後に来るので後順である。 この中で調べる方法は中間順であり、順番を巡る例は次の画像のようである。 完全二分木 完全二分木は木のデータ構造があるとき、木の高さ hに対して全ノード数が 2^h-1を満たす二分木を言う。 二分木はすべてのノードの子の数が最大2つである木を意味する。 簡単に言えば、指定した高さに対してすべてのノードが満たされた状態の木を意味する。 例えば、高さが1の下記の木は単純に下のようにノードが一つだけある場合である。 ノードの個数 = 2^1-1 = 1 高さが2であれば、次のように3つのノードを持つ木になる。 問題解決 まず中間順の結果を見てみよう。 問題で与えられた木は次のようであり、 この木を中間順に巡った結果の例入力は[1, 6, 4, 3, 5, 2, 7]である。 配列を見れば、配列自体が何か木のように見えることがわかるが、 次のような配列を、
2025年5月21日