반응형 알고리즘 문제풀이101 [알고리즘] 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. 이전 1 ··· 19 20 21 22 23 24 25 26 다음 반응형
