정렬 - 기수 정렬 (Radix Sort)

0부터 9까지의 수가 랜덤하게 있을 때, 작은 수부터 큰 수 까지 보기 좋게 정렬할 수 있습니다. 이러한 방식을 자릿수별로 반복하는 정렬법이 바로 기수정렬인데요, 오늘은 기수정렬에 대해 자세히 알아보도록 하겠습니다.🚩 기수 정렬기수 정렬은 맨 뒷 자리부터 해당 자리수를 기준으로 정렬 한 뒤, 앞으로 이동하며 각 자리수를 기준으로 정렬해 나가는 방식입니다.위와 같이 3자리 숫자가 있을 때 일의 자리를 순서대로 정렬 후, 십의 자리를 정렬해주고, 마지막으로 백의 자리를 정렬하는 과정을 거치면 숫자가 오름차순으로 정렬되는 것을 볼 수 있습니다. 정렬 방식을 조금 더 자세히 나누어 살펴보도록 하겠습니다. 가장 첫번째인 일의 자리 숫자를 정렬하는 방식은 다음과 같습니다.먼저 길이가 10인 이차원 배열이 필요합니..

• format_list_bulleted 알고리즘/이론공부
• · 2024. 11. 19.
• textsms

정렬 - 삽입 정렬 (Insertion Sort)

카드게임을 할 때, 카드를 손에 쥔 채로 카드를 한장씩 꺼내보면서 적절한 위치에 끼워넣어 순서대로 정렬시켜 본 경험이 한번쯤은 있을 것입니다. 정렬 알고리즘에도 이와 비슷한 것이 있는데요, 바로 삽입정렬입니다. 오늘은 다양한 정렬 중 삽입정렬에 대해 알아보도록 하겠습니다. 📍 삽입 정렬삽입 정렬은 앞의 모든 원소가 정렬이 되어 있다고 가정했을 때 현재 원소를 적절한 위치에 집어넣어 정렬하는 방식입니다.위와 같이 [2, 5, 6, 3, 4, 1] 순서의 배열에서, 앞의 2, 5, 6이 정렬되어 있는 경우 배열의 4번째 자리에 있는 3을 정렬해보도록 하겠습니다.3을 앞의 원소와 비교했을 때, 3보다 큰 수인 6이 나왔으므로 6과 3의 자리를 바꾸어 줍니다.그 다음 3을 앞의 원소와 비교했을 때, 3보다 큰..

• format_list_bulleted 알고리즘/이론공부
• · 2024. 11. 18.
• textsms

정렬 - 선택 정렬(Selection sort)

버블 정렬과 함께 기본적인 정렬에 속하는 정렬 알고리즘은 하나가 더 있습니다. 바로 선택 정렬인데요, 버블 정렬과 비슷하지만 약간 다른 방식의 알고리즘입니다. 오늘은 선택 정렬(Selection sort)에 대해 알아보도록 하겠습니다. 📍 선택 정렬(Selection sort)선택 정렬은 전체 값 중 가장 작은 값을 찾아 제일 앞에 두고, 첫번째 값을 제외하고 제일 작은 값을 찾아 두번째에, 두 번째까지의 값을 제외하고 가장 작은 값을 찾아 세번째에 배치하는 식의 연산을 통해 정렬하는 방식입니다.자바스크립트로 구현하면 다음과 같습니다.//숫자로 이루어진 배열 arr가 있다고 가정for (let i = 0; i 버블정렬과 비슷한 것 같지만, 버블 정렬은 정렬된 상태인 경우 중간에 중단이 가능합니다. 하지..

• format_list_bulleted 알고리즘/이론공부
• · 2024. 11. 7.
• textsms

정렬 - 버블 정렬(Bubble Sort)

배열에 1부터 10까지의 숫자가 무작위로 담겨있다고 할 때, 작은 순서대로 혹은 큰 순서대로 꺼내 쓰려면 숫자들이 차례대로 정렬이 되어 있는 편이 좋을 것입니다. 데이터를 정렬 할 경우, 사용하기도 편하고 보기도 쉽습니다. 데이터들을 정렬하는 방법은 중요하기 때문에 많은 알고리즘이 있는데요, 오늘은 그 중 거품 정렬이라고도 부르는 버블 정렬(Bubble Sort)에 대해 알아보도록 하겠습니다. 🛁 버블 정렬(거품 정렬)버블 정렬은 가장 단순하지만, 구현하기 쉬운만큼 성능이 비효율적인 정렬 알고리즘입니다. 배열이 있을 때, 첫 번째 값과 두 번째 값을 비교하고, 두 번째 값과 세 번째 값을 비교하는 방식으로 배열의 끝까지 가서 n-1번째 값과 n번째 값까지 비교합니다. 이 과정을 배열 안의 데이터가 모두..

• format_list_bulleted 알고리즘/이론공부
• · 2024. 11. 7.
• textsms

연결 리스트 - 원형 연결 리스트

이중 연결 리스트의 Head 노드와 Tail노드가 서로를 참조하고 있다면 어떨까요? 처음 노드에서 시작해 계속해서 옆으로 가다보면 다시 첫 노드로 돌아오게 될 것입니다. 오늘은 이런 원형 구조로 이루어져 있는 연결 리스트인 원형 연결 리스트에 대해 알아보도록 하겠습니다. 🔄 원형 연결 리스트원형 연결 리스트는 하나의 루프(Loop)를 이루고 있는 형태의 연결 리스트입니다. 이중 연결 리스트의 Head과 Tail을 이어주는 방식으로 간단하게 구현할 수 있습니다.이 경우, Head 노드의 prev 값이 Tail 노드가 되기 때문에 보통 출발지점인 Head만 사용하게 됩니다.따라서 최종적으로 위와 같은 모양의 연결 리스트라고 생각하시면 됩니다. 원형으로 연결되어있기 때문에 null값은 사용되지 않습니다. ✏..

• format_list_bulleted 알고리즘/이론공부
• · 2024. 11. 6.
• textsms

연결 리스트 - 반복자(Iterator)

연결 리스트에서 같은 위치에 여러번 삽입/삭제가 일어나는 경우 해당 위치를 기억하고 싶을 때는 어떻게 해야 할까요? 배열에서의 index와 같은 역할을 하는 것이 있으면 편하게 사용할 수 있지 않을까요? 이러한 역할을 해주는 것이 바로 반복자(Iterator) 입니다. 오늘은 연결리스트에서 사용하는 반복자(Iterator)에 대해서 알아보도록 하겠습니다. 🔎 반복자란?반복자는 특정 노드의 위치를 지정해줄 수 있습니다. 연결 리스트 형태에서 삽입/삭제를 하려면 해당 노드의 위치까지 탐색 과정을 먼저 거쳐야 합니다. 이는 $O(n)$의 시간복잡도가 필요한데요, 동일한 위치에 삽입/삭제가 반복적으로 일어나는 경우 반복자를 이용하여 해당 위치를 지정해두면 탐색 없이 삽입/삭제 연산이 가능하게 됩니다.  🧮 ..

• format_list_bulleted 알고리즘/이론공부
• · 2024. 11. 5.
• textsms