CordCat

https://www.acmicpc.net/problem/9095 6개 211111 2311 2 두 개 -> 22111 5! / (2!*3!) 2 3개 -> 2221 4!/3! 4 3 하나 -> 31111 5! / 4! 3 두개 -> 331 3! / 2! 2 하나 + 3 하나 -> 2311 4!/2! -> 12 2 두개 + 3 하나 -> 223 3 이런 식으로 경우의 수를 나눠 순열조합으로 풀 수 있을 거라 생각을 해서 아래와 같이 문제를 풀었다. 순열을 이용한 풀이 import java.util.*; public cl..

DP는 다양한 문제에서 사용되는 효율적인 알고리즘 기법 중 하나이다. 코딩테스트 문제를 풀다가 최단 경로 문제에 DP의 필요성을 알게 돼서 DP에 대해 정리해 본다. 최단 경로 문제는 출발지에서 도착지까지 가는 경로 중 가장 짧은 경로를 찾는 문제로, 다익스트라 알고리즘과 벨만-포드 알고리즘이 대표적인 예시이다. DP 배열은 중복 계산을 피하기 위해 사용되며, 최단 경로 문제에서는 각 노드까지의 최단 거리를 저장하는 역할을 하고, 각 노드까지의 최단 거리를 DP 배열에 저장하면 다음 계산에서 이전 계산 결과를 활용하여 중복 계산을 피할 수 있다. 아래는 최단 경로 문제를 DP 배열로 해결하는 다익스트라 알고리즘을 사용하여 출발지에서 각 노드까지의 최단 거리를 구하는 예시 코드이다. import java...