알고리즘9 [JAVA] 퀵정렬(Quick Sort) 개념과 코드 구현 퀵정렬(Quick Sort)은 가장 빠른 정렬 알고리즘 중 하나로 사용되는 정렬 알고리즘이다. 다른 원소와 비교만으로 정렬을 수행하는 비교정렬이다. 값의 정렬이후 순서가 초기 순서와 달라질 수 있는 불안정 정렬이고, 분할 정복 알고리즘에 속한다. 구분 최악 시간복잡도 최선 시간복잡도 평균 시간복잡도 공간복잡도(메모리) 안정성 퀵정렬 O(N^2) O(n log n) O(n log n) 평균적으로 O(log n), 최악의 경우 O(n) N 알고리즘 리스트 가운데에서 하나의 원소를 고른다. 이 원소를 피벗(Pivot)이라고 한다. 피벗 앞에는 피벗보다 작은 모든 원소가 오고 피벗 뒤에는 피벗보다 큰 모든 원소가 오도록 리스트를 둘로 나눈다. 분할된 각 리스트에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹.. 2023. 4. 17. [JAVA] 병합정렬(Merge Sort) 개념과 코드 구현 병합 정렬(Merge Sort)은 비교 기반 정렬 알고리즘이다. 문제를 작은 여러 문제로 쪼개서 각각을 해결하고 결과를 모아서 원래 문제를 해결하는 방법이다. 안정 정렬이며 분할 정복 알고리즘의 하나이다. 안정 정렬: 반복되는 요소를 입력때와 동일한 순서로 정렬 시키는 정렬(중복된 부분은 순서가 유지되는 정렬) 분할 정복 알고리즘: 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법. 보통 재귀함수를 통해 구현된다. 구분 최악 시간복잡도 최선 시간복잡도 평균 시간복잡도 공간복잡도(메모리) 안정성 합병정렬 O(n log n) O(n log n) O(n log n) O(n) Y 알고리즘 N개의 길이를 가진 배열 리스트를 각각 하나의 원소만 포함하는 N개의 부분 리스트로 분할한다. 부분.. 2023. 4. 17. 26일차: 알고리즘(Algorithm)과 시간복잡도(Time Complexity) ❯ 알고리즘(Algorithm) 알고리즘이란, 문제를 해결하는 최선의 선택을 구하는 것을 의미한다. 이를 위해 문제를 정확하게 이해하고, 어떻게 해결할지 전략을 수립하고, 수립한 전략을 실제 코드로 작성할 수 있어야한다. 알고리즘 문제 풀이를 위해서는 의사코드(PseudoCode)를 잘 작성하는것이 중요하다. 자연어(혹은 프로그램언어)를 사용하여 프로그램 작동 논리를 작성하게된다. 의사코드를 구체적이고 논리적으로 작성해야 코드 작성시 시간이 단축되고 디버깅이 용이해진다. ❯ 시간 복잡도(Time Complexity) 이때까지 문제 풀이 혹은 기능 구현만 신경써서 연산 수행시간은 전혀 고려하지 않았다. 시간 복잡도란, 프로그램 입력값과 연산 수행시간의 상관관계를 나타내는 척도로 입력값의 변화에 따라 연산을.. 2023. 3. 21. 이전 1 2 다음
