404 not found

7. 멱집합(Powerset) 멱집합 임의의 집합의 모든 부분집합 ​ {a,b,c,d,e,f} 의 모든 부분집합을 나열하려면 a를 제외한 {b,c,d,e,f} 의 모든 부분집합들을 나열하고 , {b,c,d,e,f} 의 모든 부분집합에 {a}를 추가한 집합들을 나열한다. ​ 집합 S : k번째부터 마지막 원소까지 연석된 원소들 : data[k], ..., data[n-1] 집합P : 처음부터 k-1번째 원소들 중 일부 : include[i] = true (i = 0, ..., k-1) private static char data[] = {'a','b','c','d','e','f'}; private static int n = data.length; private static boolean [] include..

5. 순환(Recursion)의 응용: Counting Cell in a Blob Binary 이미지 각 픽셀은 background pixel이거나 혹은 image pixel 서로 연결된 image pixel들의 집합을 blob이라고 부름 상하죄우 및 대각방향으로도 연결된 것으로 간주 ​ ex) 4개의 Blob이 존재 (x,y)가 포함된 blob의 크기를 구하는 예제 ​ 현재 픽셀이 속해있는 blob의 크기를 세려면, ​ 현재 픽셀이 image color가 아니라면, 0을 반환한다. 현재 픽셀이 image color라면 먼저 현재 픽셀을 카운트하다. 현재 픽셀이 중복카운트되는 것을 방지하기위해 다른 색으로 칠한다. 현재 픽셀에 이웃한 모든 픽셀들에 대해서 그 픽셀이 속한blob의 크기를 카운트하여 카운터..

4. 순환(Recursion)의 응용: 미로찾기 미로찾기 현재 위치에서 출구까지 가는 경로가 있으려면 1. 현재 위치가 출구이이거나, 2. 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있있어야 한다. ​ Decision Problem(답이 Yes or No인 문제) x,y로 부터 출구까지 가는 경로가 있으면 true, 없으면 false ​ 예제) boolean findPath(x,y){ if (x,y) is the exit return true; else for each neighbouring cell(x',y') of (x,y) do //이웃 셀들 //if (x',y') is on the pathway //이웃된 두 셀을 왔다갔다하는 무한루프가 가능 if (x',y') is ..

2. 순환(Recursion)의 개념과 기본 예제2 Recursive Thinking: 순환적으로 사고하기 반복문을 사용하여 짤 수 있는 프로그램을 재귀함수를 이용하여 작성할 수 있다. ​ 예제) 문자열의 길이 계산 :라이브러리 함수 사용 가능 > 라이브러리 함수는 어떻게 문자열의 길이를 계산할까? public static int length(string str) { if (str.equals("")) return 0; else return 1 + length(str.substring(1)) } 2진수로 변환하여 출력 public void printBinary (int n){ if(n

1. 순환(Recursion)의 개념과 기본 예제1 Recursion = 순환 = 재귀함수 > 스스로를 호출하는 함수 무한 루프에 빠지지 않는 조건 1. Base Case: 적어도 1개의 순환이 존재하지 않는 경우 존재한다. 2. Recursive Case: 순환을 반복하다보면 Base Case로 수렴한다. 순환 알고리즘 예제) 최대공약수: Euclid Method m≥n 인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,n) = n이고, 그렇지 않으면 gcd(m,n) = gcd(n,m%n)이다. public static double gcd(int m, int n) { if (m < n) { int tmp = m; m = n; n = tmp; } if (m % n == 0) retrun ..