코딩 테스트 개요 및 문제 풀이를 위한 자바스크립트 문법 03

이 글은 네이버 블로그에 2024년 2월 4일에 올렸던 것을 그대로 옮겨온 것입니다.

선택 정렬

선택 정렬은 매 단계에서 가장 작은 원소를 선택해서 앞으로 보내는 정렬 방법

앞으로 보내진 원소는 더 이상 위치가 변경 되지 않는다.

시간 복잡도는 비효율적인 알고리즘 중 하나다.

각 단계에서 가장 작은 원소를 선택

현재까지 처리 되지 않은 원소들 중 가장 앞의 원소와 위치 교체

선택 정렬이란 가장 작은 것을 선택해서 앞으로 보내는 정렬기법

매 단계에서 가장 작은 것을 선택하는데 약 N번의 연산이 필요하다.

결과적으로 n^2 의 시간 복잡도를 가진다.

버블 정렬

단순히 인접한 두 원소를 확인하여, 정렬이 안 되어 있다면 위치를 서로 변경

서로 인접한 두 원소를 비교하는 형태가 거품과 같다고 붙여진 이름이다.

시간 복잡도 n^2

각 단계에서는 인접한 두개의 원소를 비교하여 필요시 위치 변경

한 번의 단계가 수행되면, 가장 큰 원소가 맨뒤로 이동한다.

따라서, 그 다음 단계에서는 맨뒤로 이동한 데이터는 정렬에서 제외

각 단계를 거칠 때마다 가장 큰 값을 하나씩 확실하게 결정하는 것으로 이해

삽입 정렬

삽입 정렬 : 각 숫자를 적절한 위치에 삽입하는 정렬 기법

각 단계에서 현재 원소가 삽입될 위치

적절한 위치에 도달 될때까지 반복적으로 왼쪽으로 이동

삽입 정렬이란 각 원소를 적절한 위치에 삽입 하는 정렬

매 단계에서 현재 처리 중인 원소가 삽입 처리 N

병합 정렬

분할 정복 알고리즘

분할 : 큰 문제를 작은 부분으로 분할

정복 : 작은 부분 문제를 각각 해결

조합 : 해결한 부분 문제의 답을 이용하여 다시 큰 문제를 해결

분할 정복은 일반적으로 재귀함수로

분할 하는 방식이 동일

정복

각 부분 배열은 이미 정렬된 상태

첫째 원소부터 시작하여 하나씩 확인

총 원소 개수가 N개 일때 시간 복잡도 요구 N

정렬 기준 함수 > 우선 순위

정렬 기준 함수를 사용하지 않으면 각 원소는 문자열 취급

유니코드 값 순서대로 정렬

대소문자를 구분하지 않도록 > toUpperCase() 메서드 써라