프로그래밍/알고리즘 (45) 썸네일형 리스트형 Recursion 응용(1) 미로찾기 순환적인 방식으로 생각해보기- 현재 위치에서 출구까지 가는 경로가 있기 위해서는 밑의 두 가지 조건 중 하나가 만족해야 한다.1) 현재 위치가 출구여야 한다.2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있어야 한다.- 순환 형식을 이용하여 프로그래밍할 경우에는 무한루프에 빠질 수 있는 경우를 주의해야 한다. - 슈도 코드boolean findPath (x, y)if (x, y) is the exitreturn true;elsefor each neighboring cell (x', y') of (x, y) doif (x', y') is on the pathwayif findPath(x', y')return true;return false;-> 이 경우 무한루프에 빠.. 순환(Recursion)에 대해(3) 순환 알고리즘의 설계 (Designing Recursion) 순환 알고리즘의 성립 조건- 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 꼭 있어야 한다. (base case는 여러 개가 있을 수 있다.)- 모든 케이스는 결국 base case로 수렴해야 한다.- 암시적 (implicit)매개변수를 명시적 (explicit)매개변수로 바꾸어라. - 순차 탐색 (데이터가 정렬되어 있다면 이진검색이 더 효율적이다.)//이 함수의 임무는 data배열 내에서 target을 검색해내는 것이다.//하지만, 보통 검색 구간의 시작점인 인덱스 0은 보통 생략하는데 이를 암시적 매개변수라고 말한다.int search (int[] data, int n, int target) {for (int i =.. 순환(Recursion)에 대해(2) 순환적으로 사고하기 (Recursive Thinking)- 순환은 수학 함수 계산뿐 아니라 다른 많은 문제들을 해결할 때 도움을 줄 수 있는 사고 방식이다. 문자열의 길이 계산- 슈도 코드if the string is emptyreturn 0;elsereturn 1 plus the length of the string that excludes the first character;//원래 문자열에서 첫 번째 문자를 뺀 길이를 계산하여 거기에 1을 더한다. - 구현public static int length (String str) {if (str.equals(""))return 0;elsereturn 1 + length(str.substring(1));//substring(1)은 원래 있던 문자열에서 제일 .. 순환(Recursion)에 대해(1) 순환- 자기 자신을 다시 호출하는 함수를 말한다.void func(~) {~func(~);~}ex)public class Ex1 {public static void main (String[] args) {func();}public static void func() {System.out.println("Hello!");func();}}-> 자신을 계속 반복하여 호출하게 되면 무한정 자신을 호출하는 무한 반복에 빠지게 된다. - 순환은 코드의 작성법에 따라 무한루프에 빠지지 않게 만들 수 있다.1) Base case : 무한반복에 빠지지 않게 하는 조건식이 적어도 하나는 존재해야 한다.2) Recursive case : 순환을 계속 하다보면 결국 base case에 수렴할 수 있도록 해야 한다. ex)pub.. 시간복잡도에 대해 시간복잡도(time complexity) - 알고리즘의 자원(resource) 사용량을 분석한다. - 자원이란 실행 시간, 메모리, 저장 장치, 통신 등을 의미한다. - 실행시간은 실행 환경에 따라 달라진다.(하드웨어, 운영체제, 언어, 컴파일러 등) - 실행 시간을 측정하는 대신에 연산의 실행 횟수를 센다. - 데이터의 크기가 같아도 실제 데이터에 따라 시간 복잡도는 달라질 수 있다. 최악 시간 복잡도(worst-case analysis) 평균 시간복잡도(average-case analysis) 점근적 분석 - 점근적 표기법을 사용한다. 데이터 개수가 n -> ∞일 때 수행시간이 증가하는 growth rate로 시간복잡도를 표현하는 기법이다. 주로 세타(Θ) 표기, 빅오(O) 표기법을 사용한다. - 점.. 이전 1 ··· 3 4 5 6 다음
