반응형 알고리즘 문제풀이101 [알고리즘] 재귀함수 - 이항계수(중복조합) 재귀함수 - 이항계수(중복조합) A,B,C,D 4개의 공 중에 2개의 공을 뽑을 때 뽑을 수 있는 가지 수는 모두 몇가지일까다음과 같은 경우의 수를 계산할때 이항계수가 사용된다. 이항계수로 경우의 수를 구하는 공식은 고등학교 과정에서 배울 수 있다.재귀에서 이항계수를 이용하려면 다음과 같은 이항계수의 성질을 사용한다. 왜 이와 같은 성질이 나올수 있을까.기본 nCr 식은 다음과 같이 나눌수있다. 1. 1을 포함하는 경우 : 2,3,4 중에 2개를 선택하는 경우의수(3C2)2. 1을 포함하지 않는 경우 : 2,3,4중에 3개를 선택하는 경우의 수(3C3) 이렇게 나누어진 식이 재귀로 계산된다. 1. 중복조합을 재귀함수로 123456789101112131415161718192021222324#include .. 2017. 4. 18. [알고리즘] 재귀 - 팩토리얼 재귀 - 팩토리얼 재귀함수, 제대로 이해하려면 제일 어렵다고 생각한다.사실 과제나 개발만하다가 알고리즘을 시작한지 얼마안되서 나도 헷갈리는 부분이 많다.그러나 심화된 문제일수록 재귀함수의 적절한 쓰임이 중요하며자칫 잘못해서 재귀함수를 사용 할 경우 일반적인 함수를 사용할 때 보다연산의 시간이 더 길어 지거나 스택 오버플로우가 발생하므로 정확한 이해가 동반되어야한다.그럼 기초적인 예제를 통하여 재귀함수를 이해해 보도록하자. 팩토리얼, 피보나치, 하노이탑..이 3개의 문제는 재귀함수를 설명하는 대표적인 예제라고 할 수 있다.그 중 팩토리얼을 먼저 풀어보도록 하겠다. 팩토리얼은 N!으로 표기되며 1부터 N까지의 수를 모두 곱하는 연산이다.예를 들어 4!는 1X2X3X4 를 나타내며, 팩토리얼은 고등학교 때 배.. 2017. 4. 18. [알고리즘] 환형 큐(Circulation Queue) 환형 큐(Circulation Queue) 앞서 나왔던 큐의 포스팅이 너무 길어진 듯 해서 환형 큐는 따로 만들어 보았다. 환형 큐의 등장 배경은 다음과 같다.큐의 head가 변함에 따라 기존에 사용하던 head index를 쓰지 못하는 문제가 발생한다.쉽게 말해, Dequeue를 해버리면 그자리는 다시 못쓰는 것이다.이러한 문제점을 해결하기 위하여 환형 큐를 사용하게 되었다. 파워포인트로 그렸습니다ㅠ 이해가 잘되는 그림일지 모르겠지만 환형 큐의 구조는 다음과 같다.head와 tail이 이동하여도 원형으로 순환(Circulation)하며 같은 공간을 사용 할 수있으므로기존의 큐보다는 효율적이라고 할 수 있다. 1. 환형 큐 123456789101112131415161718192021222324252627.. 2017. 4. 18. [알고리즘] 큐(Queue)를 이용한 대기번호 큐(Queue)를 이용한 대기번호 자료구조를 배우면 가장 먼저 등장하는 스택, 큐, 링크드리스트.이 중 큐를 이용하여 대기번호 알고리즘을 작성해보겠다. 큐는 선입선출(First In First Out, FIFO)의 구조를 가지고 있으며OS에도 호출과 관련하여 스택과 같이 빈번하게 사용된다. 은행에서 대기번호를 받을 때 먼저 대기표를 받고 자신의 차례를 기다린다.이후 순서가 돌아오면 번호표대로 업무를 보기 시작한다.이와같은 구조는 선입선출의 큐 구조와 동일한 모습을 보인다.따라서 대기번호의 경우 큐로 구현이 가능하다. 1. 배열로 만든 큐(Add-Enqueue) 12345678910111213int add(int num){ if(tail==Q_Capacity){ printf("Queue is Full!").. 2017. 4. 18. 이전 1 ··· 21 22 23 24 25 26 다음 반응형
