728x90 Algorithm Practice12 동적 계획법(DP,Dynamic Programing) 동적 계획법(DP,Dynamic Programing)다이나믹 프로그래밍은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 문제를 해결하기 위해 사용되는 정차적인 방법 또는 계획으로정렬 알고리즘, 검색 알고리즘, 그래프 탐색 등을 사용한다. DP와 재귀적 호출의 차이점1. 하향씩 , 상향식 접근재귀적 호출은 주로 하향식 접근 방식을 사용하며, 큰 문제를 작은 하위 문제로 나누어 해결하는 방식이다.반면 동적 계획법은 주로 상향식 접근 방식을 사용하며, 작은 하위 문제들로부터 시작해 그 결과를 저장하고 이를 이용해 점진적으로 큰 문제의 해를 구한다. 2. 메모이제이션(Memoization) 동적 계획법은 중복되는 계산 결과를 저장하는 메모리 기법인 메모이제이션을 사용합니다.이.. 2024. 10. 24. 이분 탐색(Binary Search) 정렬된 리스트(배열)에서 원하는 값의 존재 여부를 찾는 알고리즘반드시 리스트(배열)를 정렬해서 사용해야 하는 단점을 가지고있음탐색할 때마다 검사 범위가 절반으로 줄여든다. 재귀,반복문,STL이용하여 실행하며재귀 : 코드 구조가 간결하고 이해하기 쉽지만 큰 배열에 대해 탐색할 경우 메모리초과 발생할 수 있음반복문 : 재귀적 방법에 비해 코드가 약간 더 길어 질 수 있으며, 복잡해지고 이해하기 어려울 수 있음.STL : 다양한 상황에서 안정적으로 작동하며, 범위 기반의 다양한 알고리즘 사용으로 코드 재사용성과 유연성이 높음 시간 복잡도는 O(log N)이다. 진행 과정1. 검사 범위에서 중간 값(mid)를 선택해서 찾고자 하는 값이 같은지 확인한다.2. 만약 찾고자 하는 값이라면 해당 값을 반환3. 찾고자 .. 2024. 10. 23. 최단 경로 알고리즘 최단 경로 알고리즘최단 경로 알고리즘은 그래프 내의 두 정점 사이에서 가장 짧은 경로(최소 비용 또는 최소 거리를 가진 경로)를 찾는알고리즘 입니다. 이 알고리즘들은 다양한 상황에서 사용되며, 각 알고리즘은 특정한 그래프 특성(음수 가중치, 방향성)에 따라 적합하게 선택됩니다. 이러한 최단 경로 알고리즘에는 크게 네 가지가 있습니다.1. 다익스트라 알고리즘(Dijkstra's Algorithm)2. 벨만 포드 알고리즘 (Bellman-Ford Algorithm)3. 플로이드 위셜 알고리즘(Floys-Warshall Alogorithm)4. A* 알고리즘 (A-Star Algorithm) 1. 다익스트라 알고리즘(Dijkstra's Algorithm)다익스트라 알고리즘은 가중치가 양수인 그래프에서 한 .. 2024. 10. 23. 몬테카를로 알고리즘(MonteCarlo Algorithm) 몬테카를로 알고리즘 몬테카를로 알고리즘은 무작위로 문제를 해결하거나 탐색하는 기법으로, 랜덤한 선택을 통해 해답을 찾고, 해당 해답이 올바른지 여부를 평가하는 과정을 반복하는 확률적 또는 추정 기반문제 해결에 사용한다. 그렇기에 결과가 항상 정확하지는 않지만 빠르게 근사치 해를 찾을 수 있는 경우가 많다. 백트래킹과 DFS는 체계적인 탐색을 통해 최적의 답을 보장하지만, 몬테카를로는 무작위 탐색을 통해 빠른 근사 해를 찾는 방식이다. 따라서 백트래킹은 완전 탐색방식이라면, 몬테카를로 알고리즘은 불확실성과 확률에 기반한 방식이다. 조건상태 공간 트리에서 같은 수준(Level)에 있는 모든 노드에서는 같은 유망함수를 사용해야 한다.상태 공간 트리에서 같은 수준에 있는 모든 노드들은 같은 수의 자식노드들을 가.. 2024. 10. 23. 이전 1 2 3 다음 728x90
