전체 글56 알고리즘 - 셀 정렬(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. 추상 데이터 타입(Abstract Data Type, ADT) 추상 데이터 타입(Abstract Data Type, ADT)?추상 데이터 타입은 데이터 타입을 정의하는 것이다. 이때, 데이터 타입을 정의하는 것을 데이터 추상화 혹은 추상 데이터 타입이라고 한다. 사용자는 원하는 대로 데이터 타입을 만들어 낼 수 있다. 이를 통해 사용자는 데이터를 더욱 구체적으로 표현하고 쉽게 사용할 수 있게된다. 추상 데이터 타입은 데이터가 구체적으로 어떻게 표현되어 있는지를 사용자가 알 수 없도록 숨기기 때문에 사용자는 데이터의 구체적인 표현 방식을 몰라도 된다. 이는 데이터를 더욱 안전하게 보호할 수 있게 해준다. Ex.)Conuter()카운터를 생성합니다.increment():void카운터의 값을 증가시킵니다.reset():void카운터의 값을 0으로 초기화 합니다.curr.. 2024. 7. 25. 이전 1 2 3 4 5 ··· 10 다음
