알고리즘/알고리즘 이론 및 응용3 다이나믹 프로그래밍이란? 작은 문제로 나누고 메모이제이션하는 기법 안녕하세요, 김코딩스타입니다. 오늘은 프로그래밍 블로그 코딩의 신에서 다이나믹 프로그래밍에 대해 알아보겠습니다. 다이나믹 프로그래밍이란 무엇이고, 어떤 문제에 적용할 수 있는지, 그리고 어떤 방법으로 구현할 수 있는지에 대해 자세히 설명해드릴 예정입니다. 다이나믹 프로그래밍을 이해하고 활용하면 프로그래밍의 세계가 훨씬 넓어지고 재미있어질 것입니다. 그럼 시작해볼까요? 다이나믹 프로그래밍이란? 다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누어 푸는 분할 정복 기법의 일종입니다. 다만, 분할 정복과 다른 점은 작은 문제들이 중복되어 발생한다는 것입니다. 즉, 같은 문제를 반복적으로 풀어야 하는 경우가 많습니다. 이런 경우에는 작은 문제의 해답을 저장해두고, 필요할 때마다 꺼내서 사용하는 방식으로 시간을 절.. 2023. 9. 5. 프로그래밍 기초, 최소비용 신장트리 알고리즘 이해하기 프로그래밍에서 그래프를 다루는 문제들은 많이 나오는데요, 그 중에서도 특히 최소비용신장트리를 구하는 문제는 자주 출제되는 유형입니다. 최소비용신장트리란, 그래프의 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리를 말합니다. 예를 들어, 도시들을 연결하는 도로를 건설할 때, 최소한의 비용으로 모든 도시를 연결하려면 어떻게 해야 할까요? 이런 문제를 해결할 수 있는 알고리즘이 바로 최소비용신장트리알고리즘입니다. 이 알고리즘은 크게 두 가지 방법으로 구현할 수 있는데, 바로 크루스칼 알고리즘과 프림 알고리즘입니다. 이번 포스팅에서는 이 두 가지 알고리즘의 원리와 구현 방법에 대해 자세히 알아보겠습니다. 크루스칼 알고리즘은 간단히 말하면, 가중치가 작은 간선부터 차례대로 선택하면서 최소비용신장트리를.. 2023. 8. 11. 알고리즘 이론 및 응용 프로그래밍을 하다보면, 다양한 문제를 해결해야 할 때가 있습니다. 예를 들어, 정렬, 탐색, 최단 경로 등의 문제를 효율적으로 해결하려면 어떻게 해야 할까요? 이런 경우에 사용할 수 있는 것이 알고리즘입니다. 알고리즘이란 무엇이고 왜 필요한지 알아보겠습니다. 알고리즘이란 어떤 문제를 해결하기 위한 절차나 방법입니다. 알고리즘은 입력과 출력, 유한성, 명확성, 효율성 등의 조건을 만족해야 합니다. 알고리즘은 다양한 종류가 있으며, 각각의 알고리즘은 특정한 목적과 환경에 적합하게 설계되었습니다. 알고리즘의 종류와 특징을 알아보기 전에, 먼저 알고리즘을 분석하는 기준에 대해 알아보겠습니다. 알고리즘을 분석하는 기준은 크게 두 가지입니다. 바로 시간 복잡도와 공간 복잡도입니다. 각각의 기준에 대해 자세히 알아보.. 2023. 6. 12. 이전 1 다음