늘 겸손하게

숫자 카드 2 이분 탐색의 upper bound와 lower bound를 이용하여 푸는 문제이다. upper bound 와 lower bound 란? 이분 탐색으로 배열에서 숫자를 탐색할 때 찾으려는 숫자의 개수가 배열에서 여러 개 존재할 수 있다. 이때 탐색된 동일한 숫자들중 가장 작은 인덱스 값이 lower bound, 가장 큰 인덱스 값이 upper bound이다. 예로 길이가 10이고 각 원소 값이 { 1 , 3, 5, 9 , 11 , 13 ,19 , 19 , 19 , 20 } 인 배열에서 19를 찾는다고 해보자. 19가 가장 처음 나온 인덱스는 6 , 가장 나중에 나온 인덱스는 8 이므로 lower bound는 6, upper bound는 8이 된다. 이를 이용하여 문제를 해결해야 시간 초과가 ..

수 찾기 N 개의 수를 입력받고 M개의 숫자가 주어졌을 때 해당 숫자가 N 개의 숫자들 중에 존재하는지 판별하는 문제. 문제 풀이 N 과 M의 범위가 1 이상 100,000이다. 그러므로 선형 검색(순차 검색)으로 코드를 짜면 시간제한에 걸릴 확률이 높다. 정수를 찾을때는 이분 탐색 (binary search) 알고리즘을 적용하여 검색을 하자. 그리고 모든 정수는 -2^31 보다 크거나 같고 2^31보다 작다는 제한이 있다. int 자료형의 범위는 -2^31 -1 ~ 2^31 - 1 이므로 음수 부분에서 걸린다. 그러므로 자료형을 long 형으로 해주자. 이분 탐색은 정렬된 배열에서 가능하므로 입력받은 N 개의 정수를 배열로 받아 정렬시키는 일부터 한다. import java.util.Arrays; 를 ..

피보나치 수 6 n 번째 피보나치 수를 구하면 되는 문제 이지만 n이 1,000,000,000,000,000,000 보다 작거나 같은 자연수이다. 재귀 함수를 이용하거나 단순하게 반복문으로 F2부터 Fn까지 구하려면 시간 초과가 발생한다. 시간 내에 문제를 해결하려면 다른 방식으로 접근해야 한다. 1. 방정식을 행렬식으로 표현 Fn+2 = Fn+1 + Fn 인 피보나치 수의 공식을 행렬 꼴로 바꾸어야 한다. 위 식만으로는 부족하므로 식 하나를 더 구한다. Fn+1을 Fn+1 = Fn+1 + 0 * Fn로 표현 가능하므로 위 두 식을 조합하면 위 식을 얻을 수 있다. 좌변의 를 u(n+1)로 보면 를 u(n)으로 표현할 수 있고 이고 A를 라고 하면 u(n+1) = A * u(n) 이 성립함을 알 수 있다..

간단한 행렬 곱셈 문제 정수 N , M , K , 행렬의 원소들을 입력받은 후 행렬 곱셈을 수행하면 되는 문제. ( N , M ) 행렬과 ( M, K ) 행렬을 곱하면 ( N , K ) 행렬이 나오고, 행렬의 곱셈식을 이용하여 코드를 생성하면된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 #include using namespace std; const int MAX = 100; int A[MAX][MAX]; int B[MAX][MAX]; int result[MAX]..