전체 글57 알고리즘 - 머지 정렬(Merge sort) / 머지 정렬 구현 머지 정렬?머지는 두 개의 정렬된 배열을 하나의 큰 정렬된 배열로 합치는 작업을 의미한다. 배열을 정렬할 때 배열을 반으로 나누어 각각의 절반에 대해서 재귀적으로 정렬을 수행하고 정렬된 결과를 다시 재귀적으로 병합하는 것을 머지 정렬이라고 한다. 📌 하향식 머지 정렬하향식 머지 정렬은 배열이 주어졌을 때, 배열을 더 이상 나눌 수 없을 때까지 나누고 배열이 더 이상 나누어질 수 없을 때 머지 정렬을 실행한다. 📌 실행 시간 개선 방법머지 정렬은 재귀적으로 동작하기 때문에 나누어진 배열의 크기가 작다면 삽입 정렬 알고리즘을 사용하는 게 좋다.배열이 이미 정렬되었는지 확인하고 이미 정렬된 상태로 입력되는 배열에 대한 중복된 정렬을 생략하면 이미 정렬된 부분 배열에 대한 실행 시간이 선형으로 줄어든다.원본.. 2024. 8. 2. 알고리즘 - 셀 정렬(shell sort) / 셀 정렬 구현 셀 정렬?🔑 keyword : gap, 마지막엔 삽입 정렬 셀 정렬은 ‘Donald L. Shell’이라는 사람이 제안한 방법으로 삽입정렬을 보완한 알고리즘이다. 삽입 정렬은 크기가 크고 정렬되지 않은 배열을 처리하는데 느리다. 그러나 셀 정렬은 서로 멀리 떨어진 항목 간에도 교환이 일어날 수 있다. 그리고 삽입 정렬이 빠르게 처리할 수 있도록 부분적으로 정렬된 배열을 만든다. 📌 셀 정렬 동작 순서매 h번째 한목들 간에 삽입 정렬을 수행한다.부분적으로 정렬된 배열을 h-정렬 되었다고 한다.큰 h값에 대해 h-정렬을 해서 서로 멀리 떨어진 배열 항목들을 이동시킨다.h값을 정해진 만큼 줄여나가서 1이 될 때까지 줄이면서 위의 과정을 반복한다. 📌 h-정렬h-정렬된 배열은 서로 교차하며 존재하는 h개의.. 2024. 8. 2. 알고리즘 - 삽입 정렬 (insertion sort) / 삽입 정렬 구현 삽입 정렬?항목을 삽입할 공간을 만들기 위해 삽입할 항목보다 큰 항목들을 전부 오른쪽으로 밀어서 이동시키고 확보된 빈 공간에 항목을 삽입하는 정렬 알고리즘이다. 📌 삽입 정렬의 동작 순서첫 패스스루에서 임시로 두 번째 셀(index = 1)의 값을 삭제하고 이 값을 저장해 둔다.인덱스 1에 값이 없이 때문에 공백이 생긴다.이후 각 패스스루마다 다음 인덱스의 값을 삭제한다.공백 왼쪽에 있는 각 값을 가져와 저장해둔 값과 비교한다.공백 왼쪽에 있는 값이 저장해둔 값보다 크면 그 값을 오른쪽으로 시프트한다.값을 오른쪽으로 시프트 해서 공백이 왼쪽으로 옮겨진다.임시로 삭제한 값보다 작은 값을 만나거나 배열의 왼쪽 끝에 도달하면 시프트 단계가 끝난다.임시로 제거한 값을 현재 공백에 삽입한다.1-3단계가 하나의.. 2024. 8. 2. 알고리즘 - 선택 정렬(selection sort) / 선택 정렬 구현 선택 정렬?선택 정렬은 반복적으로 남은 배열 안에서 가장 작은 항목을 선택하는 정렬 알고리즘이다. 📌 선택 정렬의 동작 순서배열 안에서 가장 작은 항목을 찾는다.그다음으로 가장 작은 항목을 찾아 두 번째 항목과 교환한다.모든 배열이 정렬될 때까지 1-2단계를 반복한다. 📌 선택 정렬의 효율성선택 정렬은 비교와 교환, 두 가지 단계를 포함하고 있다.비교 : 각 패스스루 내에서 각 값을 현재까지 찾은 최솟값과 비교한다.교환 : 최솟값을 올바른 위치에 있는 수와 교환한다. 배열의 크기가 N일 때, (N+1) + (N-2) + (N+3) + ... + 1번의 비교 연산이 필요하다. 교환은 한 번의 패스당 최대 한 번이 일어난다. 등차수열의 합 공식에 의하면 N(N-1)/2 이므로 O(N^2)이 된다. 📌 .. 2024. 8. 2. 알고리즘 - 버블 정렬(Bubble Sort) / 버블 정렬 구현 정렬이란?정렬은 객체들이 나열된 순서를 어떤 논리적인 순서에 맞도록 바꾸는 작업이다. 예를 들면 숫자들의 순서를 오름차순으로 변경하거나 내림차순으로 바꾸는 등의 일을 할 수 있다. 📌 정렬 알고리즘을 배워야 하는 이유.서로 다른 알고리즘 간의 비교하는 방법을 배울 수 있다.정렬 알고리즘에 적용한 기술들을 다른 문제에도 유사하게 활용할 수 있다.정렬을 먼저 수행하면 효율적으로 문제를 해결할 수 있거나 해결 불가능한 문제도 가능하게 해준다. 버블 정렬?각 패스마다 정렬되지 않은 값 중 가장 큰 값을 의미하는 버블이 올바른 위치로 이동하게 되면서 정렬이 수행되는 알고리즘이다. 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이라고 생각하면 쉽다. 📌 버블 정렬의 동작 순서.배열 내에서 연속된 두 항목.. 2024. 8. 2. 자료구조 - 백(Bag), 스택(Stack), 큐(Queue) 백(Bag)'우리는 항상 가방에서 물건을 꺼낼 때 중간에 있는 물건을 잡기 마련이다. 그리고 그 중간의 물건을 꺼내게 된다.'는 발상에 근거하여 Bag 자료구조가 나타나게 되었다. 백은 항목을 삭제할 수 없는 컬렉션으로 항목을 수집하고 수집된 항목들을 순회할 수 있는 도구를 제공한다. 항목들은 서로 어떤 순서로 순회하는지 전혀 상관하지 않는다. 그래서 항목의 순서에 특별히 의미가 없다면 백을 이용한다. 📌 백을 사용하는 이유백을 사용하는 이유는 단순히 데이터를 추가하고자 할 때 사용한다. 예를 들어, 중간에 조작을 하면 안 되는 로그 데이터 등의 경우에 백을 사용할 수 있다. 배열을 사용할 수도 있지만, 추상 데이터 타입은 필요한 연산만 제공하여 중간의 값을 읽거나 삭제할 수 없도록 강제하여 데이터의 .. 2024. 7. 26. 이전 1 2 3 4 5 ··· 10 다음
