BOID

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

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

안녕하세요, HoonIOS입니다. 저번에는 기초 알고리즘과 시간 복잡도(추가사항)에 대해 알아봤는데요 (이곳을 클릭하시면 저번 포스팅 내용을 보실 수 있습니다.) 이번 시간에는 O표기법, 주먹구구 법칙에 대해서 알아보겠습니다. 점근적 시간 표기: O 표기 - 우선 O표기법의 정의 대해 알아보겠습니다. O표기법이란 주어진 함수에서 가장 빨리 증가하는 항만 남긴 채 나머지 값들은 다 버리는 표기법입니다. 즉 쉽게 말해 제일 높은 다항 차만 빼고 나머지 값을 버린다고 생각하시면 되겠습니다. - 알고리즘에서는 입력의 크기가 두개 이상의 변수로 표현될 때는 그중 가장 빨리 증가하는 항들만을 떼놓고 나머지를 버린다는 의미입니다. - 예를 들어 N² + N의 알고리즘 입력 크기가 나왔다면 여기서 O표기법으로는 N² ..

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

안녕하세요, HoonIOS입니다. 저번시간에는 기초적인 알고리즘 개념과 알고리즘 평가하는 기준에 대해 알아봤는데요 만약에 못보셨다면 여기 들어가서 한번 글읽어보시는걸 추천드려요~! 이번 챕터에는 시간복잡도 분석, 선형 시간 알고리즘, 선형 이하 알고리즘, 이진 탐색 알고리즘에 대해 알아보겠습니다. 알고리즘의 시간 복잡도 - 우선 제일 기본적인 개념으로는 말그대로 알고리즘의 프로그램에 의해 컴파일 되었을때 걸린 시간이라고 할수 있습니다. - 알고리즘의 시간복잡도인 알고리즘의 속도를 비교하기 위해 가장 직관적인 방법은 각각 프로그램으로 구현한뒤 같은 입력으로 두 프로그램의 수행 시간을 측정한는 방법이 있습니다. - 근데 위 방법으로 구한 프로그램 수행시간이 알고리즘의 속도의 기준이 되기에는 매우 부적합하다...

안녕하세요, HoonIOS입니다. 개인적인 공부를 하다가 드디어 첫 포스팅을 하게 되었는데요, 저의 발전을 위해서 꾸준히 업로드하겠습니다 :) 우선 시간복잡도을 알아보기에 앞서 알고리즘에 대해 알아봐야겠죠! 알고리즘이란? - 어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 방법을 말합니다. 즉 한 개의 작업에 대한 알고리즘의 경우의 수는 매우 많을 거 같네요 - 단!!!!!!!!!!!!!!!!!!!!! 알고리즘이란 한가지 방법을 명료하게 써놓아야 하지 주관적이고 애매 모호하게 써놓은 것은 알고리즘이라고 할 수 없습니다. (예를 들어, 어느 목적지를 가기위해 a라는 버스를 타고 b라는 지하철을 타서 c라는 목적지에 도착한다라는 정확한 방법이 쓰여있어야 한다는 뜻입니다.) - 가능한한 명료하고 정확한 ..