반응형 Javascript/알고리즘4 [JavaScript] 다음 순열 (Next Permutation) 코딩테스트 문제를 풀고 알고리즘 정리합니다. 다음순열이란? 컴퓨터 과학에서, '다음 순열'이란 주어진 순열에서 사전순으로 다음에 오는 순열을 의미합니다. 예를 들어 [1,2,3]의 다음 순열은 [1,3,2]입니다. [1,2,3]의 다음 순열을 끝까지 진행하면 아래 값처럼 진행 됩니다. [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] Javascript에서 다음 순열을 구하는 과정은 다음과 같습니다: 배열의 끝에서부터 시작하여, 현재 원소가 이전 원소보다 큰 위치(i)를 찾습니다. 이 위치는 '다음 순열'에서 숫자가 바뀌어야 하는 첫 번째 위치입니다. 다시 배열의 끝에서부터 시작하여, 위치 i의 원소보다 큰 첫 번째 원소의 위치(j)를 찾습니다. 위치 i와 j의 원소를.. 2024. 3. 8. [Javascript] 정렬 - 삽입정렬(Insertion Sort) 1. 삽입 정렬 각 숫자를 적절한 위치에 삽입하는 정렬 기법 동작 방식 1. 각 단계에서 현재 원소가 삽입될 위치를 찾는다. 2. 적절한 위치에 도달할 떄까지 반복적으로 왼쪽으로 이동한다. 시간 복잡도 삽입 정렬이란 각 원소를 적절한 위치에 삽입하는 정렬 기법 매 단계에서 현재 처리중인 원소가 삽입될 위치를 찾기위해 약 N번의 연간이 필요하다. 결과적으로 약 N개의 단계를 거친다는 점에서 최악의 경우 O(N²)의 시간 복잡도를 가진다. 삽입정렬 예시 *삽입 정렬을 수행할 떄는 처음에 첫번째 원소는 정렬이 되어있다고 고려한다. 소스코드 예시 //삽입정렬함수 function insertionSort(arr) { for (let i = 1; i < arr.length; i++){ for (let j = i; .. 2023. 11. 28. [Javascript] 정렬(2) - 버블 정렬 (Bubble sort) 1. 버블 정렬(Bubble Sort) 단순히 인접한 두 원소를 확인하여, 정렬이 안되어 있다면 위치를 서로 변경 서로 인접한 두 원소를 비교하는 형태가 거품과 같다고 하여 붙여진 이름 시간 복잡도 O(N²)로 비효율적인 정렬 알고리즘 중 하나 1-1. 동작방식 각 단계에서는 인접한 두 개의 원소를 비교하여, 필요시 위치를 변경 첫째와 둘째를 비교, 둘째와 셋째를 비교하는 방식 한 번의 단계가 수행되면, 가장 큰 원소가 맨 뒤로 이동 따라서, 그 다음 단계에서는 맨 뒤로 이동한 데이터는 정렬에서 제외 * 각 단계를 거칠 때마다 가장 큰 값을 하나씩 확실하게 결정하는 것으로 이해할 수 있다. 1-2. 시간 복잡도 최악의 경우 시간 복잡도 O(N²)을 보장 이미 정렬된 배열에 대해서 모든 비교가 필요하므로,.. 2023. 11. 27. [Javascript] 정렬(1) - 선택 정렬(sorting) 1. 선택정렬 (selection sort) 매 단계에서 가장 작은 원소를 선택해서 앞으로 보내는 정렬 방법 앞으로 보내진 원소는 더 이상 위치가 변경되지 않는다. 시간 복잡도 O(N²)로 비효율적인 정렬 알고리즘 중 하나 1-1. 동작 방식 각 단계에서 가장 작은 원소 선택 현재까지 처리되지 않은 원소들 중 가장 앞의 원소와 위치를 교체 1-2 시간 복잡도 매 단계에서 가장 작은것을 선택하는 데에 약 N번의 연산이 필요 (선형 탐색) 결과적으로 약 N개의 단계를 거친다는 점에서 최악의 경우 O(N²)의 시간 복잡도를 가진다. ex) 정렬할 배열 2 4 3 1 9 8 6 7 5 1단계 1 4 3 2 9 8 6 7 5 2단계 1 2 3 4 9 8 6 7 5 3단계 1 2 3 4 9 8 6 7 5 4단계 1.. 2023. 11. 27. 이전 1 다음 반응형