알고리즘
-
병합정렬(Merge Sort) 파헤치기알고리즘/시간복잡도 2025. 5. 11. 21:46
✅ 병합 정렬 (Merge Sort)란?"분할 정복(Divide and Conquer)" 전략을 사용하는 정렬 알고리즘입니다.배열을 반으로 쪼개고각 부분을 재귀적으로 정렬한 뒤두 정렬된 부분을 하나로 합쳐서(merge) 최종 정렬된 배열을 만듭니다.병합 정렬은 배열을 왼쪽 → 오른쪽 순서대로 나누고 병합합니다.🔄 병합 정렬 동작 순서예: [5, 2, 4, 1, 3]분할 단계 (Divide)[5,2,4,1,3]→ [5,2] [4,1,3]→ [5][2] [4][1,3]→ [1][3]최종 분할 결과[5] [2] [4] [1] [3] 병합 단계 (Merge)→ [2,5]→ [1,3] → [1,3,4]→ [1,2,3,4,5] 병합 순서 : 가장 마지막에 나뉜 조각들부터 병합하기 시작해요 (재귀 구조의 특성).병..
-
버블정렬의 최악,평균, 최선 시간 복잡도 모두 동일한가..?알고리즘/시간복잡도 2025. 5. 11. 21:31
✅ 1. 버블 정렬 (Bubble Sort)🧠 개념인접한 두 수를 비교해서 큰 수를 뒤로 "버블처럼" 밀어내는 정렬매 회전마다 가장 큰 수가 맨 뒤로 이동전체 배열을 여러 번 반복하며 정렬🧮 동작 예시int[] arr = {5, 3, 2, 4, 1};// 첫 번째 반복: [3,2,4,1,5]// 두 번째 반복: [2,3,1,4,5]// ...⏱ 시간 복잡도경우시간 복잡도최악 / 평균 / 최선O(n²)/ O(n²) /O(n) n개의 원소가 있을 때, n번 반복하며 각각 (n-1), (n-2), ..., 1번 비교 → 총 (n*(n-1))/2 ≈ O(n²)작은 입력에는 문제 없지만, N=1,000,000인 경우엔 1조번 연산이 필요하므로 절대 사용 금지✅ 버블 정렬 시간 복잡도 정리경우시간복잡도 설명최..
-
JAVA 알고리즘 시간복잡도 빅오, 빅오메가, 빅세타알고리즘/시간복잡도 2025. 5. 11. 21:18
✅ 시간 복잡도의 주요 표기법(Big-O)표기명칭의미예시상황O(1)상수 시간입력 크기와 무관하게 실행 시간 고정배열의 인덱스 접근O(log n)로그 시간입력 크기가 커질수록 조금만 증가이진 탐색O(n)선형 시간입력 크기에 비례해 실행 시간 증가배열 한 번 순회O(n log n)로그 선형 시간분할+정복 알고리즘병합 정렬, 퀵 정렬 평균O(n²)2차 시간이중 루프 등버블 정렬, 이중 for문O(2ⁿ), O(n!)지수/팩토리얼 시간입력 크기 증가에 따라 급격히 시간 증가완전 탐색, 순열 생성🔍 코드 분석 – 시간 복잡도public class timeComplexityExample1 { public static void main(String[] args) { //1~100번째 사이 값 랜덤 ..
-
시간 복잡도 Big-O (O), Big-Ω (Ω), Big-Θ (Θ)알고리즘/시간복잡도 2025. 5. 11. 21:14
🧠 시간 복잡도 표기법 총정리✅ 1. 표기법의 목적별 분류표기법이름의미무엇을 나타내는가?Big-O (O)빅오최악의 시간가장 오래 걸리는 경우. 성능의 상한을 보장Big-Ω (Ω)빅오메가최선의 시간가장 빨리 끝나는 경우. 성능의 하한을 나타냄Big-Θ (Θ)빅세타평균/정확한 시간실제 시간 복잡도가 상한=하한일 때. 정확한 경계 ✅ 2. 시간 복잡도 유형별 분류 (O, Ω, Θ는 모두 해당 가능)복잡도유형표기의미예시 알고리즘상수 시간O(1)입력 크기와 무관해시맵 조회, 배열 인덱스 접근로그 시간O(log n)반씩 줄이기이진 탐색선형 시간O(n)한 번 순회단순 for문, 선형 탐색로그-선형 시간O(n log n)분할+정복병합 정렬, 퀵 정렬 평균2차 시간O(n²)이중 루프버블 정렬, 삽입 정렬지수/팩토리얼O..