깡뇽

- 멱집합 : 주어진 집합의 모든 부분집합들 - 순환으로 생각하기 -> 하나의 원소를 제외한 집합의 모든 부분집합을 나열 + 그 모든 부분집합에 하나의 원소를 추가한 부분집합을 나열

: 가로 크기가 N , 세로 크기가 N인 2차원 체스 보드에서 N개의 말을 동일한 열, 행, 대각선에 두지 않도록 만드는 것 => Backtracking(내가 했던 결정을 번복하고 다른 선택) 방법 사용 가능 - 상태공간트리 : 찾는 해를 포함하는 트리. 즉, 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당하며 이 트리를 체계적으로 탐색한다면 해를 구할 수 있음을 의미함. 하지만 상태공간 트리의 모든 노드를 탐색해야 하는 것은 아님. 아래의 노드를 더 이상 탐색할 필요가 없음을 infeasible하다고 표현. - 되추적 기법(Backtracking) : 상태공간 트리를 깊이 우선 방식으로 탐색(깊이우선탐색)하여 해를 찾는 알고리즘 코드로 구현 할 때, recursion 또는 stack으로 ..

: 좌표가 위치하는 곳이 속한 Blob의 크기를 찾는 것 조건) Binary 이미지가 주어지고 각 픽셀은 background pixel이거나 혹은 image pixel이 됨. 서로 연결된 image pixel들의 집합을 blob이라고 부르며 상하좌우 및 대각방향으로도 연결된 것으로 간주함. 입력: N * N 크기의 2차원 그리드(grid)와 하나의 좌표 ( x, y ) 출력: 픽셀 ( x, y )가 포함된 Blob의 크기 그러나 ( x, y)가 어떤 Blob에도 속하지 않는 경우에는 0 => Recursive Thinking: 현재 픽셀이 속한 Blob의 크기를 카운트하려면 1) 현재 픽셀이 image color가 아니라면 0을 반환함. 2) 현재 픽셀이 image color라면 먼저 현재 픽셀을 카운트..

=> Recursive Thinking : 현재 위치에서 출구까지 가는 경로가 있으려면 1) 현재 위치가 출구이거나 혹은 2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나 - 미로 찾기 예시 Decision Problem(답이 yes 또는 no인 문제)으로 전환 Ex) 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 findPath ( x' , y' ) return true; return false; => 무한루프에 빠지..

- 순환적 알고리즘 설계 적어도 하나의 Base case가 있어야 함. 즉, 순환되지 않고 종료되는 case가 있어야 함. 모든 case는 결국 base case로 수렴해야 함. & 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꿔야 함. Ex) 순차 탐색 : 배열의 데이터들이 저장되어 있을 때 내가 원하는 데이터가 존재하는지 어디에 있는지 찾는 것 => 시작점을 암시적으로 표현할 수도 있고 시작점과 끝점을 모두 명시적으로 지정할 수도 있음 ① 맨 앞부터 검색, ② 맨 뒤부터 검색, ③ 중간 값을 검색 ( 이진 검색과 다름 ) Ex) 최대값 찾기 Ex) 이진 검색 : 데이터가 크기 순으로 정렬되어 있을 때 사용할 수 있는 검색 방법

수학함수 계산, 문자열의 길이 계산, 문자열의 프린트, 문자열을 뒤집어 프린트, 2진수로 변환하여 출력, 배열의 합 구하기, 데이터파일로 부터 n개의 정수 읽어오기 등이 가능 - 모든 순환함수는 반복문으로 변경 가능하며 반대로 모든 반복문은 순환함수로 표현 가능 - 복잡한 알고리즘을 단순하고 쉽게 표현하는 것을 가능하게 함 - 함수 호출에 따라 overhead가 있음

- 순환 (recursion) : 자기 자신을 호출하는 함수. 재귀함수. => 무한루프에 빠지는 경우가 있음. ① Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 함. ② Recursive case : recursion을 반복하다보면 결국 Base case로 수렴해야 함. 위 2가지 요구사항을 충족하면 무한루프에 빠지지 않음. 순환함수는 수학적귀납법으로 증명 가능함. Ex) Factorial : n! 을 순환함수로 만들어보자 public static int factorial ( int n ) { if ( n == 0 ) return 1 ; else return n * factorial ( n - 1 ) ; } => 수학적귀납법 증명 1. n = 0인 경우에 1을 반환하..