본문 바로가기
반응형

메모이제이션3

메모이제이션을 통한 성능개선 (3) - DFS DFS(Depth First Search)는 그래프 탐색 및 다양한 문제를 해결하는 데 널리 사용되는 알고리즘입니다. 이 알고리즘에 메모이제이션(Memoization)을 활용하면 중복 계산을 제거하고 효율성을 극대화할 수 있습니다. 이번 포스팅에서는 DFS와 메모이제이션의 결합 아이디어를 설명하고, C, Java, Python 예제 코드와 함께 성능 비교를 통해 차이를 분석하겠습니다.1. DFS와 메모이제이션이란?DFS (Depth First Search)깊이 우선 탐색으로, 그래프의 한 경로를 끝까지 탐색한 뒤 다른 경로를 탐색합니다.백트래킹과 결합하여 다양한 문제를 해결할 수 있습니다.메모이제이션계산한 값을 저장하여 동일한 계산을 반복하지 않도록 하는 기술입니다.DFS와 결합하면 중복된 상태를 다시 .. 2024. 12. 21.
메모이제이션(Memoization) 적용을 통한 성능 개선 (2) - 백트래킹 백트래킹(Backtracking)은 문제를 해결하기 위해 모든 가능한 경우를 탐색하되 가지치기를 통해 확인할 필요가 없는 경우는 생략하는 기법입니다. 하지만, 중복된 계산이 많아질 경우 성능 문제가 발생할 수 있습니다. 이런 문제를 해결하기 위해 메모이제이션(Memoization)을 적용하면 효율을 크게 향상시킬 수 있습니다. 이번 글에서는 백트래킹과 메모이제이션을 결합하는 방법을 설명하고, C언어, Java, Python으로 구현한 예제 코드를 통해 두 접근법의 차이를 비교해 보겠습니다. 1. 백트래킹과 메모이제이션이란?백트래킹가능한 모든 경우를 재귀적으로 탐색하며 해를 찾는 알고리즘입니다.조건에 맞지 않는 경로는 빠르게 포기(가지치기, Pruning)하여 탐색을 줄이는 방식으로 동작합니다.메모이제이션.. 2024. 12. 21.
다이나믹 프로그래밍 개념부터 활용까지 완벽 정리 - 메모이제이션, 반복문, C, Java, Python 예시코드 다이나믹 프로그래밍(Dynamic Programming, DP)은 알고리즘 문제 풀이에서 매우 중요한 기법입니다. 많은 사람들이 처음에는 어려워하지만, 원리를 이해하면 복잡한 문제도 효율적으로 해결할 수 있습니다. 이번 글에서는 다이나믹 프로그래밍의 개념, 원리, 시간복잡도, 구현 방법(메모이제이션과 반복문 방식), 장단점, 대표적인 코딩테스트 문제, 그리고 C, Java, Python 예제 코드를 소개하겠습니다.1. 다이나믹 프로그래밍의 개념다이나믹 프로그래밍은 문제를 작은 하위 문제로 나누고, 이를 해결한 결과를 저장해두었다가 나중에 재사용하는 알고리즘 기법입니다. Overlapping Subproblems(중복되는 부분 문제)와 Optimal Substructure(최적 부분 구조)라는 두 가지 속.. 2024. 12. 20.
반응형

티스토리툴바