코린이의 코딩일기 코린이의 코딩일기

브루트 포스(brute force)완전탐색 알고리즘이다. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.브루트 포스의 장점은 예외없이 100%의 확률로 정답을 찾아낸다는 것이다. 대부분 반복문과 조건문을 통하여 답을 도출한다. 모든 경우의 수를 전부 탐색하기 때문에, 100%의 확률로 정답을 찾아내지만,모든 경우의 수를 전부 탐색하기 때문에, 높은 시간 복잡도를 갖는다.  완전 탐색과 브루트 포스 알고리즘의 차이 완전 탐색 알고리즘 : 모든 경우의 수를 전부 탐색하는 방식의 알고리즘, 결과보다는 탐색 과정에 중점을 둔다.브루트 포스 알고리즘 : 문제를 해결하기 위해, 모든 경우를 탐색하고 답을 도출하는 알고리즘, 결과를 찾는 것에 중점을 둔다. 브루트 포스의 기본적인..

분할 정복 알고리즘 한 번에 해결할 수 없는 큰 문제를 작은 문제들로 분할하여 작은 문제들 부터 문제를 해결하는 방법이다.분할 정복 알고리즘은 보통 재귀 함수를 통해 자연스럽게 구현한다.  분할 정복 동작과정 Divide원래 문제를 분할하여 비슷한 유형의 더 작은 하위 문제로 분할이 가능할 때까지 나눈다. Conquer각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위라면 탈출 조건을 설정하고 해결한다. CombineConpuer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다.  장점Top-dwon 재귀방식으로 구현하기 때문에 코드가 직관적이다.문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결할 수 있다. 단점 분할 정복 알고리즘은 최소한 두 개의 하위 문제를 생성하기..

메모이제이션(Menoization) 동일한 문제를 반복해야하는 경우, 한 번 계산된 결과를 저장해 두었다가 활용하는 방식이다.메모이제이션을 이용하면 중복 계산을 줄일 수 있다. 메모이제이션 방법으로는 TOP-DOWN 방식과 BOTTOM-UP 방식이 있다. TOP-DOWN 문제 해결이 위에서부터 아래로 진행되는 방식이다.int arr[] = new arr[t];int fibonaci(int n){ if(nfibonaci(10)을 호출하면 fibonaci(10)부터 작은 수를 호출하며 가장 작은 수까지 도달하게 된다.  BOTTOM-UP 문제 해결이 아래에서부터 위로 진행되는 방식이다.int fibonaci(int n){ arr[0] = 0; arr[1] = 1; for(int i=2; ifibo..

동적 계획법을 이해하려면 피보나치 수열부터 알아야한다.동적 계획법의 등장 배경은 피보나치 수열을 통해 알 수 있기 때문이다.  피보나치 수열(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 143 ....피보나치 수열은 제 2항까지 1을 반환, 제 3항부터는 바로 앞의 두 항을 더한 수로 정의된다.(제 0항은 생략할 수 있다.) 피보나치 수열은 재귀를 통해 표현할 수 있다. 재귀란  (자신)함수를 다시 호출하는 방식이다.int fibonaci(int n) { if(n  하지만 피보나치 수열은 중복이 생기게된다. 그렇기 때문에 동적계획법을 사용하게된다. 동적계획법 피보나치와 재귀를 통해 표현한다는 점에서 비슷하지만, 동적계획법에서는 처음 진행되는 연산은 기록해 두고, 이미 진행..