정신차려 하프물범 정신차려 하프물범

브루트 포스(brute force) 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다. 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다. 선형 구조(저장되는 자료의 전후관계가 1:1 )를 전체적으로 탐색하는 순차탐색, 비선형 구조(데이터 항목 사이의 관계가 1:n 또는 n:m (트리, 그래프)) 전체를 탐색하는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) *너비 우선 탐색은 브루트 포스와 관련이 깊고, 깊이 우선 탐색은 다음에 작성될 백트래킹과 관련이 깊음 문제해결 방법 주어진 문제를 선형 구조로 구조화한다. 구..

수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 알고리즘 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. 그림의 경우, 11^{2}>120이므로 1..

1. Dynamic Programming 이란? - 알고리즘을 디자인 하기 위한 전략 - 큰 문제를 작은 문제로 나누어 푸는 문제 (동적 프로그래밍이란 이름 때문에 동적으로 이루어지는지 찾아볼 필요 x, 그저 멋있는 이름을 붙였다는 원작자) 1.1 Divide and Conquer (분할 정복)과 비슷? : 작은 문제로 나누어 푼다는 점에서 비슷한 면이 있지만 결정적 차이점은 바로, 작은 문제가 중복을 일으키는지 아닌지 이다. 분할 정복은 단지 작은 문제로 나누어 푸는 것이기 때문에 작은 문제에 반복이 일어나지 않는 것이 특징이지만, 동적 프로그래밍은 작은 문제들이 반복되는 것(답이 바뀌지 않음) 을 이용해 풀어나가는 방법이다. 1.2 Dynamic Programming 방법 - 모든 작은 문제들은 한번..