정렬 - 기수 정렬 (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

연결 리스트 - 단일 연결 리스트

배열의 중간에 데이터를 삽입/삭제할 때의 시간복잡도는 $O(n)$ 이었습니다. 따라서 삽입과 삭제가 자주 발생하는 상황에서는 배열이 비효율적일 수 있는데요, 그럼 어떠한 자료구조를 사용해야 할까요? 오늘은 삽입과 삭제의 연산이 빠른 단일 연결 리스트에 대해 알아보도록 하겠습니다. 📦  노드연결 리스트를 이해하기 위해서 알아야 하는 노드라는 개념이 있습니다. 쉽게 말해 데이터를 담고있는 박스라고 생각하면 됩니다. 연결 리스트들은 이 노드들이 여러개 모여 이루어진 구조인데요, 배열과 달리 한 노드에서 다른 노드로 이동하는 경로를 가지고 있습니다. 이것을 '다른 노드를 참조한다' 라고 합니다. 🚂  단일 연결 리스트그러면 '단일' 연결 리스트는 무엇일까요? 이름에서 알 수 있듯, 단방향(한쪽 방향)으로 연..

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

빅 오 표기법으로 표현하는 시간복잡도 (Time Complexity)

프로그램의 수행 시간은 알고리즘을 설계할 때 중요하게 고려해야 하는 요소 중 하나이기 때문에 코드를 분석해서 효율성을 따져보는것도 중요합니다. 오늘은 여러가지 연산에 대하여 저번 게시물에서 설명한 점근적 표기법인 빅 오 표기법을 이용한 시간복잡도(Time Complexity)에 대해 알아보도록 하겠습니다. #️⃣빅 오 표기법을 사용하는 이유점근적 표기법에서는 $O,\;\Omega,\;\Theta$ 3가지의 표기법이 있는데, 시간복잡도를 표현 할 때 빅 오 표기법을 사용하는것은 왜일까요? 만약 빅 오메가 $(\Omega)$ 표기법을 사용하게 된다면, 시간복잡도가 너무 낮게 표현될 가능성이 있습니다. 예를 들어 $n^{6}+1$이라는 식이 있을 때, 빅 오메가 표기법으로는 $ n^{6}+1 =\Omega(n..

• format_list_bulleted 알고리즘/이론공부
• · 2024. 10. 24.
• textsms