일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 리트코드
- 그레이들
- java
- 안드로이드
- DFS
- 다이나믹 프로그래밍
- Database
- frontend
- LeetCode
- network
- 백준
- 자바
- Redux
- 동적 계획법
- 알고리즘
- git
- vscode
- Javascript
- CS
- Algorithm
- db
- TypeScript
- react
- Python
- Graph
- Data Structure
- DP
- 프로그래머스
- VIM
- BFS
- Today
- Total
목록분류 전체보기 (390)
늘 겸손하게
수 찾기 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) 이 성립함을 알 수 있다..
이차원 배열을 동적 할당해보자 동적 할당을 위해서 malloc이 필요하다. #include 혹은 #include 을 추가하여 malloc을 사용 가능하도록 한다. 1. 배열을 저장할 배열을 생성 1 2 3 4 5 6 7 int** arr; int a, b; cin >> a >> b; arr = (int**)malloc(sizeof(int*) * (a)); cs a, b는 사용자로부터 입력받는 숫자로 a는 배열의 개수, b는 배열의 원소 개수로 가정한다. 더블 포인터 arr를 선언하고 입력받은 정수 값 a를 이용하여 a개의 배열 주소 값들을 저장할 배열을 malloc으로 이용하여 생성하고 생성한 배열의 주소 값을 포인터 arr에 할당한다. ( sizeof(int*) * a ) 값만큼의 크기를 생성한 이유는..
간단한 행렬 곱셈 문제 정수 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]..