깡뇽

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

: 가로 크기가 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을 반환하..

- 시간복잡도 : 실행시간은 하드웨어, 운영체제 등과 같은 실행환경에 따라 달리질 수 있기 때문에 실행 시간을 측정하는 대신 연산의 실행 횟수를 측정함. 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 가능. - 점근적 분석 : 데이터의 개수 n→∞일때 수행시간이 증가하는 growth rate로 시간복잡도를 표현 하는 기법. 상대적으로 가장 간단하며 알고리즘의 실행환경에 비의존적이기 때문에 광범위하게 사용될 뿐임. - 이진검색 : 정렬된 데이터의 중간값을 비교해 나가는 방식이기 때문에 한 번 비교할 때마다 남아있는 데이터가 절반으로 줄어듬. 즉, 시간복잡도는 O(log2n)임. => 순차검색의 시간복잡도는 O(n)이고 이진검색은 O(log2n)이며 둘의 차이는 매우 큼. ① 버블 정렬 ② 삽입..

- 클래스 Ex) Example d ; d = new Example ( ) ; class Example ( ) { System.out.println ( "hi" ) ; } -> 실행하면 hi public void left ( ) { System.out.println ( "좌회전" ) ; } public void right ( ) { System.out.println ( "우회전" ) ; } Car myCar ; myCar = new Car ( ) ; myCar.left ( ) ; -> 실행하면 좌회전 Car yourCar ; yourCar = new Car ( ) ; yourCar.left ( ) ; -> 실행하면 우회전 - 생성자 함수 : 클래스로 객체를 만들 때 1번만 최초로 생성되는 함수 ( 무조건..

- 함수 : public static 자료형 함수명 ( 매개변수 ) { 기능 } Ex) public static int sample ( int x ) { int result = 2 * x - 1 ; return result ; } System.out.println ( sample ( 2 ) ) ; -> 실행하면 3 => public static : 접근제어자 int : return 되는 자료형. int 대신 void로 변경하면 return이 없을 때 함수 사용 가능. sample : Ex에서의 함수명 return : Ex에서는 없으면 오류 발생 Ex) public static void hi ( ) { System.out.println ( " hello " ) ; } hi ( ) ; -> 실행하면 hell..

- 배열 ① 방법1 : 배열의 크기를 정하고 값을 따로 넣는 방법 Ex) int [ ] arr1 = new int [ 5 ] ; arr1 [ 0 ] = 10; arr1 [ 1 ] = 20; arr1 [ 2 ] = 30; arr1 [ 3 ] = 40; arr1 [ 4 ] = 50; arr1 [ 5 ] = 60; System.out.println ( arr1 [ 2 ] ) ; -> 출력하면 30 => 위의 예시에서 int는 배열 안에 들어갈 자료형을 표시함. arr1은 배열의 이름. [ 5 ]는 배열 내 자료의 개수를 의미함. ② 방법2 : 배열에 값을 바로 넣는 방법 Ex) int [ ] arr2 = { 100, 200, 300, 400, 500 }; System.out.println ( arr2 [ 0 ..

- 반복문 ① for 문 for ( 변수 초기화 ; 조건 ; 증가or감소 ) { 반복할 코드 } ② while 문 while ( 조건 ) { 반복할 코드 } ③ do while 문 do { 반복할 코드 } while ( 조건 ); => 조건이 틀려도 반복할 코드가 1회 실행됨. Ex) 구구단 만들기 for ( int i = 2 ; i < 10 ; i ++ ) { for ( int j = 1 ; j < 10 ; j ++ ) { System.out.println ( i + " * " + j + " = " + j * i ) } }