ellie의 일지

부경대학교 권오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘 강좌' Recursion vs. Iteration 모든 순환 함수는 반복문(iterator)으로 변경 가능 모든 반복문은 순환 함수로 변경 가능 순환함수는 복잡한 알고리즘을 단순하게 표현하는 것이 가능하지만, 함수 호출에 따른 오버해드가 있다. (매개변수 전달, 액티베이션 프레임 생성 등) 순환적 알고리즘 설계 암시적 매개변수(시작 지점을 암시적으로 0부터라고 하는 것)에서 명시적 매개변수(시작과 끝을 정확히 나타내는 것)로 바꾸어라 이진 탐색: Iterator(반복문 버전) public int binarySearch(int data[], int n, int target) { int begin = 0, end = n - 1; // 시작과 끝 ..

부경대학교 권오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘' Recursion의 적용 문자열의 길이 계산 문자열이 비어있으면 문자열의 길이는 0, 그렇지 않으면 1+(문자열의 첫 번째 문자를 제외한 문자열의 길이)이다. public static int length(String str) { if(str.equals("")) return 0; else return 1+length(str.substring(1)); // 1+(문자열의 첫 번째 문자 제외한 문자열의 길이) } 순차 탐색 data[0]에서 data[n-1] 사이에서 target을 검색한다. target이 존재하면 배열의 인덱스를 반환하고, 존재하지 않으면 -1을 반환한다. public int search(int data[], int n, in..

부경대학교 권오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘' 순환(Recursion)이란? 자기 자신을 호출하는 함수 void funtion(){ ... function(); } Recursion이 무한루프에 빠지지 않으려면? Base case와 Recursive case가 필요 Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. Recursive case : recursion을 반복하다보면 결국 Base case에 수렴해야 한다. public int func(int n) { if(n==0) // Base case n==0일 경우 return 0; // 0을 반환 else return n+func(n-1); // Recursive case } Factorial:..