본문 바로가기
반응형

전체 글340

[알고리즘] Recursion의 응용 - 미로찾기 Recursion의 응용 - 미로찾기 미로찾기 문제에 대해서 생각해보도록 하자 그리드의 크기를 NxN이라고 가정한다면[0,0]이 입구, [n-1,n-1]이 출구가 된다.여기서 흰색으로 표시된것이 통로, 파란색은 벽 임을 가정 했을 때,탈출 할 수있는 경로를 찾는것이 과제이다. 위의 문제를 풀수 있는 방법은 많지만 가장 간명하게 풀수있는 것이 재귀이다.이 문제를 재귀적으로 푼다면 다음과같은 재귀적 사고가 필요하다. 현재 서있는 위치에서 출구까지 가려는 경로가 있으려면1) 내가 있는 위치가 출구일 때(이미 내가 출구에 도달해 있을 때)2) 이웃한 셀들중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있을 때위의 둘중 하나를 만족해야한다. 123456789101112boolean findPath(x,.. 2017. 4. 18.
[알고리즘] Recursion 이란 - 3 Recursion(재귀) 이란 - 3 암시적 매개 변수의 명시적 표현 앞에서 배운 Recursion의 내용을 다시 한번 종합해보자면 다음과 같다. 1. 적어도 하나의 base case를 가지고 있어야한다, 즉 순환되지 않고 종료되는 case가 있어야한다.2. 모든 case는 base case로 수렴해야한다. 여기서 추가적으로 코드를 작성하는 방법으로는,'암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라!' 이다.예제를 살펴보자 순차탐색 12345678int search(int [] data, int n, int target){ for(int i=0; iend) return -1; else if(target == data[begin]) return begin; else ret.. 2017. 4. 18.
[알고리즘] Recursion 이란 - 2 Recursion(재귀) 이란 앞서 우리는 피보나치나, 최대공약수등의 수학적 계산에 대한 예제를 살펴보았다.그렇다면 Recursion은 수학적 계산에만 유용한 것일까그렇지 않다. 우리는 일반적으로 for나 while등의 반복문을 이용하여 문제를 푸는데,이는 모두 재귀함수로 풀어낼수 있다.예제를 살펴보자 문자열의 길이 찾기 12345if this string is empty return 0;else return 1 plus the length of the string that excludes the first characterColored by Color Scriptercs 슈도(의사) 코드로 작성한 문자열의 길이 찾기이다.문자의 길이가 0이라면 0을 리턴하고길이가 0이 아니라면 하나의 문자열을 제외한 문.. 2017. 4. 18.
[알고리즘] Recursion 이란 - 1 Recursion(재귀) 이란 12345void func(...){ ... func(...); ...}cs 위의 코드와 같이 자기자신을 호출하는 함수를 Recursion,재귀 함수라고 한다. 1234567891011public class recur{ public static void main(String [] args){ func(); } public static void func(){ System.out.println("Hello world!"); func(); }} Colored by Color Scriptercs 위와 같은 자바 코드를 보자.이 함수를 우리가 main 메소드에서 호출하게되면 불행하게도무한 루프에 빠져서 영원히 Hello world!를 호출하게 된다.이렇게 재귀 함수는 항상 무한 루프.. 2017. 4. 18.
[알고리즘] string 형 변환 string 형 변환 sring으로, 또는 string을 형변환 하기 위해서는 일련의 메소드를 사용하면 쉽게 변환이 가능하다 1. string to X 1234567891011121314151617181920#include#include using namespace std; int main() { string str; float a; int b; long c; long long d; cin >> str; a = atof(str.c_str()); b = atoi(str.c_str()); c = atol(str.c_str()); d = atoll(str.c_str()); }Colored by Color Scriptercs 변환을 위하여 atox를 사용한다. 여기서 x는 자료형의 앞머리 글자 이다.atox의 .. 2017. 4. 18.
[알고리즘] 파일 입출력 파일 입출력 알고리즘을 하는데 있어서 가장 기본이 되는 요소는 파일 입출력이다. 이는, 주어진 문제의 테스트케이스를 받고 결과를 출력하기 위해서는 당연하게 사용되는 기능이라고 할수 있다. 가장 기본이 되는 파일 입출력을 살펴보도록 하자 (기준은 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.
반응형

티스토리툴바