BOID

안녕하세요 HoonIOS입니다. :) 이번에는 어제 공부한 동적 계획법에 대해 알아보겠습니다. 동적 계획법이란? - 동적 계획법은 큰 의미에서 분할정복과 같은 접근 방식을 의미합니다. - 동적 계획법과 분할정복의 차이가 발생하는 부분은 문제를 나누는 방식입니다. - 예를 들어 cde는 abcde를 해결할때와 cdefg를 해결할때 한 번씩 계산하고 그러면 c, d, e는 각각 세번씩 중복 실행이 됩니다. - 이렇게 계산의 종복횟수는 분할의 깊이가 깊어질수록 더 증가하게 됩니다. 이런 문제를 해결하기 위해서 고안된 알고리즘은 동적계획법 입니다. * 여기서 분할정복이란? - 주어진 경우를 작은 사례로 나뉘고 해답을 구할수 있을 만큼 충분히 더 작은 사례로 나누어 해결하는 방법입니다. - 대표적인 예시로 이진 ..

안녕하세요 HoonIOS입니다 :) 이번에는 저번 시간에 이어서 P문제와 NP 문제, NP-난해 문제에 대해 알아보겠습니다. P문제란? 우리가 정의하는 문제의 어려움은 우리가 문제를 풀 때의 난이도가 아니라 계산 복잡도 이론에서 문제의 난이도는 해당 문제를 해결하는 빠른 알고리즘이 있느냐를 나타내는 것입니다. 여기서 빠른 알고리즘이 있는 문제는 계산적으로 쉽고, 빠른 알고리즘이 없는 문제는 계산적으로 어렵다고 합니다. 이 말은 즉 알고리즘을 유도하는 과정이 책이 열 권이고 그 구현이 아무리 길어도 수행 시간만 빠르다면 이건 쉬운 문제가 된다는 것을 알 수 있습니다. 그럼 여기서 빠른 알고리즘의 기준이 뭐라고 할 수 있을까요?, 그 기준은 우리는 다항시간 알고리즘이나 그보다 빠른 알고리즘만을 빠르다고 할수..

안녕하세요, HoonIOS입니다. 저번에는 알고리즘의 시간 복잡도, 선형 시간 알고리즘, 선형 시간 이하 알고리즘, 이진 탐색인 기초 알고리즘을 알아봤는데요. 이곳을 클릭 하시면 저번에 포스팅했던걸 보실 수 있을 겁니다. 이번에는 저번 기초 알고리즘에 이은 다항 시간 알고리즘, 지수 시간 알고리즘, 소인수 분해의 수행 시간, 그다음 시간 복잡도에 좀 더 알아보도록 하겠습니다. 다항 시간 알고리즘이란? - 다항 시간 알고리즘이란 반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘이다. 예를 들어) n², n...을 말한다. - 다항 시간은 하나의 분류에 포함되는 알고리즘 간에도 큰 시간 차이가 날 수 있는데 이것은 loop안에도 코드에 따라 큰 시간 차이가 날 수도 있습니다, 그만큼 같은..