YunaNote

동적 계획법 ( Dynamic Programming ) : 하나의 복잡한 문제를 한번에 해결하는 것이 아닌 여러 개의 작은 문제로 나눠 큰 문제를 점차적으로 해결할 때 사용한다 -> 점화식을 이용해 문제를 풀어나간다고 생각하면 된다. 동적 계산법 사용 조건 1. Overlapping Subproblems (중복되는 부분 문제) DP는 기본적으로 큰 문제를 나누고 여러 부분 문제로 나눠지며 부분 문제들이 중복해서 나타난다. 하지만 DP는 부분 문제의 결과를 저장하여 계산이 되어야하지만 부분 문제가 중복으로 나타나지 않아 재사용이 불가능한 경우 DP(동적계산법)을 사용할 수 없다. 2. Optimal Substructure(최적 부분 구조) 부분 문제의 최적의 값을 이용해 큰 문제에 영향을 받지 않고 항상 ..

그리디 (Greedy) / 탐욕 알고리즘 : 현재 상황에서 최적이라고 생각하는 해를 선택하는 방법이다. 하지만 앞으로 남은 단계의 선택을 고려하지않고 현재 단계의 가장 최선의 선택만 고려하기 때문에 항상 최적해를 보장하지않는다. 각 단계에서 최선의 선택한 결과가 전체적으로 최선이길 바라는 알고리즘이다. 예를 들어, 아래 트리구조의 경로가 있고 가장 적은 거스름돈을 남기는 것을 목적을 해보자. 가장 적은 거스름돈을 남기기 위해선 파란색 경로로 이동해야 하지만 단계별로 높은 금액을 선택하는 그리디 방법은 빨간색 경로로 이동하여 900원의 거스름돈을 남긴다. ⭐ 최적의 해를 도출하기 위한 2가지 조건 탐욕스런 선택 조건(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않음..

브루트포스(Brute Force) Brute(난폭한) + Force(힘) = 완전 탐색 알고리즘이라 불리며 모든 경우의 수를 탐색하며 요구조건에 충족한 결과만 가져온다. 모든 영역 전체를 탐색 BFS(너비 우선), DFS(깊이 우선) , 순차 탐색 등을 사용 특징 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식 암호학에서 가장 확실한 방법으로 통용되고 있으며 100% 정확도를 보장 완벽한 병렬 작업이 가능 But, 시간적인 측면에서 비효율적인 알고리즘 대표 문제 [ 백준 ] 브루트포스 - 블랙잭 브루트포스란? brute [짐승, 짐승같은, 난폭한 ] + force [ 힘, 무력, 폭력 ] 의 합성어로 짐승같은 힘, 난폭한 힘, 완전 탐색 알고리즘이라고 말할 수 있다. 완전 탐색?? 모든 경우의 수를 ..