728x90 ALGORITHM/ALGORITHM 이론3 [알고리즘 이론] 정렬 알고리즘 정렬 알고리즘이란?배열 등의 데이터 단위를 사용자에 맞춰 순서대로 배치 시켜주는 알고리즘. 선택 정렬 이름과 같이 현제 위치에 들어갈 값을 찾은 후, 정렬하는 알고리즘입니다. 시간 복잡도의 경우 O(n^2)입니다.1. 배열의 크기 만큼 반복문문을 돌려준다. 2. 현제 위치부터 배열의 크기만큼 반복문을 다시 돌려준다. 3. 가장 작은 값을 찾고, 해당 값을 해당 위치와 스왑한다. 4. 2로 돌아간다. int i,j;int aLength;for (i = 0; i 버블 정렬 현제 인덱스의 값과 뒤 인덱스 값을 비교한 후, 큰 값을 뒤로 보내며 정렬하는 알고리즘입니다.시간복잡도는 O(n^2)입니다. 1. 배열 전체를 반복문을 돌려준다. 2. (배열 크기 - 현 인덱스)값만큼 반복분 돌려준다. 3. 현 인덱.. 2024. 8. 18. [알고리즘 이론] 시간 복잡도와 공간 복잡도 복잡도란, 1. 알고리즘의 성능, 효율성을 나타내는 척도2. 알고리즘의 사용 시간 및 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준 3. 빅오(O), 오메가(Ω), 세타(Θ) 표기법 등이 잇다. 빅-오(Big-O) 표기법 최악의 경우를 나타냅니다.즉, 알고리즘을 실행 했을 때 최대로 걸릴 수 있는 시간을 나타냅니다. O(1): n이 증가하여도 실행 시간은 동일한 알고리즘 (EX, 기본 연산 수)O(log n): 연산이 한 번 실행될 때 마다 데이터의 크기가 절반 감소하는 알고리즘 (EX, 이진 탐)O(n): n의 값이 증가함에 따라 선형적으로 증가하는 알고리즘 (EX, 1중 for)O(n log n): O(n)의 알고리즘과 O(log n)의 알고리즘이 중첩된 형태 (EX, 퀵 정렬)O(n^.. 2024. 8. 8. [알고리즘 이론] DFS와 BFS 더보기* DFS와 BFS 이해 전 그래프에 대한 이론을 알고 있다면 도움이 될 것이다. DFS 깊이 우선 탐색(Depth-First Seartch)는 그래프 완전 탐색 기법 중 하나이다. DFS는 그래프의 시작 노드부터 시작하여 탐색할 분기를 정하고, 끝까지 탐색 후 다음 분기로 넘어가서 다시 탐색하여 모두 다 탐색하는 알고리즘이다. DFS는 Stack 또는 재귀함수를 이용하여 구현할 수 있으며 시간 복잡도는 O(노드 수 + 에지 수)이다. 재귀함수를 사용할떈 스택 오버플로를 조심하며 사용해야한다. 우선 이런 그래프가 있다고 가정해보자. 이 그래프를 인접 리스트로 표현한다면 아래처럼 표현 할 수 있다. 1) 1부터 시작한다고 가정하고 1을 Stack에 넣음과 동시에 1이 들어 왔다는 것을 체.. 2023. 8. 1. 이전 1 다음 728x90
