프로그래밍 (100) 썸네일형 리스트형 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) 표기법을 사용한다. - 점.. Properties와 Collections에 대해 보호되어 있는 글입니다. HashMap과 TreeMap에 대해 Map- 순서가 없고 키는 중복을 허용하지 않으나, 값은 중복을 허용한다.- 데이터를 키와 값의 쌍으로 저장한다.- Map을 구현한 컬렉션 클래스 : Hashtable, HashMap, LinkedHashMap, TreeMap HashMap- Map인터페이스를 구현한 대표적인 컬렉션 클래스- HashMap(동기화되어있지 않음)은 Hashtable(동기화되어있음)의 신버전이다.- 저장 순서를 유지하고 싶으면 LinkedHashMap 클래스를 사용하면 된다.- 해싱(hashing)기법을 이용해 데이터를 저장하여 데이터가 많아도 검색이 빠르다는 장점이 있다.- 같은 키로 값을 저장하게 되면 나중에 저장된 값이 이전 값을 덮어씌운다.- HashMap은 HashMap클래스의 내부 클래스인 Entry의 배열에 저장.. Arrays, Comparable, Comparator에 대해 Arrays- 배열을 다루기에 편리한 메소드들(static)을 제공한다. Arrays 클래스의 메소드- toString()배열을 출력한다. boolean[], byte[], char[] 등 여러 자료형들에 대한 출력을 폭넓게 지원한다.- deepToString(), equals(), deepEquals()다차원 배열에서 비교와 출력을 할 때 쓰인다. deepToString과 deepEquals는 다차원배열에서 각각 출력과 비교를 담당하며 equals는 1차원 배열에서의 비교를 수행한다.- copyOf(), copyOfRange()배열을 복사할 때 쓰인다. copyOf는 처음부터 지정된 곳까지 저장을 하며 copyOfRange는 지정된 곳부터 지정된 곳까지 저장을 한다. 만일 기존 배열의 크기를 넘어서는 .. 이전 1 ··· 8 9 10 11 12 13 다음
