💡 알고리즘의 효율성을 알아내기 위해 알고리즘을 측정하는 방법 복잡도의 종류 시간 복잡도 공간 복잡도 프로그램이 시작하며 종료될때까지 걸리는 시간을 측정하는 방법 프로그램을 실행하여 완료까지 필요로하는 저장공간의 양을 측정하는 방법 공간 복잡도 (Space Complexity) 프로그램을 실행하여 완료까지 필요로하는 저장공간의 양을 측정 공간복잡도는 시간 복잡도와 반비례하는 경우가 많다. 컴퓨터의 발전으로 대용량 지원이 많이되며 시간 복잡도보다 덜 중요시되는 경우가 많다. 공간 복잡도 계산법 공간 복잡도는 알고리즘에 사용되는 저장 공간을 계산하면된다. 빅 오 표기법으로 표현할 수 있어야한다. 예제) int Factoria(int _fac){ int _return = 1; for (int n = 2; n ..
DFS와 BFS DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프 탐색 알고리즘으로, 각각 다른 방식으로 노드를 탐색하면서 그래프의 모든 노드를 방문하는데 사용된다. 각각의 특징과 장단점을 살펴보자. 시간복잡도 두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다. DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합한다. DFS BFS 장점 메모리 사용이 상대적으로 적다. 스택을 사용하므로 각 노드를 방문하기 위해 추가 메모리가 거의 필요하지 않다. 경로가 길 경우 BFS보다 빠르게 해답을 찾을 수 있다. 일반적으로 재귀 구조로 구현하기 쉽다. 최단 경로를 보장한다. 무한루프에 빠질 위..
최대한 넓게 이동하고 더 이동이 갈 수 없을 때 아래로 이동 너비우선 탐색이란 기준점 루트 노드(Root Node) 혹은 임의 Node에서 가장 인접한 노드를 먼저 탐색하는 방법이다. 루트에 가장 가까운 노드 탐색 같은 깊이의 모든 노드를 탐색했다면 다음 깊이로 이동 시간복잡도 인접 리스트 : O(N + E) 인접 행렬 : O(V^2) 접점 Node(N), 간선(E) 특징 큐로 구현이 가능 장점 단점 최단 경로를 보장한다. 무한루프에 빠질 위험이 적다. 사이클이 있는 그래프라도 노드를 중복 방문하지 않기 때문이다. 일반적으로 반복 구조로 구현하기 쉽다. 메모리 사용이 많다. 모든 인접 노드를 큐에 저장해야 하기 때문에 DFS보다 더 많은 메모리가 필요하다. 긴 경로를 탐색하는 데에는 시간이 더 오래 걸린..
DFS 최대한의 깊이로 탐색, 더 이상 깊이 갈 곳이 없을 경우 다음 브랜치로 이동 깊이우선 탐색이란 기준점이되는 루트 노드(Root Node) 혹은 임의 Node에서 다음 분기(Branch)로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방법이다. 한쪽 방향으로 최하단 노드까지 탐색 더이상 탐색이 불가능하면 다른 방향 탐색 한 브랜치를 모두 탐색하면 다음 브랜치도 동일하게 탐색 시간복잡도 인접 리스트 : O(N + E) 인접 행렬 : O(V^2) 접점 Node(N), 간선(E) 특징 스택 혹은 재귀함수로 구현이 가능 장점 단점 메모리 사용이 상대적으로 적다. 스택을 사용하므로 각 노드를 방문하기 위해 추가 메모리가 거의 필요하지 않다. 경로가 길 경우 BFS보다 빠르게 해답을 찾을 수 있다. 일반적으로 ..
- Total
- Today
- Yesterday
- 프로세스
- CPU
- dynamic_cast
- const
- 멀티스레드
- 입출력
- 백준
- thread
- 인터럽트
- malloc
- 초기화
- 컴파일
- 스레드
- 수학
- 크기
- 함수
- New
- 클래스
- 알고리즘
- 명령어
- 포인터
- 게임수학
- 할당
- 구조
- 메모리
- c++
- 상속
- static_cast
- 운영체제
- 레지스터
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |