404 not found

8. 기본적인 정렬 알고리즘 Bubble sort, Insertion sort, Selection sort : simple, slow Selection Sort (선택정렬) 1. 가장 큰 값을 찾는다. 2. 가장 큰 값을 가장 끝에 있는 값과 위치를 바꾼다. 3. 위치가 바뀐 가장 끝 값을 제외한 그 앞 부분에서 1,2번을 반복한다. 실행시간: 1) n-1번 반복 2) 가장 큰 수를 찾기 위한 비교 횟수: n-1, n-2, n-3,...,2,1 3) 위치 교환은 상수시간 작업 T(n) = O(n²) =n(n-1)/2 ⇒ 최악, 최선, 평균이 항상 같다. Bubble Sort 1. 자기자신을 다음 값과 비교하여 자신이 더 크면 다음 값과 교환한다. 2. 가장큰 값이 마지막으로 가게 되면 마지막 값을 제외하..

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의 크기를 카운트하여 카운터..

3. 순환(Recursion)의 개념과 기본 예제3 Designing Recursive: 순환 알고리즘의 설계 ​ 1. 적어도 하나의base case가 있어야한다.(여러개의 base case가 있을 수 있다.) 2. 모든 case는 결국 base case로 수렴해야한다. 3. 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라. ​ 예제 순차탐색 // 이 함수의 미션은 data[0]에서 data[n-1] 사이에서 target을 검색하는 것이다. //하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉 암시적 매개변수이다. int search(int [] data, int n, int target) { for (int i = 0; i end) return -1; else i..

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 ..