728x90 넓고 얕은 자료구조 & 알고리즘35 시간복잡도(Time Complexity) 1분 요약 정리 코드를 짤 때 시간 복잡도를 고려한다는 것은 연산 횟수에 비해 시간이 얼마나 걸리는가를 계산하여 가장 효율적인 알고리즘을 만드는 것을 말한다. 항상 입력값으로 0 이상의 수를 입력받는다. 음의 입력값은 시간복잡도를 고려할 때 말이 되지 않는다. 따라서 시간복잡도는 항상 0보다 크다고 가정한다. 함수는 더 많은 입력값이 있을 때 더 많은 작업을 필요로 한다. 시간 복잡도에서는 모든 상수를 삭제한다. ex) 3n, 5n, 50n 복잡도란 존재하지 않는다. 오로지 n만이 존재한다. 알고리즘에서 1보다 작은 지점은 고려하지 않는다. n이 아주 클 때의 경우를 고려한다. 다양한 차수 항을 가지고 있는 함수가 있을 때 낮은 차수의 항과 상수는 고려하지 않는다. 오직 제일 큰 차수의 항만이 알고리즘의 시간 복잡도에 .. 2023. 2. 6. 우선순위 큐(Priority Queue) // 낮은 숫자를 우선으로 하여 꺼내 처리하는 int 형 우선순위 큐 PriorityQueue pq = new PriorityQueue(); // 높은 숫자를 우선으로 하여 꺼내 처리하는 int 형 우선순위 큐 PriorityQueue pq = new PriorityQueue(Collections.reverseOrder()); 2022. 11. 6. 정규표현식을 이용한 문자열에서 숫자 분리 String str1 = str1.replaceAll("[^0-9]", ""); // 문자열에서 숫자를 제외한 모든 값(공백 포함 )을 지움 String str2 = str2.replaceAll("[0-9]", ""); // 문자열에서 숫자를 지움 String str3 = str3.replaceAll("[0-9a-zA-Z]", ""); // 문자열에서 숫자, 대문자, 소문자를 모두 지움(공백이 없다는 가정 하에 특수문자만 남음) 2022. 10. 20. 바빌로니아 법(The Babylonian Method) 바빌로니아 법(The Babylonian Method) 임의의 수의 제곱근에 빠르게 수렴하는 수열을 만들어 근사값을 구하는 방법 => 제곱근을 구하는 점화식을 코드로 구현 static double sqrt(int num) { int PRECISION_COUNT = 10; // 임의의 자연수로 이 값이 클수록 더 정확한 근사값을 구할 수 있다. double x = num / 2.0; for (int i = 0; i < PRECISION_COUNT; i++){ x = (x + (num / x)) / 2; // xn+1 = (xn + (num / xn)) / 2 } return x; } 2022. 10. 20. Integer로 표현할 수 있는 최대값과 최소값 int min = Integer.MIN_VALUE; // -2147483648 int max = Integer.MAX_VALUE; // 2147483647 2022. 10. 20. StringBuilder StringBuilder 일반적으로 String 객체를 더하는 것은(ex. str1 + str2) 메모리 할당과 해제를 발생시켜 연산이 많아질수록 성능이 떨어지게 된다. StringBuilder의 경우 문자열을 더할 때 새로운 객체를 생성하지 않고 기존의 데이터에 더하는 방식으로 작동한다. 따라서 문자열을 더하는 상황이 발생할 경우 StringBuilder를 사용하는 것이 속도도 빠르고 상대적으로 부하도 적다. StringBuilder sb = new StringBuilder(); sb.append("a").append(" ").append("b"); System.out.println(sb); // a b 2022. 10. 3. StringTokenizer StringTokenizer 문자열을 구분자를 이용해 쪼갤 때 사용한다. StringTokenizer st = new StringTokenizer(str); // 기본 구분자(공백 등)이 자동 적용되어 문자열을 쪼갬 StringTokenizer st = new StringTokenizer(str, " "); // 공백을 기준으로 문자열을 쪼갬 st.nextToken() // st에서 쪼갠 문자열을 하나씩 불러온다. 2022. 10. 3. Collections.singleton() Collections.singleton() 단 하나의 객체만 저장 가능한 컬렉션을 생성한다. Integer[] intArr = {1, 2, 3} // 객체 Collections.singleton(arr); 2022. 9. 29. 이전 1 2 3 4 5 다음 728x90
