본문 바로가기

Computer Science/알고리즘14

[알고리즘] 그리디 알고리즘이란? (크루스칼 알고리즘, 프림 알고리즘, 다익스트라 알고리즘) 목차 그리디 알고리즘이란? 그리디 알고리즘 정당성 그리디 알고리즘 종류 그리디 알고리즘 예시 그리디 알고리즘과 DP 비교 1. 그리디 알고리즘이란? 그리디 알고리즘은 현재 이 순간에서 가장 최적의 해를 선택하는 알고리즘이다. 앞으로 진행될 선택에 끼칠 영향을 고려하지 않고 매 순간 선택에서 현재가 항상 최적의 해를 가져야 하기 때문에, 욕심쟁이 알고리즘이라고도 부른다. 현재 문제에서 가질 수 있는 최적의 해를 선택하면 다음 부분적인 문제에 대한 선택이 이뤄진다. 다시 말해, Top-Down 방식으로 더 작은 문제에 대한 최적의 해를 선택하고, 한번 선택된 결정은 다시 번복할 수 없다. 이러한 이유로 부분 문제는 최적의 해를 가지지만, 모든 전체 문제에서 최적의 해를 가진다고 말할 수 없다. 2. 그리디 .. 2024. 3. 8.
[알고리즘] 퀵 정렬 (Quick Sort, 개념과 장단점, 과정, 자바 코드 구현, 시간복잡도, 공간복잡도) 목차 퀵 정렬이란? 퀵 정렬 과정 퀵 정렬 구현 (자바 코드) 시간복잡도 공간복잡도 정렬 알고리즘 비교 1. 퀵 정렬이란? 피벗을 기준으로 왼쪽은 피벗보다 작은 값, 오른쪽은 피벗보다 큰 값을 가질 수 있도록 값을 이동시킨다. 분할과 동시에 정렬이 이뤄지며, 분할된 배열의 크기가 1이 되면 정렬이 완료된다. (특징) 최선 및 평균 시간복잡도는 O(n log(n))이며, 최악의 시간복잡도는 O(n^2)이다. O(n log(n))의 시간복잡도를 가지는 병합 정렬보다 상대적으로 속도가 빠르다. JAVA의 Arrays.sort()에서 사용되는 정렬 알고리즘이다. (장점) 배열 내에서 교환하는 방식(제자리 정렬)으로 추가적인 메모리 공간을 필요로 하지 않는다. 다른 알고리즘과 비교했을 때도 가장 빠르다. (단점).. 2024. 2. 28.
[알고리즘] 합병 정렬 (Merge Sort, 개념과 장단점, 과정, 자바 코드 구현, 시간복잡도, 공간복잡도) 목차 합병 정렬이란? 합병 정렬 과정 합병 정렬 구현 (자바 코드) 시간복잡도 공간복잡도 정렬 알고리즘 비교 1. 합병 정렬이란? 하나의 배열을 두 개의 균등한 배열로 분할해 정렬하고, 두 배열을 다시 합하여 정렬한다. 큰 문제를 작은 단위의 문제들로 쪼개어 해결해가는 방식인 분할 정복을 이용한 정렬 알고리즘이다. (특징) 배열을 이용할 경우 추가적인 메모리가 필요하지만, 연결리스트를 이용할 경우에는 필요하지 않다. 최선, 평균, 최악의 시간복잡도는 모두 O(n log(n))이다. (장점) 연결리스트를 이용할 경우, 링크 인덱스만 변경하면 되므로 이동 연산이 줄어든다. (추가적인 메모리 필요 X) 퀵 정렬과 비교했을 때 데이터 분포에 영향을 받지 않는다. (단점) 배열을 이용할 경우, 추가적인 메모리(임.. 2024. 2. 28.
[알고리즘] 버블 정렬 (Bubble Sort, 개념과 장단점, 과정, 자바 코드 구현, 시간복잡도, 공간복잡도) 목차 버블 정렬이란? 버블 정렬 과정 버블 정렬 구현 (자바 코드) 시간복잡도 공간복잡도 정렬 알고리즘 비교 1. 버블 정렬이란? 연속하는 두 개의 원소를 오름차순 혹은 내림차순으로 비교하며 교환한다. 정렬되지 않는 값들 중 가장 큰 값(혹은 가장 작은 값)이 끝으로 이동하게 된다. (특징) 최선, 평균, 최악의 시간복잡도는 모두 O(n^2)이다. 직관적이나 거의 사용하지 않는 정렬 알고리즘이다. (장점) 알고리즘이 단순하고, 구현이 쉽다. 배열 내에서 교환하는 방식(제자리 정렬)으로 추가적인 메모리 공간을 필요로 하지 않는다. (단점) 배열의 길이가 길어질수록 지수적으로 시간이 증가하기 때문에 비효율적이다. 하나의 요소가 끝으로 이동하기 위해서 배열의 모든 요소와 교환이 이뤄져야 한다. 2. 버블 정렬.. 2024. 2. 28.
[알고리즘] 삽입 정렬 (Insertion Sort, 개념과 장단점, 과정, 자바 코드 구현, 시간복잡도, 공간복잡도) 목차 삽입 정렬이란? 삽입 정렬 과정 삽입 정렬 구현 (자바 코드) 시간복잡도 공간복잡도 정렬 알고리즘 비교 1. 삽입 정렬이란? 선택한 요소를 이미 정렬된 요소들과 비교해 알맞은 위치에 삽입한다. 선택한 요소의 앞쪽 요소들은 이미 정렬된 상태를 유지하고 있으므로, 매 순서마다 바로 이전 인덱스 요소와 비교하여 원소가 삽입될 올바른 위치를 찾아낸다. (특징) 최선의 시간복잡도는 O(n)이며, 평균 및 최악의 시간복잡도는 O(n^2)이다. O(n^2)의 시간복잡도를 가지는 선택 정렬과 버블 정렬에 비해 상대적으로 속도가 빠르다. (장점) 알고리즘이 단순하고, 구현이 쉽다. 이미 정렬된 배열일 경우, 매번 1번의 비교로 정렬되기 때문에 O(n)의 시간복잡도를 가지며 매우 효율적이다. 배열 내에서 교환하는 방.. 2024. 2. 28.
[알고리즘] 선택 정렬 (Selection Sort, 개념과 장단점, 과정, 자바 코드 구현, 시간복잡도, 공간복잡도) 목차 선택 정렬이란? 선택 정렬 과정 선택 정렬 구현 (자바 코드) 시간복잡도 공간복잡도 정렬 알고리즘 비교 1. 선택 정렬이란? 정렬되지 않은 값들 중에서 최솟값(혹은 최댓값)을 찾고, 정렬되지 않은 값 중 제일 앞에 위치한 값과 교체한다. 정렬되지 않는 값들 중 제일 앞쪽 위치, 즉 해당 순서에 원소를 넣을 위치가 이미 정해져 있다. (특징) 최선, 평균, 최악의 시간복잡도는 모두 O(n^2)이다. 비교 횟수는 많지만, 실제 교환되는 횟수는 적다. 따라서 똑같은 O(n^2)의 시간복잡도를 가지는 버블 정렬보다 적은 시간이 소요된다. (장점) 알고리즘이 단순하고, 구현이 쉽다. 정렬된 배열을 반대로 재정렬할 때 효율이 좋다. 배열 내에서 교환하는 방식(제자리 정렬)으로 추가적인 메모리 공간을 필요로 하.. 2024. 2. 28.

티스토리툴바