일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 스택
- API
- C++
- .net maui
- Get
- c++ 버전 확인
- REDIS
- maui
- 정렬
- mysql
- dfs
- BFS
- 자료구조
- .net core
- __cplusplus
- .NET
- 재귀
- asp.net core
- sql
- quick sort
- 파이썬
- C#
- 탐색
- 백준
- 큐
- asp.net
- Merge Sort
- 시간복잡도
- file *
- 알고리즘
- Today
- Total
목록컴공의 일상 (47)
코젤브
나의 경우 default 경로로 설정하면 그냥 Program Files\Unity 20XX.X.XX 식으로 설치가 되었는데, 이렇게 되면 버전을 유니티에서 접근할 수 없었다. 따라서 Program Files\Unity\Hub\Editor 아래에 각 버전을 설치하니 문제 없이 접근할 수 있었다. 특히 새로운 bulid platform를 설정하기 위해 추가적으로 Android나 IOS의 Support-for-Editor를 설치할 때 유의하도록 하자.
오늘은 이어서 탐색 알고리즘 DFS, BFS 에 대해 공부하겠다! 더보기 사실 차근차근 진도를 나가면서 블로그에 정리하려고 했으나, 항상 밀려서 급하게 정리한다. 알고리즘 개념에 해당하는 간단한 세미코테 문제들도 곧 올리겠다! 탐색 알고리즘 : 리스트/배열 내에서 특정 원소를 탐색하는 방법 DFS, BFS를 공부하기 전, Stack과 Queue의 자료구조와 그래프에 대해 간단하게 복습하자. 자료 구조 데이터를 표현 관리 처리하기 위한 구조 Stack : 선입후출 구조 먼저 들어온 것이 나중에 나간다 first in last out (FILO) Queue : 선입선출 구조 들어온 순서대로 나간다 first in first out (FIFO) 그래프 유한개의 꼭지점 Vertex의 집합 V와 두 꼭지점을 원소..
💡 내용 순차탐색 이진탐색 보간탐색 속도 비교 탐색 알고리즘 : 리스트/배열 내에서 특정 원소를 탐색하는 방법 순차 탐색 가장 기본적인 탐색 알고리즘 주어진 데이터를 찾기 위해 처음부터 하나씩 차례로 확인 시간복잡도: O(n) 단점 : 데이터가 큰 경우에는 적합하지 않음 장점 : 데이터가 작거나 중간 정도는 적당 / 미리 정렬 필요 X L=[9,8,1,2,7,3,6,4,5] def LinearSearch(L, n): for i in range(0, len(L)): if L[i] == n: return i return -1 print(LinearSearch(L, 3)) Binary Search (이진 탐색) 배열 내부 데이터가 정렬되어 있어야만 사용 가능 배열 크기 작으면 효율적이지 않음 각 단계에서 배열..
알고리즘 : 어떤 문제를 해결하기 위한 정해진 절차 정렬 알고리즘 : 데이터를 특정 기준에 따라 순서대로 나열 naive sort : 선택 정렬 가장 작은 원소를 찾아 맨 앞으로 이동 그 다음 작은 원소를 찾아 두 번째로 이동 위 과정의 반복 시간복잡도: O(n²) L=[4,2,1,0,5,3,6] def sort_list_naive(L): nlen= len(L) for i in range(0, nlen): idx = i for j in range(i+1, nlen): if L[idx]>L[j]: idx = j L[i], L[idx] = L[idx], L[i] return L print(sort_list_naive(L)) insert sort : 삽입 정렬 현재 위치 이전은 정렬되어 있다 가정하고, 이후의..
https://youtube.com/playlist?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC (이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬 www.youtube.com
동적계획법(Dynamic Programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 접근하는 방법이다. 부분 문제가 반복되고 최적의 원칙을 만족하는 문제를 일반적인 방법에 비해 적은 시간 내에 풀 때 사용한다. ex) 피보나치, 정수삼각형, 이항 계수 상향식 해결법(Bottom-Up 방식) 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식 최적의 원칙 : 어떤 문제의 입력에 대한 최적해가 그 입력을 나누어 쪼갠 여러 부분에 대한 최적해를 항상 포함하고 있으면, 그 문제는 최적의 원칙이 적용된다고 한다. 백준 2579번: 계단 오르기 #include #define MAX 301 using namespace std; int main() { int n; int DP[301];..
Backtracking : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. (최적화 문제와 결정 문제를 푸는 방법) : 모든 경우가 아닌 제약 조건에 맞는 후보해에 대해서만 탐색한다. 즉, 불필요한 탐색을 하지 않고 이전 단계로 돌아와 다른 후보해를 탐색한다. 해를 찾다가, 지금의 경로가 해가 될 것 같지 않으면, 그 경로로 가지 않고 바로 되돌아간다. (즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적) 이를 가지치기라고 하는데, 불필요한 부분은 빼고 최대한 올바른 쪽으로 간다는 의미이다. 일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 ..
백준 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(..
- 알고리즘의 분석 시간복잡도 분석: 입력 크기에 따라 단위연산이 몇번 수행되는지 결정하는 절차 표현 척도 - 단위연산: 비교, 지정 … - 입력 크기: 배열 크기, 리스트의 길이, 행렬에서 행과 열의 크기 … - 알고리즘 분석 방법의 종류 모든 경우 분석: (입력 크기에만 종속) 입력값과 무관하게 결과값 일정 => 적용 한정적 최악 경우 분석: (입력 크기와 입력 값에 종속) 단위연산의 수행횟수 최대 평균 경우 분석: (입력 크기와 입력 값에 종속) 평균 최선 경우 분석: (입력 크기와 입력 값에 종속) 단위연산의 수행횟수 최소 - [예시] 배열 덧셈 알고리즘 : 배열에 있는 모든 수를 더해라 case1) 단위연산: 덧셈 입력 크기: 배열의 크기 n 모든 경우 분석: 루프가 n번 반복, 따라서 T(n)..