개발소설

두 수를 입력받아 거듭제곱을 리턴 시간복잡도 O(logN) 실제 계산 결과를 94,906,249로 나눈 나머지를 리턴 (long 타입의 표현 범위를 넘어 설수 있으므로) o(log n)은 업다운 게임과 비슷하다. - 값을 계속 반으로 나누어 답을 찾는다. 아래와 같이 구할 수 있다. n^10 = n^5 * n^5 n^5 = n^2 * n^2 * n n^2 = n*n n = n * 1 public long power(int base, int exponent) { // 탈출조건(더이상 나눌수 없는 경우) if(exponent == 0) return 1; // 절반 나누기 n^10 = n^5 * n^5 long result = power(base, exponent / 2); // 홀수라면 n^2 * n^2 *..

최대 공약수 최대 공약수란 두 수 (n과 r)의 약수들 중 공통된 약수의 최대 값 4와 8의 최대 공약수는 4의 약수 1 2 4 8의 약수 1 2 4 8 공통된 숫자중 4가 제일 크기 떄문에 4이다. 유클리드 호제법을 재귀함수로 최대 공약수를 간단하게 구할 수 있다. main{ int gcdNum = gcd(4, 8); print(gcdNum); // 4 } // 유클리드 호제법 int gcd(int n, int m) { if (m == 0) return n; return gcd(m, n % m); }

순열(permutation) 요소 n개 중에 r개를 선택하여 순서에 상관 있게 뽑는 경우의 수 순서에 상관이 있다는것은 알파벳 3개를 뽑을때 [ A, B, C ]와 [B, A, C] 는 다르다 뽑은 요소가 같아도 순서가 다르면 다른것 요소가 중복되면 안된다. nPr = n! / (n - r)! 5장에서 3장을 뽑는다면 5P3 5 * 4 * 3 * 2 * 1 / 2 * 1 120 / 2 = 60 자바 순열 템플릿 (Template) //뽑을 요소들이 담긴 리스트 n //뽑을 갯수 r //결과를 담을 리스트 ArrayList result = new ArrayList(); boolean[] visited = new boolean[n.size()]; // 요소 사용 여부 체크용 return permtation(..

탐욕(Greedy) 사전적으로 '탐욕스러운, 욕심 많은' 이라는 뜻으로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒는것 지금 이 순간 당장 최적인 답을 찾는다. 항상 최적의 결과를 도출하지는 않지만, 최적에 근사한 값을 빠르게 도출 할 수 있다. 탐욕 알고리즘 단계 선택 절차 : 현재 상태에서의 최적의 해답을 선택 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사 해답 검사 : 원래의 문제가 해결 되었는지 검사, 해결이 안되었다면 선택 절차로 돌아가 반복 탐욕 알고리즘 적용 예시 주로 거스름돈 문제가 나오는듯 하다. 편의점 알바중 물건의 값이 4230원이 나왔고 손님은 5000원을 냈다. 거스름돈을 줄때 동전의 갯수를 최소한으로 거슬러 줘야한다. 동전은 500,100,50,10원이 있..

시간복잡도 문제를 해결하기 위한 알고리즘의 로직을 코드로 구현 할때 입력값의 변화에 따라 연산을 실행시 연산 횟수에 비해 시간이 얼마나 걸리는가를 고려하는것 효율적인 알고리즘을 구현하는것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화 하는것 Big-O 표기법 시간 복잡도의 표현법에는 Big-O(빅-오), Big-Ω(빅-오메가), Big-θ(빅-세타)가 있다. 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 나타내는 방법이다. 그중 최악의 경우를 나타내는 Big-O 표기법을 많이 사용 하는데 프로그램이 실행하되는 과정에서 소요되는 최악의 시간까지 고려하기 때문이다. 최선의 경우나 평균의 경우로 문제가 해결 되면 좋겠지만 그렇지 않은 경우에 대하여 대처 할 수 있다. O(1) 입력값이 아무리 ..

재귀함수 (Recursion) 재귀의 사전적 의미 : 원래의 자리로 되돌아가거나 되돌아옴 자기 자신을 호출하는 함수 반복적인 작업을 간결하게 해결 할 수 있다. // 재귀함수 예제 class Recursion{ void recursion(){ System.out.println("제발 그만해.."); recursion(); } } // recursion() 호출시 /* 제발 그만해.. 제발 그만해.. 제발 그만해.. 제발 그만해.. 제발 그만해.. 제발 그만해.. 제발 그만해.. 제발 그만해.. .. */ 재귀 함수의 장점 여러개의 반복문을 사용하지 않아, 코드가 간결, 수정이 용이해진다. 변수를 여러개 사용 할 필요가 없다. 재귀 함수의 단점 반복문과 달리, 코드의 흐름 직관적 파악이 안된다. (선언형 ..

배열에서 1차원 배열은 배열의 크기를 동적으로 할당 할수 없기때문에 배열에 요소를 추가할때 아래와 같은 방법으로 해야함 int[] nums = new int[0]; // 길이가 0인 배열 for(int i=0; i

수(num)를 입력받아 num 까지 총 num + 1 개의 피보나치 수열을 리턴 피보나치 수열 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ... 어떤 수열의 항이 앞의 두항의 합과 같은 수열 public int[] fibonacci(int num) { int[] fibo = new int[num+1]; fibo[0] = 0; // 맨앞 항은 0 고정 for(int i=1; i