꿀팁대방출노트

삽입 정렬(Insertion Sort) 삽입 정렬은O($n^2$)의 복잡도를 가진 대표적인 알고리즘이다. 비교 정렬, 제자리 정렬이면서 온라인 정렬 방식으로, 정렬할 원소를 이미 정렬된 배열의 적절한 위치에 삽입한다는 의미이다. 평균적으로 같은 O($n^2$)의 복잡도 정렬 알고리즘 중 좋은 성능을 보여주나, 자료구조에 따라서 최악의 성능이 나온다. 다른 복잡도의 정렬 알고리즘에 비해 이해하기는 쉬우나 구현하기는 조금 까다로운 알고리즘이다. 하지만 연결리스트라는 자료구조일 경우 정말 효율적인 알고리즘이고, 이미 정렬되어 있는 배열에 원소를 하나씩 삽입/제거하는 경우에 최고의 정렬 알고리즘이라고 평가받는다. 정렬 방법(오름차순) 배열에서 어떤 원소를 자신보다 작은 원소가 나올 때까지 왼쪽으로 이동시키면 된..

선택 정렬(Selection Sort) 선택 정렬은 O($n^2$)의 복잡도를 가진 대표적인 알고리즘이다. 비교 정렬이면서 제자리 정렬 방식으로, 한 번 돌 때마다 가장 큰 원소를 선택하여 배치한다는 의미이다. 평균적으로 같은 성능을 보여준다는 특징이 있다. 어찌보면 사람이 실제로 정렬하는 방식과 가장 유사하기 때문에 손쉽게 구현하여 사용할 수 있지만, 만들기가 쉽고 직관적일 뿐이지 대단히 비효울적인 정렬 방식이므로 실제 개발에선 사용되지 않는다. 정렬 방법(오름차순) 배열의 모든 원소를 모두 비교하여 그 중 가장 작은 값을 찾고, 찾아낸 값의 위치와 첫 번째 원소를 바꾸면 된다. 처음 모든 원소를 비교하면 총 $n-1$회 비교하게 되는데, 한 번 수행했을 경우 가장 작은 원소가 가장 앞에 위치하게 되므..

버블 정렬(Bubble Sort) 버블 정렬은 O($n^2$)의 복잡도를 가진 대표적인 알고리즘이다. 비교 정렬이면서 제자리 정렬 방식으로, 한 번 돌 때마다 마지막 하나가 정렬되어 원소들이 거품처럼 올라온다는 의미이다. 거의 모든 상황에서 최악의 성능을 보여주나, 이미 정렬된 자료에서는 최선의 성능이 나온다. 가장 생각하고 이해하기 쉬워서 각종 교습서에 예시로 많이 보여지고 손쉽게 구현하여 사용할 수 있지만, 만들기가 쉽고 직관적일 뿐이지 대단히 비효울적인 정렬 방식이므로 실제 개발에선 사용되지 않는다. 정렬 방법(오름차순) 배열의 모든 원소에 대해서 인접한 두 원소를 비교하며 앞 원소가 뒤 원소보다 비교하는 값이 클 경우 위치를 교환하면 된다. $1$번 원소와 $2$번 원소, $2$번 원소와 $3$번..

정렬(Sort) 정렬이란, 어떤 리스트가 주어졌을 때, 그 리스트를 정해진 순서대로 가지런히 나열하는 것을 의미한다. 정해진 순서로 다양한 방법이 있겠지만, 일반적으로 오름차순(Ascending) 혹은 내림차순(Descending)을 주로 사용한다. 오름차순이란 뒤로 갈수록 값이 커지는 순서로, 그래프에 표시했을 때 뒤로 갈수록 올라가기 때문이라고 이해하면 편하다. 반대로 내림차순이란 뒤로 갈수록 값이 작아지는 순서로, 오름차순과 마찬가지로 그래프를 떠올리면 쉽게 이해할 수 있다. 숫자 배열 { 9, 10, 108, 72, 66, 45, 62 } 문자열 { ‘A’, ‘a’, ‘C’, ‘K’, ‘b’, ‘z’, ‘F’ } 두 배열을 오름차순으로 정렬하면 { 9, 10, 45, 62, 66, 72, 108 ..