본문 바로가기
반응형

분류 전체보기340

[알고리즘] 파일 입출력 파일 입출력 알고리즘을 하는데 있어서 가장 기본이 되는 요소는 파일 입출력이다. 이는, 주어진 문제의 테스트케이스를 받고 결과를 출력하기 위해서는 당연하게 사용되는 기능이라고 할수 있다. 가장 기본이 되는 파일 입출력을 살펴보도록 하자 (기준은 C++로 설명) 1. 기본 12345678910#includeusing namespace std; int main() { char str; cin >> str; cout num){ // 입력 도중 수행해야할 // 알고리즘이 있다면 // 여기 작성 } }Colored by Color Scriptercs 입력이 주어지지 않은경우는 EOF(End Of File)까지 입력을 받으면 된다.말그대로 파일의 끝까지 입력을 받으면 되는 것인데, 이는 입력 함수의 반환값을 통해 .. 2017. 4. 18.
[알고리즘] 동적프로그래밍 - 길찾기 동적 프로그래밍(Dynamic Programming) 동적프로그래밍, 동적 계획법이라고도 표현한다.동적 프로그래밍은 재귀의 중복으로 계산시간이 오래걸릴 때 메모이제이션을 대체 할 다른 방법이다.동적 프로그래밍을 잘 사용하면 재귀보다 크게 성능을 향상 시킬 수 있다.따라서 소프트웨어 직군의 알고리즘 시험에 종종 출제되니 꼭 짚고 넘어가도록 하자 1. 재귀로 구현한 길찾기 동적프로그래밍의 대표적인 문제는 길찾기이다.고등학교때 한번씩 다 풀어본 문제일 것이다.위와같은 경로가 있을때 A에서 B까지 도달할 수 있는 최단 경로는 얼마일까? 답은 다음과 같다.A에서 부터 시작하여 (i,0), (0,j)를 1이라고 하면다음 경로는 아래위의 합과 같다.이와같이 더해나가면 끝에서 최단 경로를 구할 수 있다. 이를 점화식으.. 2017. 4. 18.
[알고리즘] 재귀함수 - 피보나치 수열 재귀함수 - 피보나치 수열 피보나치 수열은 다음과 같다.1,1,2,3,5,8,13,21,34,55,89,144,233,377...즉, n+2항은 바로 뒤 2개의 항의 합으로 결정되는 구조이다. 1. 재귀함수 피보나치 수열 12345678910111213141516171819202122#include int main() { int num, result; scanf_s("%d", &num); result = fibo(num); printf("%d", result); return 0;} int fibo(int num) { if ((num == 1)||(num==2)) { return 1; } return fibo(num - 1) + fibo(num - 2); } Colored by Color Scripterc.. 2017. 4. 18.
[알고리즘] 재귀함수 - 이항계수(중복조합) 재귀함수 - 이항계수(중복조합) 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.
반응형

티스토리툴바