일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- Merge Sort
- 수학문서
- 자료구조
- naive sort
- dfs
- C++
- BFS
- 시간복잡도
- 실수자료형
- LU분해
- 정렬
- non-nullable
- 정수자료형
- 수치미분
- 큐
- 파이썬
- 스택
- 보간탐색
- APIE
- 알고리즘
- programable switch
- 백준
- Tikz
- PGF
- 재귀
- Unity Editor
- [Required]
- C#
- 탐색
- quick sort
- Today
- Total
목록전체 글 (38)
코젤브
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/SWH4r/btssAEoljuF/2vxLcbVMwwnMNXkNywIF50/img.jpg)
https://youtube.com/playlist?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC (이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬 www.youtube.com
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bgWymU/btrC9LjuArE/ZJKbk2JFPjYmxPao8S2sSK/img.png)
동적계획법(Dynamic Programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 접근하는 방법이다. 부분 문제가 반복되고 최적의 원칙을 만족하는 문제를 일반적인 방법에 비해 적은 시간 내에 풀 때 사용한다. ex) 피보나치, 정수삼각형, 이항 계수 상향식 해결법(Bottom-Up 방식) 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식 최적의 원칙 : 어떤 문제의 입력에 대한 최적해가 그 입력을 나누어 쪼갠 여러 부분에 대한 최적해를 항상 포함하고 있으면, 그 문제는 최적의 원칙이 적용된다고 한다. 백준 2579번: 계단 오르기 #include #define MAX 301 using namespace std; int main() { int n; int DP[301];..
Backtracking : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. (최적화 문제와 결정 문제를 푸는 방법) : 모든 경우가 아닌 제약 조건에 맞는 후보해에 대해서만 탐색한다. 즉, 불필요한 탐색을 하지 않고 이전 단계로 돌아와 다른 후보해를 탐색한다. 해를 찾다가, 지금의 경로가 해가 될 것 같지 않으면, 그 경로로 가지 않고 바로 되돌아간다. (즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적) 이를 가지치기라고 하는데, 불필요한 부분은 빼고 최대한 올바른 쪽으로 간다는 의미이다. 일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/GxeBU/btrB2XMjWvE/Cvtzvuq0DLicqfwh5EYdb0/img.jpg)
백준 11047번 그리디 알고리즘을 통해 해결할 수 있는 간단한 문제이다. 특히 동전의 단위가 배수이므로, 큰 단위의 동전부터 나눠주고, 차례로 진행하면 된다. #include using namespace std; int main() { int n, k; int sum = 0; int a[11]; cin >> n >> k; for (int i = 0; i > a[i]; for (int i = n - 1; i >= 0; i--) { sum += k / a[i]; k = k % a[i]; } cout
- Big O 표기법 = worst와 비슷 : 점근적 상한 : 궁극적으로 이것보단 좋다(=기울기가 같거나 낮다) - Ω 표기법 : 점근적 하한 : 아무리 좋아도 이것보다 좋아질 수 없다(=기울기가 높다) - Θ 표기법 : 점근적 협소 : 차수가 같다(=기울기가 같다) - Small o 표기법 : 차수가 작다(=기울기가 낮다) (같을 수 없다) - 차수의 주요 성질 g(n) ∈ O(f(n)) f(n) ∈ Ω(g(n)) g(n) ∈ Θ(f(n)) f(n) ∈ Θ(g(n)) 로그 복잡도 함수는 모두 같은 카테고리 => Θ(lg n) 지수 복잡도 함수는 모두 같은 카테고리 X n! 는 어떤 지수 복잡도 함수보다 나쁨 좋은 것부터 나열 n c ≤ 0, d > 0 일 때, g(n) ∈ O(f (n)), 그리고 h(..