전체 글

 (163)
선택 정렬(Selection Sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 선택 정렬(selection sort)는 비교적 간단한 정렬 알고리즘이다. ㉠ 추가적인 메모리 공간이 필요하지 않지만, 알고리즘의 수행 시간이 O(n^2)이다. ② 삽입 정렬은 제자리 알고리즘(in-place algorithm) 중 하나이다. ㉠ 제자리 알고리즘은 자료 구조를 추가로 사용하지 않아 추가적인 메모리 공간이 필요하지 않다는 것을 의미한다. ③ 선택 정렬의 기본 원리는 다음과 같다. ㉠ 정렬된 부분 배열과 정렬되지 않은 부분 배열로 나눈다. ㉡ 정렬되지 않은 부분 배열에서 가장 작은(혹은 가장 큰) 요소를 찾는다. ㉢ 정렬되지 않은 부분의 첫 번째 인덱스(혹은 제일 뒤 인덱스)와 스왑한다. ㉣ ㉡과 ㉢를 반복해서 시행해서 전체 배열이 ..
이진 검색 알고리즘(Binary Search Algorithm) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 이진 검색 알고리즘(binary search algorithm)은 크기가 n인 정렬된 배열 안에 X가 존재하는 지를 탐색하기 위한 알고리즘이다. ㉠ 이진 검색 알고리즘은 이분 탐색 알고리즘, 이진 탐색 알고리즘, 이분 검색 알고리즘이라고도 불린다. ② 이진 검색 알고리즘을 이해하기 위한 가장 쉬운 예시로 업 앤 다운(up and down)을 들 수 있다. ㉠ 상대는 숫자 한 가지를 생각한다. ㉡ x보다 큰가? -> Yes -> x보다 작은 숫자 집합은 정답에서 제외된다. ㉢ x보다 큰가? -> No-> x보다 큰 숫자 집합은 정답에서 제외된다. ㉣ 정답 x를 찾을 때까지 ㉡과 ㉢을 반복한다. ③ 특정 x를 결정하는 가장 합리적인 방법이 상한과 하..
삽입 정렬(Insertion Sort)과 이진 삽입 정렬(Binary Insertion Sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 삽입 정렬(insertion sort)는 비교적 간단한 정렬 알고리즘이다. ㉠ 추가적인 메모리 공간이 필요하지 않지만, 알고리즘의 수행 시간이 O(n^2)이다. ② 삽입 정렬은 제자리 알고리즘(in-place algorithm) 중 하나이다. ㉠ 제자리 알고리즘은 자료 구조를 추가로 사용하지 않아 추가적인 메모리 공간이 필요하지 않다는 것을 의미한다. ③ 삽입 정렬과 이진 삽입 정렬의 기본 원리는 정렬된 배열 A에 정렬할 요소를 집어넣는 것이다. ㉠ 삽입 정렬과 이진 삽입 정렬의 작동 원리는 다음과 같다. ⓐ 정렬할 배열을 정렬된 배열 A와 비정렬된 배열 B로 나눈다.(크기가 1인 배열은 정렬된 상태로 본다.) ⓑ 비정렬된 배열의 첫 번째 요소가..
백준 2263번 : 트리의 순회
백준 10830번 : 행렬 제곱
백준 1992번 : 쿼드트리
백준 1074번 : Z
분할 정복(Divide and conquer) ① 분할 정복(divide and conquer)은 컴퓨터 과학과 알고리즘 설계에서 널리 사용되는 문제 해결 전략이다. ㉠ 분할(divide) : 분할 정복 알고리즘은 큰 문제를 작은 하위 문제로 분할하는 과정을 거친다. ㉡ 정복(conquer) : 분할된 하위 문제를 재귀적으로 해결하는 과정을 거친다. 하위 문제의 크기가 충분히 작아질 경우, 직관적인 방법으로 해결할 수 있다. ㉢ 결합(combinie) : 분할된 문제를 다시 결합하면서 원래의 큰 문제의 해결책을 구한다. ② 분할 정복을 사용하는 유명한 알고리즘의 예시는 병합/합병 정렬(merge sort), 퀵 정렬(quick sort), 고속 푸리에 변환(fast fourier transform, FFT), 쉬트라센의 행렬 곱셈(Strassen's..

티스토리툴바