Algorithme
[BOJ-2579] Problème de montée d'escaliers et programmation dynamique (Golang)
Introduction En fait, je n’ai pas pratiqué la programmation dynamique depuis trop longtemps et, même quand je l’ai fait auparavant, je l’ai simplement traitée comme quelque chose d’existant sans vraiment m’y plonger. C’était peut-être cela le problème, car je n’avais jamais touché à ce sujet. C’est pourquoi j’ai décidé d’étudier la programmation dynamique comme il se doit et de résoudre un problème. Qu’est-ce que la programmation dynamique ? La programmation dynamique (Dynamic Programming, DP) est une technique de conception d’algorithmes qui consiste à diviser un problème en sous-problèmes plus petits. Cette technique est généralement utilisée pour des problèmes d’optimisation et fonctionne en utilisant la mémoïsation (Memoization) ou des tableaux pour sauvegarder et réutiliser les résultats de calcul précédents afin de résoudre efficacement les sous-problèmes qui se chevauchent.
26 mai 2025
[Programmers] Joystick (Golang)
Problème Programmers - Joystick Complétez le nom alphabetique avec le joystick. Au départ, il est composé uniquement de A. ex) Si le nom à compléter fait trois lettres, c'est AAA, si quatre lettres, c'est AAAA. En déplaçant le joystick dans chaque direction, cela se présente comme suit : ▲ - Lettre suivante ▼ - Lettre précédente (en déplaçant vers le bas depuis A, on arrive à Z) ◀ - Déplacer le curseur à gauche (si on est au premier caractère et qu'on déplace à gauche, le curseur ira au dernier caractère) ▶ - Déplacer le curseur à droite (si on est au dernier caractère et qu'on déplace à droite, le curseur ira au premier caractère) Par exemple, on peut obtenir "JAZ" de la manière suivante : - À partir de la première position, manipulez le joystick vers le haut 9 fois pour compléter J. - Déplacez le joystick à gauche 1 fois pour amener le curseur à la dernière position. - À la dernière position, manipulez le joystick vers le bas 1 fois pour compléter Z. Ainsi, il est possible de créer "JAZ" avec 11 mouvements, ce qui est le minimum. Lorsque le nom que l'on veut créer, name, est donné comme paramètre, créez une fonction solution qui retourne le nombre minimum de manipulations du joystick pour ce nom. Ce problème est classé dans la partie pratique des tests de programmation sous le niveau 2, mais je trouve personnellement que c’est un problème plus difficile qu’il n’y paraît.
26 mai 2025
[Programmers] Inspection d'entrée (Golang)
Problème Problème de Programmers Inspection d’entrée Il y a n personnes qui font la queue pour l'inspection d'entrée. Chaque agent d'inspection a un temps de traitement différent. Au départ, toutes les barrières d'inspection sont vides. Une seule personne peut être inspectée simultanément à chaque barrière. La personne en tête de la queue peut aller à la barrière d'inspection vide et passer l'inspection. Cependant, si une barrière d'inspection peut traiter plus rapidement, elle peut attendre et aller là-bas pour être inspectée. Nous voulons minimiser le temps nécessaire pour que tout le monde passe l'inspection. La fonction solution doit renvoyer le temps minimal nécessaire pour que toutes les personnes soient inspectées, lorsque le nombre de personnes attendant l'inspection n (n) et un tableau times contenant le temps nécessaire pour qu'un agent d'inspection traite une personne sont donnés comme paramètres. Restrictions - Le nombre de personnes attendant l'inspection est d'au moins 1 et d'au plus 1 000 000 000. - Le temps nécessaire à chaque agent d'inspection pour traiter une personne est d'au moins 1 minute et d'au plus 1 000 000 000 minutes. - Le nombre d'agents d'inspection est d'au moins 1 et d'au plus 100 000. Approche En général, pour un tel large éventail, il est possible de résoudre le problème par recherche binaire.
23 mai 2025
[BOJ-3273] Résolvons le problème de la somme de deux nombres de deux manières (Hash, Two Pointers) avec Go
Problème Accéder à BOJ-3273 n nombres entiers positifs distincts a1, a2, ..., an composent une séquence. La valeur de ai est un entier naturel qui est supérieur ou égal à 1 et inférieur ou égal à 1000000. Quand on nous donne un nombre naturel x, écrivons un programme pour compter le nombre de paires (ai, aj) telles que ai + aj = x (1 ≤ i < j ≤ n). Le problème consiste à déterminer si une somme correspond au nombre désigné x dans le tableau donné comme ci-dessus.
21 mai 2025
[BOJ-9934] Arbre binaire complet (Golang)
Aperçu En préparant un changement de carrière, j’ai revisité les algorithmes d’arbre et j’ai décidé de rédiger ce post. Le problème d’arbre binaire complet consiste à déterminer la forme d’un arbre binaire complet à partir d’un tableau représentant l’ordre d’un parcours infixe. Il est donc essentiel de comprendre le concept de parcours infixe. Parcours infixe Les notions de parcours préfixe, infixe et postfixe se basent sur la position du nœud.
21 mai 2025