알고리즘16 [알고리즘] 시간복잡도 순서(Big O) 빅오(Big O)표기법으로 보는 시간 복잡도프로그래밍에서 알고리즘의 시간 복잡도(Time Complexity)는 알고리즘이 어떤 문제를 해결하는 데 필요한 시간이 입력의 크기에 따라 어떻게 변하는지를 나타내는 척도입니다. 시간 복잡도를 표기하는 데는 여러 가지 방법이 있지만, 가장 널리 사용되는 표기법은 빅 오(Big O) 표기법입니다. 빅 오 표기법으로 표현된 시간 복잡도의 종류를 빠른 순서부터 느린 순서대로 나열하면 다음과 같습니다.O(1) 상수 시간(Constant Time)입력 데이터의 크기와 상관없이 알고리즘의 실행 시간이 일정합니다.O(log n) 로그 시간(Logarithmic Time)입력 데이터의 크기가 커질수록, 실행 시간이 로그 적으로 증가합니다.이진 탐색(Binary Search.. 2024. 5. 16. [알고리즘] 이진 탐색(Binary Search) 이진 탐색(Binary Search) 정렬된 배열에서 특정 값을 찾는 알고리즘입니다.(필수조건!) 특징 반복 또는 재귀적 구현: 이진 탐색은 반복문이나 재귀 함수를 사용하여 구현할 수 있습니다. 정렬된 배열에서 사용: 이진 탐색은 정렬된 배열에서만 사용할 수 있습니다. 배열의 중간 값을 기준으로 탐색 범위를 좁혀가며 값을 찾습니다. 시간 복잡도: 이진 탐색의 시간 복잡도는 O(log n)입니다. 배열을 반으로 분할하면서 탐색 범위를 절반으로 줄여나가기 때문에 탐색 시간이 로그 시간에 비례합니다. 알고리즘 동작 방식 탐색 범위의 시작 인덱스와 끝 인덱스를 설정합니다. 탐색 범위의 중간 인덱스를 찾습니다. 중간 값과 찾고자 하는 값을 비교합니다. 중간 값이 찾고자 하는 값과 일치하면 탐색 성공입니다. 중간 .. 2023. 7. 16. [알고리즘] 병합 정렬(Merge Sort) 병합 정렬(Merge Sort) 특징 안정 정렬(Stable Sort): 동일한 값에 대해 상대적인 순서가 유지됩니다. 즉, 동일한 값의 원소들은 입력 배열에서의 순서와 동일한 순서로 정렬됩니다. 분할 정복(Divide and Conquer): 큰 문제를 작은 문제로 분할하여 해결하는 방식을 사용합니다. 추가적인 메모리 사용: 임시 배열을 사용하여 원소들을 병합하는 과정에서 추가적인 메모리가 필요합니다. 평균적으로 빠른 속도: 평균 시간 복잡도가 O(n log n)으로 매우 효율적입니다. 비교 기반 정렬(Comparison Sort): 원소들의 상대적인 크기를 비교하여 정렬합니다. 알고리즘 동작 방식 주어진 배열을 반으로 분할합니다. 분할된 부분 배열에 대해 재귀적으로 병합 정렬을 수행합니다. 분할된 부.. 2023. 7. 16. [알고리즘] 퀵 정렬(Quick Sort) 퀵 정렬(Quick Sort) 특징 불안정 정렬(Unstable Sort): 동일한 값에 대해 상대적인 순서가 유지되지 않을 수 있습니다. 제자리 정렬(In-place Sort): 입력 배열 내에서 정렬이 수행되며, 추가적인 메모리를 사용하지 않습니다. 분할 정복(Divide and Conquer): 큰 문제를 작은 문제로 분할하여 해결하는 방식을 사용합니다. 평균적으로 빠른 속도: 평균적으로 O(n log n)의 시간 복잡도를 가지므로 대부분의 경우에 빠른 속도를 보입니다. 재귀적 구현: 주로 재귀 함수를 통해 구현되며, 스택의 호출로 인해 추가적인 메모리를 사용할 수 있습니다. 알고리즘 동작 방식 배열에서 하나의 원소를 피벗(Pivot)으로 선택합니다. 피벗을 기준으로 작은 값은 피벗의 왼쪽에, 큰 .. 2023. 7. 16. [알고리즘] 버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort) 특징 안정 정렬(Stable Sort): 동일한 값에 대해 상대적인 순서가 유지됩니다. 즉, 동일한 값의 원소들은 입력 배열에서의 순서와 동일한 순서로 정렬됩니다. 제자리 정렬(In-place Sort): 입력 배열 이외에 추가적인 메모리를 사용하지 않습니다. 입력 배열 내에서 정렬이 수행됩니다. 비교 기반 정렬(Comparison Sort): 원소들의 상대적인 크기를 비교하여 정렬합니다. 알고리즘 동작 방식 버블 정렬은 인접한 원소들을 비교하고 필요에 따라 위치를 교환하는 과정을 반복하여 전체 배열이 정렬될 때까지 진행합니다. 첫 번째 원소부터 인접한 원소와 비교합니다. 인접한 두 원소의 순서가 잘못되어 있다면, 두 원소의 위치를 교환합니다. 배열의 끝까지 위의 과정을.. 2023. 7. 16. [알고리즘] 삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) 특징 안정 정렬(Stable Sort): 동일한 값에 대해 상대적인 순서가 유지됩니다. 즉, 동일한 값의 원소들은 입력 배열에서의 순서와 동일한 순서로 정렬됩니다. 제자리 정렬(In-place Sort): 입력 배열 이외에 추가적인 메모리를 사용하지 않습니다. 입력 배열 내에서 정렬이 수행됩니다. 비교 기반 정렬(Comparison Sort): 원소들의 상대적인 크기를 비교하여 정렬합니다. 알고리즘 동작 방식 삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어 처리합니다. 정렬되지 않은 부분의 첫 번째 원소를 정렬된 부분에 삽입하는 과정을 반복하여 전체 배열이 정렬될 때까지 진행합니다. 정렬되지 않은 부분에서 첫 번째 원소를 선택합니다. 이 원소를 정렬.. 2023. 7. 16. 이전 1 2 3 다음
